ion

package module
v0.0.4 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 30, 2023 License: BSD-3-Clause Imports: 7 Imported by: 0

Documentation

Overview

package ion provides basic immutable data structures and functions on them, enabling writing Go programs in a functional style.

This includes immutable trees and sequences, Map, Fold, Filter functions and a few other things.

Computations such as those done by Map, Filter, and others are made as lazy as possible. This means that most of the operations on a Seq[T] are not actually executed until one or more elements of that sequence are realized with Elem or Iterate.

The main functionality of this package are the functions operating on the Seq[T] type. Take a look at type Seq in the index below.

See the programs in cmd/ for examples demonstrating the usage.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Always 

func Always[T any](f func(e T)) func(e T) bool

Always takes a function accepting an element T which returns nothing, and returns a function that does the same thing but always returns true.

This is useful for calls to Iterate: 

seq.Iterate(func(e int) {
    f(e)
    return true
})

becomes:
seq.Iterate(Always(f))

func Fold 

func Fold[T, U any](s Seq[T], f func(U, T) U) U

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 unbounded sequence will never terminate. One should usually use Split() or Take() on unbounded 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)

func ToSlice 

func ToSlice[T any](s Seq[T]) []T

ToSlice converts a Seq[T] into a []T.

Note: Running ToSlice on an unbounded sequence will never terminate. One should usually use Split() or Take() on unbounded sequences first to limit the output.

Types

type AVLTree 

type AVLTree[T cmp.Ordered, U any] struct {
	// contains filtered or unexported fields
}

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 

func (t *AVLTree[T, U]) Delete(k T) (*AVLTree[T, U], bool)

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 

func (r *AVLTree[T, U]) Dot(w io.Writer)

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 

func (t *AVLTree[T, U]) Get(k T) (U, bool)

Get looks up the element in the map associated with `k`. It also returns a boolean indicating whether the value was found.

func (*AVLTree[T, U]) Insert 

func (t *AVLTree[T, U]) Insert(k T, v U) *AVLTree[T, U]

Insert returns a new tree, consisting of the original tree with the key/value pair `k`/`v` added to it.

func (*AVLTree[T, U]) Size 

func (t *AVLTree[T, U]) Size() uint64

Size returns the number of elements present in the tree.

type Number 

type Number interface {
	constraints.Integer | constraints.Float
}

type RBTree 

type RBTree[T cmp.Ordered, U any] struct {
	// contains filtered or unexported fields
}

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 

func (r *RBTree[T, U]) Delete(k T) (*RBTree[T, U], bool)

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 

func (r *RBTree[T, U]) Dot(w io.Writer)

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 

func (r *RBTree[T, U]) Get(k T) (U, bool)

Get looks up the element in the map associated with `k`. It also returns a boolean indicating whether the value was found.

func (*RBTree[T, U]) Insert 

func (r *RBTree[T, U]) Insert(k T, v U) *RBTree[T, U]

Insert returns a new tree, consisting of the original tree with the key/value pair `k`/`v` added to it.

func (*RBTree[T, U]) Size 

func (r *RBTree[T, U]) Size() uint64

Size returns the number of elements present in the tree.

type Seq 

type Seq[T any] interface {
	// Elem returns the element at index i.
	// If the sequence does not contain i elements, it will return
	// the zero value of T and false.
	Elem(i uint64) (T, bool)

	// 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. If the seq contains < n elements, the
	// first returned sequence will contain all elements from
	// the original sequence and the second returned sequence
	// will be empty.
	//
	// Note: the first returned sequence may contain < n elements,
	// if the original sequence contained < n elements.
	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) bool)
}

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 unbounded sequences.

func Filter 

func Filter[T any](s Seq[T], f func(T) bool) Seq[T]

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/ion"
)

func main() {
	// Create an unbounded list of natural numbers
	n := ion.From[int](1, 1)

	// Filter the even numbers
	n = ion.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 

func From[T Number](start, by T) Seq[T]

From creates an unbounded Seq[T] of numeric values (see Number) starting at start and increasing by `by`.

func Generate 

func Generate[T, U any](f func(state U) (T, U, bool)) Seq[T]

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/ion"
)

func main() {
	// primes is a Seq[int] of prime numbers created by this generator
	primes := ion.Generate(func(state []int) (int, []int, bool) {
		// 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}, true
		}
		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, true
		}
	})

	// 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 GenerateInit 

func GenerateInit[T, U any](state U, f func(state U) (T, U, bool)) Seq[T]

func Map 

func Map[T, U any](s Seq[T], f func(T) U) Seq[U]

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 unbounded sequences.

For example: 

// Create an unbounded list of integers.
n := From[int](0,1)
// Map the integers by adding 1 and converting to float64, into an unbounded Seq[float64].
m := Map(n, func(i int) float64 { return float64(i) + 1 })

Values resulting from the application of `f` to the underlying Seq are not retained, and `f` may be called multiple times on a given element. This being the case, `f` should ideally be idempotent and stateless. If it is not, it may not be safe to Iterate the resulting Seq more than once.

Notes about State:

Although it is ideal to use idempotent functions, it is often very useful to iterate stateful functions over stateful values, for instance Map'ing a handler function over a sequence of connections (say, net.Conn). In these cases, it is important not to "realize" elements of the Seq more than once. The simplest and fool-proof way to do this is to never apply more than one operation to a seq. e.g. this is ok: 

var conns Seq[net.Conn]
conns = listen()
n := Map(conns, handle)
e := Fold(n, handleErrors)

But this bay be problematic, because we are applying multiple operations to n: 

var conns Seq[net.Conn]
conns = listen()
n := Map(conns, handle)
e := Fold(n, handleErrors)
other := n.Iterate(func(e SomeType) {
    ...
})

The Memo function may be useful in ensuring Map functions are never applied more than once to the elements of their underlying Seqs, but keep in mind this means the values of these operations are retained in memory.

Example 
package main

import (
	"fmt"

	"github.com/knusbaum/ion"
)

func main() {

	// Create an unbounded list of integers
	n := ion.From[int](0, 1)

	// Map the integers to themselves mod 3
	n = ion.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 Memo 

func Memo[T any](s Seq[T]) Seq[T]

Memo takes a Seq[T] `s` and returns a new memoized Seq[T] which is identical, except any computations involved in producing elements of `s` are cached, and subsequent accesses of those elements return the cached value.

Keep in mind that Memo'd Seq's keep their values in memory, so Memo'ing unbounded sequences can lead to unbounded memory usage if you use them carelessly. Only Memo sequences when you have a specific reason to do so.

func Repeatedly 

func Repeatedly[T any](e T) Seq[T]

Repeatedly returns an unbounded Seq[T] containing e.

Note, e is copied, so it is wise to use non-pointer or immutable values.

func StateGen 

func StateGen[T any](f func() (T, bool)) Seq[T]

StateGen takes a func `f` and executes it in order to generate values of type T in the resulting Seq[T].

The func `f` should be a clojure containing whatever state it needs to generate values. Each call to `f` should generate the next element in the sequence.

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 

func BuildVec[T any](f func(add func(T))) *Vec[T]

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 

func (s *Vec[T]) Append(i T) *Vec[T]

Append returns a new list containing the elements of the original Vec[T] with i appended to the end.

func (*Vec[T]) Dot 

func (s *Vec[T]) Dot(w io.Writer)

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 (*Vec[T]) Elem 

func (s *Vec[T]) Elem(idx uint64) (T, bool)

Elem implements Seq

func (*Vec[T]) Iterate 

func (s *Vec[T]) Iterate(f func(T) bool)

Iterate implements Seq

func (*Vec[T]) Join 

func (s *Vec[T]) Join(s2 *Vec[T]) *Vec[T]

Join returns a new Vec[T] that is the contents of the original Vec[T] followed by `s2`.

func (*Vec[T]) Lazy 

func (s *Vec[T]) Lazy(f func(func() T) bool)

Lazy implements Seq

func (*Vec[T]) Len 

func (s *Vec[T]) Len() uint64

Len returns the number of elements in the Vec

func (*Vec[T]) Split 

func (s *Vec[T]) Split(idx uint64) (Seq[T], Seq[T])

Split implements Seq

func (*Vec[T]) Take 

func (s *Vec[T]) Take(idx uint64) Seq[T]

Take implements Seq

Source Files

View all Source files

Directories

Path Synopsis
cmd
functional_echo
simple_echo
package result is an experiment in monadic types.
 package result is an experiment in monadic types.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.