Skip to content

Instantly share code, notes, and snippets.

@jdh30
Created February 18, 2017 15:26
Show Gist options
  • Save jdh30/55a3e0815890ca03eae2f3283b83a3d9 to your computer and use it in GitHub Desktop.
Save jdh30/55a3e0815890ca03eae2f3283b83a3d9 to your computer and use it in GitHub Desktop.
MicroKanren ported from Scheme to F#
type Term =
| Var of int
| Pair of Term * Term
| Int of int
let (|Find|_|) s k = Map.tryFind k s
let rec walk (s: Map<_,_>) = function
| Var(Find s t) -> walk s t
| t -> t
let extend s (v, t) = Map.add v t s
let rec unify u v s =
match walk s u, walk s v with
| Var u, Var v -> Some(if u=v then s else extend s (u, Var v))
| Var u, v | v, Var u -> Some(extend s (u, v))
| Pair(u1, u2), Pair(v1, v2) ->
Option.bind (unify u2 v2) (unify u1 v1 s)
| Int i1, Int i2 -> if i1=i2 then Some s else None
| _ -> None
let (==) u v (s, n) =
seq { match unify u v s with
| None -> ()
| Some s -> yield s, n }
let fresh f (s, n) = f (Var n) (s, n + 1)
let (||) g1 g2 a = Seq.collect (fun g -> g a) [g1; g2]
let (&&) g1 g2 a = Seq.collect g2 (g1 a)
let empty = Map.empty, 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment