ds-kanren: A subset of the miniKanren language

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

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


Change log None available
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:11:53Z




Maintainer's Corner

For package maintainers and hackage trustees