Merge pull request #79 from fhackett/main

Variations on effectful lookup table w/ Koka

1 files changed, 83 insertions, 0 deletions

diff --git a/entries/fhackett/fib.kk b/entries/fhackett/fib.kk
new file mode 100644
index 0000000..e4d8107
--- /dev/null
+++ b/entries/fhackett/fib.kk
@@ -0,0 +1,83 @@
+
+effect store<k,v> {
+  fun put(key: k, value: v): ()
+  fun get(key: k): maybe<v>
+}
+
+fun no-store(body: () -> <store<k,v>,div|e> t): <div|e> t {
+  with handler {
+    fun get(key) Nothing
+    fun put(key, value) {}
+  } in {
+    body()
+  }
+}
+
+fun list-store(eq: (k,k) -> total bool, body: () -> <store<k,v>,div|e> t): <div|e> t {
+  var data := Nil
+  with handler {
+    fun get(key) {
+      data.lookup fn(candidate-key) key.eq(candidate-key)
+    }
+    fun put(key, value) {
+      data := Cons((key, value), data.filter(fn((kk, _)) !kk.eq(key)))
+    }
+  } in {
+    body()
+  }
+}
+
+fun pair-store(body: () -> <store<int,int>,div|e> t): <console,div|e> t {
+  var first := 0
+  var second := 1
+  var idx := 1
+
+  with handler {
+    fun get(key) {
+      if idx == key then Just(second)
+      else if idx - 1 == key then Just(first)
+      else Nothing
+    }
+    fun put(key, value) {
+      if key == idx + 1 then {
+        idx := idx + 1
+        first := second
+        second := value
+      } else {
+        println("error: " ++ key.show ++ " := " ++ value.show ++ "; " ++ first.show ++ ", " ++ second.show ++ ", " ++ idx.show)
+      }
+    }
+  } in {
+    mask<console>(body)
+  }
+}
+
+fun fib(n: int): <div,store<int,int>> int {
+  match get(n) {
+    Just(result) -> result
+    Nothing ->
+      match n {
+        0 -> 0
+        1 -> 1
+        _ ->
+          val result = fib(n - 2) + fib(n - 1)
+          put(n, result)
+          result
+      }
+  }
+}
+
+pub fun fib-naive(n: int): div int {
+  with no-store
+  fib(n)
+}
+
+pub fun fib-list(n: int): div int {
+  with list-store(fn(a: int, b: int) a == b)
+  fib(n)
+}
+
+pub fun fib-pair(n: int): <div,console> int {
+  with pair-store
+  fib(n)
+}