From a9b52dddae0559f286422cc12bae0ede91f63588 Mon Sep 17 00:00:00 2001
From: sgf <sgf.dma@gmail.com>
Date: Fri, 30 Aug 2024 18:00:13 +0300
Subject: [PATCH] Full 'Cont' reimplementation in go.

---
 revCps/cont.go | 141 +++++++++++++++++++++++++++++++++++++++++++++++++
 revCps/rev.go  |   2 +
 2 files changed, 143 insertions(+)
 create mode 100644 revCps/cont.go

diff --git a/revCps/cont.go b/revCps/cont.go
new file mode 100644
index 0000000..8509aa4
--- /dev/null
+++ b/revCps/cont.go
@@ -0,0 +1,141 @@
+
+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})))
+}
diff --git a/revCps/rev.go b/revCps/rev.go
index d602ccc..592d369 100644
--- a/revCps/rev.go
+++ b/revCps/rev.go
@@ -43,6 +43,8 @@ func reverseCps(xs0 []int) (R, []int) {
         }(m) // Capture current m
         */
         stepX := func (xs []int, k Cont) (R, []int) { return step(x, xs, k) } // Haskell: step x
+        // It's not a real 'Cont' though, because there is no >>=. Monads
+        // composition is done manually here. For real 'Cont' see cont.go.
         m = shift(stepX, m) // Haskell: \zs -> m =<< (shift (step x zs))
     }
 
-- 
2.20.1