μKanren

Haskell implementation of Jason Hemann (@jasonhemann) and Daniel P. Friedman's (@dfried00) "microKanren: A Minimal Functional Core for Relational Programming".

“In this paper, we present μKanren, a ‘featherweight’ implementation for a pure relational (logic) programming language.”

Original Scheme implementation: https://github.com/jasonhemann/microKanren

In action

appendo l s out =
  mplus
    (do l === LVal empty
        s === out)
    (do h ← fresh
        t ← fresh
        l === LVal (cons h t)
        res ← fresh
        out === LVal (cons h res)
        appendo t s res)

See Example and ExampleM files.

To do

• [x] Implement appendo, custom unify
• [x] Logic as a state monad
• [x] Tests
• [ ] Use Map for substitutions
• [ ] Polymorphic substitutions
• [ ] Reification (do not reifies for structs, like lcons)
• [ ] Nominal
• [ ] Benchmarks

Add examples

• [ ] Membero
• [ ] Oleg's numbers
• [ ] Quines generator