ds-kanren: A subset of the miniKanren language

[ language, library, mit ] [ Propose Tags ]

ds-kanren is an implementation of the miniKanren language.

What's in ds-kanren?

Try the left and the right and gather solutions that satisfy either one.
Create a fresh logical variable
Equate two terms. This will backtrack if we can't unify them in this branch.
Actually run a logical computation and return results and the constraints on them.

In addition to these core combinators, we also export a few supplimentary tools.

The opposite of ===, ensure that the left and right never unify.

The Classic Example

We can define the classic appendo relationship by encoding lists in the Lisp "bunch-o-pairs" method.

appendo :: Term -> Term -> Term -> Predicate
appendo l r o =
  conde [ program [l === "nil",  o === r]
        , manyFresh $ \h t o ->
            program [ Pair h t === l
                    , appendo t r o
                    , Pair h o === o ]]

Once we have a relationship, we can run it backwards and forwards as we can with most logic programs.

>>> let l = list ["foo", "bar"]
>>> map fst . runN 1 $ \t -> appendo t l l
>>> map fst . runN 1 $ \t -> appendo l t l
>>> map fst . runN 1 $ \t -> appendo l l t
[(foo, (bar, (foo, (bar, nil))))]

Related Links

Some good places to start learning about miniKanren would be


Maintainer's Corner

For package maintainers and hackage trustees


Versions [RSS],
Dependencies base (>=4 && <5), containers (>=0.4), logict [details]
License MIT
Author Danny Gratzer
Maintainer jozefg@cmu.edu
Category Language
Source repo head: hg clone http://bitbucket.org/jozefg/ds-kanren
Uploaded by jozefg at 2014-10-09T04:15:36Z
Distributions NixOS:
Downloads 1734 total (5 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]