μ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

• Implement appendo, custom unify
• Logic as a state monad
• 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