Skip to content

Instantly share code, notes, and snippets.

@maxsei
Created September 25, 2023 00:12
Show Gist options
  • Select an option

  • Save maxsei/fbe9f736d582ee2b87d3508d3d0cc9ec to your computer and use it in GitHub Desktop.

Select an option

Save maxsei/fbe9f736d582ee2b87d3508d3d0cc9ec to your computer and use it in GitHub Desktop.
this is transducers in golang using golang generics (didn't implement cat or filter sorry)
package main
import "fmt"
type InitFn[A any] func() A
type IdentityFn[A any] func(x A) A
type ReduceFn[A any, B any] func(acc A, cur B) A
type Reducer[A any, B any] struct {
Init InitFn[A]
Identity IdentityFn[B]
Reduce ReduceFn[A, B]
}
func NewReducer[A any, B any](init InitFn[A], rfn ReduceFn[A, B]) Reducer[A, B] {
return Reducer[A, B]{
Init: init,
Identity: func(x B) B { return x },
Reduce: rfn,
}
}
// Transducer is a reversed reducer order because that's how it unwinds itself
// when it is "transduced".
type Transducer[X any, A any, Y any, B any] func(Reducer[Y, B]) Reducer[X, A]
type Iterator[T any] func() (x T, done bool)
func NewIterator[T any](x []T) func() (x T, done bool) {
var i int
var zero T
return func() (T, bool) {
if i < len(x) {
i += 1
return x[i-1], false
}
return zero, true
}
}
func Map[A any, B any, T any](fn func(a A) B) Transducer[T, A, T, B] {
return func(r Reducer[T, B]) Reducer[T, A] {
return NewReducer(
func() (z T) { return z },
func(acc T, cur A) T { return r.Reduce(acc, fn(cur)) },
)
}
}
func Comp[X any, A any, Y any, B any, Z any, C any](tx1 Transducer[X, A, Y, B], tx2 Transducer[Y, B, Z, C]) Transducer[X, A, Z, C] {
return func(r Reducer[Z, C]) Reducer[X, A] {
return tx1(tx2(r))
}
}
func Push[A any]() Reducer[[]A, A] {
return NewReducer(
func() (z []A) { return z },
func(acc []A, cur A) []A { return append(acc, cur) },
)
}
func Transduce[X any, A any, Y any, B any](xform Transducer[X, A, Y, B], reducer Reducer[Y, B], xs Iterator[A]) X {
r := xform(reducer)
acc := r.Init()
for x, done := xs(); !done; x, done = xs() {
acc = r.Reduce(acc, x)
}
return acc
}
func main() {
xx := make([]int, 8)
for i := range xx {
xx[i] = i
}
type T float32
xform1 := Map[int, float64, []T](func(x int) float64 { return float64(x) * 2.5 })
xform2 := Map[float64, T, []T](func(x float64) T { return T(x) / -2 })
xform := Comp(
xform1,
xform2,
)
yy := Transduce(
xform,
Push[T](),
NewIterator(xx),
)
fmt.Printf("xx = %v\n", xx)
fmt.Printf("yy = %v\n", yy)
fmt.Printf("typeof(yy[0]) = %T\n", yy[0])
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment