Created
August 30, 2024 14:52
-
-
Save sgf-dma/6b626f270a2aca586915fdc419735d96 to your computer and use it in GitHub Desktop.
Haskell's Cont implementation in go with reversing slice as an example.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "fmt" | |
| ) | |
| // newtype Cont r a = Cont ((a -> r) -> r) | |
| type Cont[Result any, A any] func(func(A) Result) Result | |
| // runCont :: Cont r a -> (a -> r) -> r | |
| // runCont (Cont m) k = m k | |
| func RunCont[Result any, A any] (m Cont[Result, A], f func(A) Result) Result { | |
| return m(f) | |
| } | |
| // return :: a -> Cont r a | |
| // return x = Contr $ \k -> k x | |
| func Pure[Result any, A any] (x A) Cont[Result, A] { | |
| return func(k func(A) Result) Result { | |
| return k(x) | |
| } | |
| } | |
| type MFunc[Result any, A any, B any] func(A) Cont[Result, B] | |
| // >>= :: Cont r a -> (a -> Cont r b) -> Cont r b | |
| // m >>= f = Cont $ \k -> m (\x -> runCont (f x) k) | |
| func Bind[Result any, A any, B any] (m Cont[Result, A], f func(A) Cont[Result, B]) Cont[Result, B] { | |
| //func Bind[Result any, A any, B any] (m Cont[Result, A], f MFunc[Result, A, B]) Cont[Result, B] { | |
| return func(k func(B) Result) Result { | |
| t := func(x A) Result { | |
| return f(x)(k) | |
| } | |
| return m(t) | |
| } | |
| } | |
| // >=> :: (a -> Cont r b) -> (b -> Cont r c) -> a -> Cont r c | |
| func Compose[Result any, A any, B any, C any](f func(A) Cont[Result, B], g func(B) Cont[Result, C]) func(A) Cont[Result, C] { | |
| return func(x A) Cont[Result, C] { | |
| return Bind[Result, B, C](f(x), g) | |
| } | |
| } | |
| type ShiftFunc[Result any, A any] func(func(A) Result) Result | |
| // shift :: ((a -> r) -> r) -> Cont r a | |
| // is a modified variant, which just returns 'f k' instead of longer 'runCont (f k) id', | |
| // and avoids useless wrap/unwrap in 'Cont'. | |
| func Shift[Result any, A any](f ShiftFunc[Result, A]) Cont[Result, A] { | |
| return func(k func(A) Result) Result { | |
| return f(k) | |
| } | |
| } | |
| // data R a = R (R a) | E a | |
| // is a suspended computation. | |
| type R[Result any] func() (R[Result], Result) | |
| func RunR[Result any](f R[Result], zs Result) Result { | |
| for ; f != nil; f, zs = f() { // Haskell: fix run | |
| fmt.Printf("Iterate..\n") | |
| } | |
| return zs | |
| } | |
| // step(x, xs) is ShiftFunc. | |
| // Haskell: 'step x zs' | |
| func step(x int, xs []int, k func ([]int) R[string]) R[string] { | |
| fmt.Printf("Got x = %v, xs = %v\n", x, xs) | |
| xs = append(xs, x) | |
| // Haskell: R (k (x : xs)) | |
| return func() (R[string], string) { return k(xs), "" } | |
| } | |
| // forwardCps builds string in slice order. | |
| func forwardCps(xs []int) (R[string], string) { | |
| if len(xs) == 0 { | |
| return nil, "" | |
| } | |
| // pure [] | |
| m := Pure[R[string], []int]([]int{}) | |
| for _, x := range xs { | |
| // m >>= \zs -> shift (step x zs) | |
| f := func(zs []int) Cont[R[string], []int] { | |
| g := func(k func ([]int) R[string]) R[string] { | |
| return step(x, zs, k) | |
| } | |
| return Shift[R[string], []int](g) | |
| } | |
| m = Bind[R[string], []int, []int](m, f) | |
| } | |
| // end :: a -> Cont r r | |
| end := func(zs []int) R[string] { | |
| return func() (R[string], string) { | |
| return nil, fmt.Sprintf("result is %v", zs) | |
| } | |
| } | |
| return m(end), "" | |
| } | |
| // reverseCps builds string in reverse slice order. | |
| func reverseCps(xs []int) (R[string], string) { | |
| if len(xs) == 0 { | |
| return nil, "" | |
| } | |
| // end :: a -> r | |
| end := func(zs []int) R[string] { | |
| return func() (R[string], string) { | |
| return nil, fmt.Sprintf("result is %v", zs) | |
| } | |
| } | |
| // 'mg :: a -> Cont r r' is a final continuation | |
| mg := func(zs []int) Cont[R[string], R[string]] { | |
| // >>= pure . end | |
| return Pure[R[string], R[string]](end(zs)) | |
| } | |
| for _, x := range xs { | |
| mf := func(zs []int) Cont[R[string], []int] { | |
| g := func(k func ([]int) R[string]) R[string] { | |
| return step(x, zs, k) | |
| } | |
| return Shift[R[string], []int](g) | |
| } | |
| // mf >=> mg | |
| mg = Compose[R[string], []int, []int, R[string]](mf, mg) | |
| } | |
| id := func(r R[string]) R[string] { return r } | |
| return RunCont(mg([]int{}), id), "" | |
| } | |
| func main() { | |
| fmt.Println(RunR[string](forwardCps([]int{1, 2, 3, 4}))) | |
| fmt.Println("\n") | |
| fmt.Println(RunR[string](reverseCps([]int{1, 2, 3, 4}))) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment