The ds-kanren package

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]

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

Properties

Versions0.2.0.0, 0.2.0.0, 0.2.0.1
Change logNone available
Dependenciesbase (==4.*), containers (>=0.4), logict [details]
LicenseMIT
AuthorDanny Gratzer
Maintainerjozefg@cmu.edu
CategoryLanguage
Source repositoryhead: hg clone http://bitbucket.org/jozefg/ds-kanren
UploadedThu Oct 9 04:11:53 UTC 2014 by jozefg

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees