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.


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 logNone available
Dependenciesbase (==4.*), containers (>=0.4), logict [details]
AuthorDanny Gratzer
Source repositoryhead: hg clone http://bitbucket.org/jozefg/ds-kanren
UploadedThu Oct 9 04:11:53 UTC 2014 by jozefg




Maintainers' corner

For package maintainers and hackage trustees