Documentation ¶
Overview ¶
package memoized provides basic immutable data structures and functions for writing in a functional style.
This includes immutable trees and sequences, Map, Fold, Filter functions and a few other things.
The structures and functions contained in this package memoize the results of computations progressively, meaning multiple calls to something like Elem() on a Map'd sequence only execute the map function once.
Index ¶
- func Fold[T, U any](s Seq[T], f func(U, T) U) U
- func ToSlice[T any](s Seq[T]) []T
- type AVLTree
- type Number
- type RBTree
- type Seq
- type Vec
- func (s *Vec[T]) Append(i T) *Vec[T]
- func (s *Vec[T]) Dot(w io.Writer)
- func (s *Vec[T]) Elem(idx uint64) T
- func (s *Vec[T]) Iterate(f func(T) bool)
- func (s *Vec[T]) Join(s2 *Vec[T]) *Vec[T]
- func (s *Vec[T]) Lazy(f func(func() T))
- func (s *Vec[T]) Len() uint64
- func (s *Vec[T]) Split(idx uint64) (Seq[T], Seq[T])
- func (s *Vec[T]) Take(idx uint64) Seq[T]
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Fold ¶
Fold folds a Seq[T] `s` into a value of type U, based on the function `f`. The function `f` is run over each element of `s`. It accepts a value of type U, which is the current value (accumulator) for the fold, and a value of type T, which is the current element of `s`. The function `f` must return the new accumulator value of type U. Fold returns the final accumulator value after `f` has been run over every element of `s`.
Note: Running a fold on an infinite sequence will never terminate. One should usually use Split() or Fold() on infinite sequences first to limit the output.
For example, to sum the first 1000 primes (with imaginary isPrime and sum functions):
n := From[int](1,1) n = Filter(n, isPrime) n = n.Take(1000) result := Fold(n, sum)
Or more succinctly:
result := Fold(Filter(From[int](1,1), isPrime).Take(1000), sum)
Types ¶
type AVLTree ¶
AVLTree is a tree-based map of keys of type T to values of type U.
AVLTree is immutable, meaning operations performed on it return new trees without modifying the old. Because of the immutable nature of the structure, the new tree shares most of its memory with the original, meaning operations can be performed efficiently without needing to reconstruct an entirely new tree for every operation.
func (*AVLTree[T, U]) Delete ¶
Delete returns a new tree that does not contain the key `k`, and a boolean indicating whether or not an element was removed.
func (*AVLTree[T, U]) Dot ¶
Dot writes out a graphviz dot formatted directed graph to the writer `w`. This can be used with graphviz to visualize the tree's internal structure.
func (*AVLTree[T, U]) Get ¶
Get looks up the element in the map associated with `k`. It also returns a boolean indicating whether the value was found.
type Number ¶
type Number interface { constraints.Integer | constraints.Float }
type RBTree ¶
RBTree is a tree-based map of keys of type T to values of type U.
RBTree is immutable, meaning operations performed on it return new trees without modifying the old. Because of the immutable nature of the structure, the new tree shares most of its memory with the original, meaning operations can be performed efficiently without needing to reconstruct an entirely new tree for every operation.
func (*RBTree[T, U]) Delete ¶
Delete returns a new tree that does not contain the key `k`, and a boolean indicating whether or not an element was removed.
func (*RBTree[T, U]) Dot ¶
Dot writes out a graphviz dot formatted directed graph to the writer `w`. This can be used with graphviz to visualize the tree's internal structure.
func (*RBTree[T, U]) Get ¶
Get looks up the element in the map associated with `k`. It also returns a boolean indicating whether the value was found.
type Seq ¶
type Seq[T any] interface { // Elem returns the element at index i. // If the sequence does not contain i elements, this will panic // with an out-of-bounds error. // TODO: Perhaps this should be (T, bool) to be safer Elem(i uint64) T // Split splits a sequence after n elements, returning a Seq // containing the first n elements and one containing the // remainder of the original Seq. Split must not modify the // original Seq. Split(n uint64) (Seq[T], Seq[T]) // Take returns a Seq containing the first n elements of the // original Seq. The original Seq is not modified. // Take can be more efficient than Split since there are // more scenarios where evaluation of the Seq elements // can be delayed. Take(n uint64) Seq[T] // Iterate executes a function over every element of the Seq, // until the Seq ends or the function returns false. Iterate(func(T) bool) // Lazy executes a function over every element of the Seq, // passing the elements as thunks which will return the // element. // // This is useful to delay the execution of computations // such as maps until the execution of the thunk. For instance, // this can be used to distribute work over a set of goroutines // and have the goroutines themselves incur the cost of mapping // the elements is parallel, rather than having the routine // executing Lazy incuring the cost as is the case with Iterate. Lazy(func(func() T)) }
A Seq is a possibly unbounded sequence of elements of type T. Seqs are immutable, so any operation modifying a Seq (such as Split) must leave the original Seq intact and return two new Seqs.
Many operations on Seqs are lazy in nature, such as mapping and filtering, meaning it's possible (and useful) to map and filter infinite sequences.
func Filter ¶
Filter takes a Seq[T] 's' and returns a new Seq[T] which contains only the elements for which the func `f` returns true. The func `f` should be idempotent, as it may be called multiple times on the same element.
Example ¶
package main import ( "fmt" "github.com/knusbaum/gunk/memoized" ) func main() { // Create an infinite list of natural numbers n := memoized.From[int](1, 1) // Filter the even numbers n = memoized.Filter(n, func(i int) bool { return i%2 == 0 }) // Get the first 10 and print them n.Take(10).Iterate(func(i int) bool { fmt.Printf("%d ", i) return true }) }
Output: 2 4 6 8 10 12 14 16 18 20
func From ¶
From creates an infinite Seq[T] of numeric values (see Number) starting at start and increasing by `by`.
func Generate ¶
Generate takes a func `f` and executes it in order to generate values of type T in the resulting Seq[T].
The func `f` takes a state of any type, and should generate a value based on that state. `f` should be idempotent, as it may be executed multiple times on the same state. The func `f` must return a value of type T, and the next state of type U.
Example ¶
package main import ( "fmt" "github.com/knusbaum/gunk/memoized" ) func main() { // primes is a Seq[int] of prime numbers created by this generator primes := memoized.Generate(func(state []int) (int, []int) { // Sieve of erasthenes (sort of) // state is the list of primes followed by the current number if len(state) == 0 { return 2, []int{2, 3} } i := state[len(state)-1] state = state[:len(state)-1] outter: for { for _, p := range state { if i%p == 0 { i += 1 continue outter } } state = append(state, i, i+1) return i, state } }) // Grab the first 10 primes and print them primes.Take(10).Iterate(func(i int) bool { fmt.Printf("%d ", i) return true }) }
Output: 2 3 5 7 11 13 17 19 23 29
func Map ¶
Map takes a Seq[T] `s` and a func `f` which will be executed on every element of `s`, returning a new value of type U. It returns a new Seq[U] containing the results of the map.
The mapping is executed lazily, meaning it is safe and useful to Map over infinite sequences.
For example:
// Create an infinite list of integers. n := From[int](0,1) // Map the integers by adding 1 and converting to float64, into an infinite Seq[float64]. m := Map(n, func(i int) float64 { return float64(i) + 1 })
Example ¶
package main import ( "fmt" "github.com/knusbaum/gunk/memoized" ) func main() { // Create an infinite list of integers n := memoized.From[int](0, 1) // Map the integers to themselves mod 3 n = memoized.Map(n, func(i int) int { return i % 3 }) // Get the first 10 and print them n.Take(10).Iterate(func(i int) bool { fmt.Printf("%d ", i) return true }) }
Output: 0 1 2 0 1 2 0 1 2 0
func Repeatedly ¶
Repeatedly returns an infinite Seq[T] containing e.
Note, e is copied, so it is wise to use non-pointer or immutable values.
type Vec ¶
type Vec[T any] struct { // contains filtered or unexported fields }
Vec is a sequence of elements of type T. It is constructed internally of spans connected in a somewhat balanced tree structure.
Vec is immutable, meaning operations performed on it return new Vecs without modifying the old. Because of the immutable nature of the structure, the new Vec shares most of its memory with the original, meaning operations can be performed efficiently without needing to reconstruct an entirely new vec for every operation.
func BuildVec ¶
BuildVec constructs a Vec in an efficient way. It accepts a function, `f`, which it executes, passing `f` a function `add`. The function `add` can be called repeatedly within the body of `f` in order to progressively append elements to the Vec.
For example:
BuildVec(func(add func(int)) { for i := 0; i < 100; i++ { add(i) } })
This is more efficient than simply Appending to a Vec in a loop.
func (*Vec[T]) Append ¶
Append returns a new list containing the elements of the original Vec[T] with i appended to the end.
func (*Vec[T]) Dot ¶
Dot writes out a graphviz dot formatted directed graph to the writer `w`. This can be used with graphviz to visualize the tree's internal structure.