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?

disconj
Try the left and the right and gather solutions that satisfy either one.
fresh
Create a fresh logical variable
===
Equate two terms. This will backtrack if we can't unify them in this branch.
run
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
[nil]
>>> map fst . runN 1 $ \t -> appendo l t l
[nil]
>>> 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

Versions 0.2.0.0, 0.2.0.1
Dependencies base (==4.*), 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 Thu Oct 9 04:15:36 UTC 2014
Distributions NixOS:0.2.0.1
Downloads 888 total (13 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees