[plt-scheme] miniKanren: translation from Prolog

From: Marek Kubica (marek at xivilization.net)
Date: Wed May 26 13:20:07 EDT 2010


As the miniKanren community seems to be quite dead, I thought about
posting about my problem here.

I am trying to translate the n-queen problem solution from here:
<http://okmij.org/ftp/Prolog/QueensProblem.prl> into miniKanren.

Currently, though, I am struggling with the definition of permute.

The original source code looks like this:

do_insert(X,[Y1|Y2],[Y1|Z]) :- do_insert(X,Y2,Z).

permute([X|Y],Z) :- permute(Y,Z1), do_insert(X,Z1,Z).

Which I translated into

(define do-insert conso)

(define permute
  (lambda (l1 l2)
    (fresh (l2-cadr)
           (cdro l2 l2-cadr)
            ((nullo l2-cadr) (== l1 l2))
             (let ((x (car l1))
                   (y (cdr l1)))
                   (fresh (z1)
                          (permute y z1)
                          (do-insert x z1 l2))))))))

Unfortunately, this fails because at some point, (car l1) fails because
l1 is '(). I tried replacing the let with (fresh x y) and (caro x l1)
and (cdro y l1) but that gives me an infinite loop.

Any help would be greatly appreciated!


Posted on the users mailing list.