README
¶
seq
Clojure-like immutable data-structures and lazy lists for go.
Installation
go get github.com/mediocregopher/seq
or if you're using goat:
- loc: https://github.com/mediocregopher/seq.git
type: git
ref: v0.1.0
path: github.com/mediocregopher/seq
Usage
Check the godocs for the full API. Also, check out the Examples section below.
Examples coming soon!
About
This library constitutes an attempt at bringing immutability and laziness to go in a thread-safe way.
Immutability
If you have any Seq data-structure, be it a List, Set, or HashMap, and you
perform an operation on it (say adding an element to it) a new instance will be
returned to you with the change, leaving the original in-place. Conceptually
it's as if a copy is made on every operation. In reality Seq uses
structure-sharing to minimize the amount of copying needed. For Sets and
HashMaps there should be only two or three node copies per operation.
Additionally, the actual values being held aren't being copied.
There are multiple advantages to immutability, and most of them have been described in great depth elsewhere. Primary benefits are:
-
Code becomes easier to think about. You never have to worry about whether or not a function you passed a variable into changed that variable. On the flip side, when inside a function you never have to worry about whether or not you're allowed to modify a variable.
-
Thread-safety comes free. Pass around variables with great abandon, there won't ever be race-conditions caused by two threads modifying the same value at the same time.
Laziness
Seq provides a common interface for all of its structures so that they can all
be treated as sequential lists of elements. With this, Seq also provides
multiple functions for iterating and modifying these sequences, such as Map,
Reduce, Filter, and so on. These correspond to similar functions in other
object oriented languages.
Where possible Seq also provides lazy forms of these functions (LMap,
LFilter, etc...). These functions return a special Lazy type, which also
implements the Seq interface. With Lazy, the next item in the sequence won't
be evalutated until it's actually needed. So if you have a lazy map over a list
but you only consume half the result, the map function will only be called on
half the elements.
Lazy sequences cache their results in a thread-safe way. So if you pass
a reference to the same Lazy to multiple threads and they all consume it, each
element is only evalutated once globally.
Legal
The license supplied in the repo applies to all code and resources provided in the repo.
Copyright Brian Picciano, 2014
Documentation
¶
Index ¶
- Constants
- func All(fn func(interface{}) bool, s Seq) bool
- func Any(fn func(el interface{}) bool, s Seq) (interface{}, bool)
- func Reduce(fn ReduceFn, acc interface{}, s Seq) interface{}
- func Size(s Seq) uint64
- func ToSlice(s Seq) []interface{}
- func ToString(s Seq, dstart, dend string) string
- type HashMap
- func (hm *HashMap) Del(key interface{}) (*HashMap, bool)
- func (hm *HashMap) FirstRest() (interface{}, Seq, bool)
- func (hm *HashMap) FirstRestKV() (*KV, *HashMap, bool)
- func (hm *HashMap) Get(key interface{}) (interface{}, bool)
- func (hm *HashMap) Set(key, val interface{}) (*HashMap, bool)
- func (hm *HashMap) Size() uint64
- func (hm *HashMap) String() string
- type KV
- type Lazy
- type List
- type ReduceFn
- type Seq
- func Drop(n uint64, s Seq) Seq
- func DropWhile(pred func(interface{}) bool, s Seq) Seq
- func Filter(fn func(el interface{}) bool, s Seq) Seq
- func Flatten(s Seq) Seq
- func LFilter(fn func(interface{}) bool, s Seq) Seq
- func LMap(fn func(interface{}) interface{}, s Seq) Seq
- func LTake(n uint64, s Seq) Seq
- func LTakeWhile(fn func(interface{}) bool, s Seq) Seq
- func Map(fn func(interface{}) interface{}, s Seq) Seq
- func Reverse(s Seq) Seq
- func Take(n uint64, s Seq) Seq
- func TakeWhile(pred func(interface{}) bool, s Seq) Seq
- type Set
- func (set *Set) DelVal(val interface{}) (*Set, bool)
- func (set *Set) Difference(s Seq) *Set
- func (set *Set) FirstRest() (interface{}, Seq, bool)
- func (set *Set) GetVal(val interface{}) (interface{}, bool)
- func (set *Set) Intersection(s Seq) *Set
- func (set *Set) SetVal(val interface{}) (*Set, bool)
- func (set *Set) Size() uint64
- func (set *Set) String() string
- func (set *Set) SymDifference(s Seq) *Set
- func (set *Set) Union(s Seq) *Set
- type Setable
- type Thunk
Examples ¶
Constants ¶
const ARITY = 32
The number of children each node in Set (implemented as a hash tree) can have
Variables ¶
This section is empty.
Functions ¶
func Any ¶
Returns the first element in Seq for which fn returns true, or nil. The returned boolean indicates whether or not a matching element was found. Completes in O(N) time.
func Reduce ¶
Reduces over the given Seq using ReduceFn, with acc as the first accumulator value in the reduce. See ReduceFn for more details on how it works. The return value is the result of the reduction. Completes in O(N) time.
func Size ¶
Returns the number of elements contained in the data structure. In general this completes in O(N) time, except for Set and HashMap for which it completes in O(1)
Types ¶
type HashMap ¶
type HashMap struct {
// contains filtered or unexported fields
}
HashMaps are actually built on top of Sets, just with some added convenience methods for interacting with them as actual key/val stores
func NewHashMap ¶
Returns a new HashMap of the given KVs (or possibly just an empty HashMap)
func (*HashMap) Del ¶
Returns a new HashMap with the given key removed from it. Also returns whether or not the key was already there (true if so, false if not). Has the same time complexity as Set's DelVal method.
func (*HashMap) FirstRest ¶
Implementation of FirstRest for Seq interface. First return value will always be a *KV or nil. Completes in O(log(N)) time.
func (*HashMap) FirstRestKV ¶
Same as FirstRest, but returns values already casted, which may be convenient in some cases.
func (*HashMap) Get ¶
Returns a value for a given key from the HashMap, along with a boolean indicating whether or not the value was found. Has the same time complexity as Set's GetVal method.
func (*HashMap) Set ¶
Returns a new HashMap with the given value set on the given key. Also returns whether or not this was the first time setting that key (false if it was already there and was overwritten). Has the same complexity as Set's SetVal method.
type KV ¶
type KV struct {
Key interface{}
Val interface{}
}
Container for a key/value pair, used by HashMap to hold its data
func (*KV) Equal ¶
Implementation of Equal for Setable. Only actually compares the key field. If compared to another KV, only compares the other key as well.
type Lazy ¶
type Lazy struct {
// contains filtered or unexported fields
}
A Lazy is an implementation of a Seq which only actually evaluates its contents as those contents become needed. Lazys can be chained together, so if you have three steps in a pipeline there aren't two intermediate Seqs created, only the final resulting one. Lazys are also thread-safe, so multiple routines can interact with the same Lazy pointer at the same time but the contents will only be evalutated once.
type List ¶
type List struct {
// contains filtered or unexported fields
}
A List is an implementation of Seq in the form of a single-linked-list, and is used as the underlying structure for Seqs for most methods that return a Seq. It is probably the most efficient and simplest of the implementations. Even though, conceptually, all Seq operations return a new Seq, the old Seq can actually share nodes with the new Seq (if both are Lists), thereby saving memory and copies.
func NewList ¶
func NewList(els ...interface{}) *List
Returns a new List comprised of the given elements (or no elements, for an empty list)
func ToList ¶
Returns the elements in the Seq as a List. Has similar properties as ToSlice. In general this completes in O(N) time. If the given Seq is already a List it will complete in O(1) time.
func (*List) Append ¶
Appends the given element to the end of the List, returning a copy of the new List. While most methods on List don't actually copy much data, this one copies the entire list. Completes in O(N) time.
func (*List) Nth ¶
Returns the nth index element (starting at 0), with bool being false if i is out of bounds. Completes in O(N) time.
func (*List) Prepend ¶
Prepends the given element to the front of the list, returning a copy of the new list. Completes in O(1) time.
func (*List) PrependSeq ¶
Prepends the argument Seq to the beginning of the callee List, returning a copy of the new List. Completes in O(N) time, N being the length of the argument Seq
type ReduceFn ¶
type ReduceFn func(acc, el interface{}) (interface{}, bool)
A function used in a reduce. The first argument is the accumulator, the second is an element from the Seq being reduced over. The ReduceFn returns the accumulator to be used in the next iteration, wherein that new accumulator will be called alongside the next element in the Seq. ReduceFn also returns a boolean representing whether or not the reduction should stop at this step. If true, the reductions will stop and any remaining elements in the Seq will be ignored.
type Seq ¶
type Seq interface {
// Returns the "first" element in the data structure as well as a Seq
// containing a copy of the rest of the elements in the data structure. The
// "first" element can be random for structures which don't have a concept
// of order (like Set). Calling FirstRest on an empty Seq (Size() == 0) will
// return "first" as nil, the same empty Seq , and false. The third return
// value is true in all other cases.
FirstRest() (interface{}, Seq, bool)
}
The general interface which most operations will actually operate on. Acts as an interface onto any data structure
func Drop ¶
Returns a Seq the is the previous Seq without the first n elements. If n is greater than the length of the Seq, returns an empty Seq. Completes in O(N) time.
func DropWhile ¶
Drops elements from the given Seq until pred returns false for an element. Returns a Seq of the remaining elements (including the one which returned false). Completes in O(N) time.
func Filter ¶
Returns a Seq containing all elements in the given Seq for which fn returned true. Completes in O(N) time.
func Flatten ¶
Flattens the given Seq into a single, one-dimensional Seq. This method only flattens Seqs found in the top level of the given Seq, it does not recurse down to multiple layers. Completes in O(N*M) time, where N is the number of elements in the Seq and M is how large the Seqs in those elements actually are.
func LTakeWhile ¶
Lazy implementation of TakeWhile
func Map ¶
Returns a Seq consisting of the result of applying fn to each element in the given Seq. Completes in O(N) time.
type Set ¶
type Set struct {
// contains filtered or unexported fields
}
A Set is an implementation of Seq in the form of a persistant hash-tree. All public operations on it return a new, immutable form of the modified variable, leaving the old one intact. Immutability is implemented through node sharing, so operations aren't actually copying the entire hash-tree everytime, only the nodes which change, making the implementation very efficient compared to just copying.
Items in sets need to be hashable and comparable. This means they either need to be some real numeric type (int, float32, etc...), string, []byte, or implement the Setable interface.
func NewSet ¶
func NewSet(vals ...interface{}) *Set
Returns a new Set of the given elements (or no elements, for an empty set)
func ToSet ¶
Returns the elements in the Seq as a set. In general this completes in O(N*log(N)) time (I think...). If the given Seq is already a Set it will complete in O(1) time. If it is a HashMap it will complete in O(1) time, and the resultant Set will be comprised of all KVs
func (*Set) DelVal ¶
Returns a new Set with the given value removed from it and whether or not the value was actually removed. Completes in O(log(N)) time.
func (*Set) Difference ¶
Returns a Set of all elements in the original Set that aren't in the Seq. Completes in O(M*log(N)), with M being the number of elements in the Seq and N the number of elements in the Set
func (*Set) GetVal ¶
Returns a value from the Set, along with a boolean indiciating whether or not the value was found. Completes in O(log(N)) time.
func (*Set) Intersection ¶
Returns a Set with all of the elements in Seq that are also in Set. Completes in O(M*log(N)), with M being the number of elements in the Seq and N the number of elements in the Set
func (*Set) SetVal ¶
Returns a new Set with the given value added to it. Also returns whether or not this is the first time setting this value (false if it was already there and was overwritten). Completes in O(log(N)) time.
func (*Set) SymDifference ¶
Returns a Set of all elements that are either in the original Set or the given Seq, but not in both. Completes in O(M*log(N)), with M being the number of elements in the Seq and N the number of elements in the Set.
func (*Set) Union ¶
Returns a Set with all of the elements of the original Set along with everything in the given Seq. If an element is present in both the Set and the Seq, the element in the Seq overwrites. Completes in O(M*log(N)), with M being the number of elements in the Seq and N the number of elements in the Set
type Setable ¶
type Setable interface {
// Returns an integer for the value. For two equivalent values (as defined
// by ==) Hash(i) should always return the same number. For multiple values
// of i, Hash should return different values if possible.
Hash(uint32) uint32
// Given an arbitrary value found in a Set, returns whether or not the two
// are equal
Equal(interface{}) bool
}
type Thunk ¶
Thunks are the building blocks a Lazy. A Thunk returns an element, another Thunk, and a boolean representing if the call yielded any results or if it was actually empty (true indicates it yielded results).
Example ¶
package main
import (
"fmt"
"github.com/mediocregopher/seq"
)
// numberThunk is used to create a sequence of inifinte, sequential integers
func numberThunk(i int) seq.Thunk {
return func() (interface{}, seq.Thunk, bool) {
return i, numberThunk(i + 1), true
}
}
// Numbers is a nice wrapper around numberThunk which creates an root thunk and
// wraps it with a Lazy
func Numbers() *seq.Lazy {
rootThunk := numberThunk(0)
return seq.NewLazy(rootThunk)
}
func main() {
var el interface{}
var s seq.Seq = Numbers()
var ok bool
for i := 0; i < 10; i++ {
if el, s, ok = s.FirstRest(); ok {
fmt.Println(el)
} else {
break
}
}
}
Output:
Source Files