ty: github.com/BurntSushi/ty/fun Index | Examples | Files

package fun

import "github.com/BurntSushi/ty/fun"

Package fun provides type parametric utility functions for lists, sets, channels and maps.

The central contribution of this package is a set of functions that operate on values without depending on their types while maintaining type safety at run time using the `reflect` package.

There are two primary concerns when deciding whether to use this package or not: the loss of compile time type safety and performance. In particular, with regard to performance, most functions here are much slower than their built-in counter parts. However, there are a couple where the overhead of reflection is relatively insignificant: AsyncChan and ParMap.

In terms of code structure and organization, the price is mostly paid inside of the package due to the annoyances of operating with `reflect`. The caller usually only has one obligation other than to provide values consistent with the type of the function: type assert the result to the desired type.

When the caller provides values that are inconsistent with the parametric type of the function, the function will panic with a `TypeError`. (Either because the types cannot be unified or because they cannot be constructed due to limitations of the `reflect` package. See the `github.com/BurntSushi/ty` package for more details.)

Requirements

Go tip (or 1.1 when it's released) is required. This package will not work with Go 1.0.x or earlier.

The very foundation of this package only recently became possible with the addition of 3 new functions in the standard library `reflect` package: SliceOf, MapOf and ChanOf. In particular, it provides the ability to dynamically construct types at run time from component types.

Further extensions to this package can be made if similar functions are added for structs and functions(?).

Examples

Squaring each integer in a slice:

square := func(x int) int { return x * x }
nums := []int{1, 2, 3, 4, 5}
squares := Map(square, nums).([]int)

Reversing any slice:

slice := []string{"a", "b", "c"}
reversed := Reverse(slice).([]string)

Sorting any slice:

// Sort a slice of structs with first class functions.
type Album struct {
	Title string
	Year int
}
albums := []Album{
	{"Born to Run", 1975},
	{"WIESS",       1973},
	{"Darkness",    1978},
	{"Greetings",   1973},
}

less := func(a, b Album) bool { return a.Year < b.Year },
sorted := QuickSort(less, albums).([]Album)

Parallel map:

// Compute the prime factorization concurrently
// for every integer in [1000, 10000].
primeFactors := func(n int) []int { // compute prime factors }
factors := ParMap(primeFactors, Range(1000, 10001)).([]int)

Asynchronous channel without a fixed size buffer:

s, r := AsyncChan(new(chan int))
send, recv := s.(chan<- int), r.(<-chan int)

// Send as much as you want.
for i := 0; i < 100; i++ {
	s <- i
}
close(s)
for i := range recv {
	// do something with `i`
}

Shuffle any slice in place:

jumbleMe := []string{"The", "quick", "brown", "fox"}
Shuffle(jumbleMe)

Function memoization:

// Memoizing a recursive function like `fibonacci`.
// Write it like normal:
var fib func(n int64) int64
fib = func(n int64) int64 {
	switch n {
	case 0:
		return 0
	case 1:
		return 1
	}
	return fib(n - 1) + fib(n - 2)
}

// And wrap it with `Memo`.
fib = Memo(fib).(func(int64) int64)

// Will keep your CPU busy for a long time
// without memoization.
fmt.Println(fib(80))

Index

Examples

Package Files

chan.go doc.go func.go list.go map.go rand.go set.go sort.go util.go

func All Uses

func All(f, xs interface{}) bool

All has a parametric type:

func All(p func(A) bool, xs []A) bool

All returns `true` if and only if every element in `xs` satisfies `p`.

func AsyncChan Uses

func AsyncChan(baseChan interface{}) (send, recv interface{})

AsyncChan has a parametric type:

func AsyncChan(chan A) (send chan<- A, recv <-chan A)

AsyncChan provides a channel abstraction without a fixed size buffer. The input should be a pointer to a channel that has a type without a direction, e.g., `new(chan int)`. Two new channels are returned: `send` and `recv`. The caller must send data on the `send` channel and receive data on the `recv` channel.

Implementation is inspired by Kyle Lemons' work: https://github.com/kylelemons/iq/blob/master/iq_slice.go

func Concat Uses

func Concat(xs interface{}) interface{}

Concat has a parametric type:

func Concat(xs [][]A) []A

Concat returns a new flattened list by appending all elements of `xs`.

func Copy Uses

func Copy(xs interface{}) interface{}

Copy has a parametric type:

func Copy(xs []A) []A

Copy returns a copy of `xs` using Go's `copy` operation.

func Difference Uses

func Difference(a, b interface{}) interface{}

Difference has a parametric type:

func Difference(a map[A]bool, b map[A]bool) map[A]bool

Difference returns a set with all elements in `a` that are not in `b`. The sets `a` and `b` are not modified.

func Exists Uses

func Exists(f, xs interface{}) bool

Exists has a parametric type:

func Exists(p func(A) bool, xs []A) bool

Exists returns `true` if and only if an element in `xs` satisfies `p`.

func Filter Uses

func Filter(p, xs interface{}) interface{}

Filter has a parametric type:

func Filter(p func(A) bool, xs []A) []A

Filter returns a new list only containing the elements of `xs` that satisfy the predicate `p`.

func Foldl Uses

func Foldl(f, init, xs interface{}) interface{}

Foldl has a parametric type:

func Foldl(f func(A, B) B, init B, xs []A) B

Foldl reduces a list of A to a single element B using a left fold with an initial value `init`.

func Foldr Uses

func Foldr(f, init, xs interface{}) interface{}

Foldr has a parametric type:

func Foldr(f func(A, B) B, init B, xs []A) B

Foldr reduces a list of A to a single element B using a right fold with an initial value `init`.

func In Uses

func In(needle, haystack interface{}) bool

In has a parametric type:

func In(needle A, haystack []A) bool

In returns `true` if and only if `v` can be found in `xs`. The equality test used is Go's standard `==` equality and NOT deep equality.

Note that this requires that `A` be a type that can be meaningfully compared.

func Intersection Uses

func Intersection(a, b interface{}) interface{}

Intersection has a parametric type:

func Intersection(a map[A]bool, b map[A]bool) map[A]bool

Intersection returns the intersection of two sets, where a set is represented as a `map[A]bool`. The sets `a` and `b` are not modified.

func Keys Uses

func Keys(m interface{}) interface{}

Keys has a parametric type:

func Keys(m map[A]B) []A

Keys returns a list of the keys of `m` in an unspecified order.

func Map Uses

func Map(f, xs interface{}) interface{}

Map has a parametric type:

func Map(f func(A) B, xs []A) []B

Map returns the list corresponding to the return value of applying `f` to each element in `xs`.

func Memo Uses

func Memo(f interface{}) interface{}

Memo has a parametric type:

func Memo(f func(A) B) func(A) B

Memo memoizes any function of a single argument that returns a single value. The type `A` must be a Go type for which the comparison operators `==` and `!=` are fully defined (this rules out functions, maps and slices).

Code:

// Memoizing a recursive function like `fibonacci`.
// Write it like normal:
var fib func(n int64) int64
fib = func(n int64) int64 {
    switch n {
    case 0:
        return 0
    case 1:
        return 1
    }
    return fib(n-1) + fib(n-2)
}

// And wrap it with `Memo`.
fib = Memo(fib).(func(int64) int64)

// Will keep your CPU busy for a long time
// without memoization.
fmt.Println(fib(80))

Output:

23416728348467685

func ParMap Uses

func ParMap(f, xs interface{}) interface{}

ParMap has a parametric type:

func ParMap(f func(A) B, xs []A) []B

ParMap is just like Map, except it applies `f` to each element in `xs` concurrently using N worker goroutines (where N is the number of CPUs available reported by the Go runtime). If you want to control the number of goroutines spawned, use `ParMapN`.

It is important that `f` not be a trivial operation, otherwise the overhead of executing it concurrently will result in worse performance than using a `Map`.

func ParMapN Uses

func ParMapN(f, xs interface{}, n int) interface{}

ParMapN has a parametric type:

func ParMapN(f func(A) B, xs []A, n int) []B

ParMapN is just like Map, except it applies `f` to each element in `xs` concurrently using `n` worker goroutines.

It is important that `f` not be a trivial operation, otherwise the overhead of executing it concurrently will result in worse performance than using a `Map`.

func QuickSort Uses

func QuickSort(less, xs interface{}) interface{}

QuickSort has a parametric type:

func QuickSort(less func(x1 A, x2 A) bool, []A) []A

QuickSort applies the "quicksort" algorithm to return a new sorted list of `xs`, where `xs` is not modified.

`less` should be a function that returns true if and only if `x1` is less than `x2`.

func Range Uses

func Range(start, end int) []int

Range generates a list of integers corresponding to every integer in the half-open interval [x, y).

Range will panic if `end < start`.

func Reverse Uses

func Reverse(xs interface{}) interface{}

Reverse has a parametric type:

func Reverse(xs []A) []A

Reverse returns a new slice that is the reverse of `xs`.

func Sample Uses

func Sample(population interface{}, n int) interface{}

Sample has a parametric type:

func Sample(population []A, n int) []A

Sample returns a random sample of size `n` from a list `population` using a default random number generator seeded once at program initialization. All elements in `population` have an equal chance of being selected. If `n` is greater than the size of `population`, then `n` is set to the size of the population.

func SampleGen Uses

func SampleGen(population interface{}, n int, rng *rand.Rand) interface{}

SampleGen has a parametric type:

func SampleGen(population []A, n int, rng *rand.Rand) []A

SampleGen returns a random sample of size `n` from a list `population` using a given random number generator `rng`. All elements in `population` have an equal chance of being selected. If `n` is greater than the size of `population`, then `n` is set to the size of the population.

func Set Uses

func Set(xs interface{}) interface{}

Set has a parametric type:

func Set(xs []A) map[A]bool

Set creates a set from a list.

func Shuffle Uses

func Shuffle(xs interface{})

Shuffle has a parametric type:

func Shuffle(xs []A)

Shuffle shuffles `xs` in place using a default random number generator seeded once at program initialization.

func ShuffleGen Uses

func ShuffleGen(xs interface{}, rng *rand.Rand)

ShuffleGen has a parametric type:

func ShuffleGen(xs []A, rng *rand.Rand)

ShuffleGen shuffles `xs` in place using the given random number generator `rng`.

func Sort Uses

func Sort(less, xs interface{})

Sort has a parametric type:

func Sort(less func(x1 A, x2 A) bool, []A)

Sort uses the standard library `sort` package to sort `xs` in place.

`less` should be a function that returns true if and only if `x1` is less than `x2`.

func Union Uses

func Union(a, b interface{}) interface{}

Union has a parametric type:

func Union(a map[A]bool, b map[A]bool) map[A]bool

Union returns the union of two sets, where a set is represented as a `map[A]bool`. The sets `a` and `b` are not modified.

func Values Uses

func Values(m interface{}) interface{}

Values has a parametric type:

func Values(m map[A]B) []B

Values returns a list of the values of `m` in an unspecified order.

Package fun imports 7 packages (graph) and is imported by 10 packages. Updated 2016-07-20. Refresh now. Tools for package owners.