MicroKanren ported from Scheme to F#

MicroKanren.fs

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