Documentation
¶
Overview ¶
package gunk 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.
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 a new tree without modifying the old.
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 red/black tree-based map of keys of type T to values of type U. RBTree is immutable, meaning operations performed on it return a new tree without modifying the old.
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(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"
)
func main() {
// Create an infinite list of natural numbers
n := gunk.From[int](1, 1)
// Filter the even numbers
n = gunk.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.
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"
)
func main() {
// Create an infinite list of natural numbers
n := gunk.From[int](1, 1)
// Map the naturals to themselves mod 3
n = gunk.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: 1 2 0 1 2 0 1 2 0 1
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.
Source Files