使用clojure的core.logic/core.match解决Dinesman的多住宅示例

Question

在观看了Sussman的讲座http://www.infoq.com/presentations/We-Really-Dont-Know-How-To-Compute之后,我受到启发,给予core.logic和core.match一个去.我所知道的唯一例子是我以前做过的那些约束问题求解器.这个是SICP课程中使用的一个例子,也是在谈话中提到的:

Baker,Cooper,Fletcher,Miller和Smith住在一栋只有五层楼的公寓楼的不同楼层.贝克不住在顶楼.库珀不住在底层.弗莱彻不住在顶层或底层.米勒生活在比库珀更高的楼层.史密斯不住在弗莱彻附近的地板上.弗莱彻并不住在库珀附近的地板上.每个人住在哪里？

我在rosettacode网站上找到了这个:http://rosettacode.org/wiki/Dinesman%27s_multiple-dwelling_problem#PicoLisp

但不太确定如何转化为clojure.我希望有人可以使用core.logic或core.match提供解决此问题的示例

Answer 1

这是 core.logic 中的解决方案。它并不完全等同于 picolisp 算法，因为我们没有相同的可用原语，但它的总体思路是相同的。感谢您向我介绍了这个问题 - 发明很有趣permuteo，beforeo而且我有了第一个可以使用的借口conda。 编辑：使用conda那里是可怕和错误的，我conde现在又回来了。哦，好吧，有一天。

(ns dwelling.core
  (:refer-clojure :exclude [==])
  (:use clojure.core.logic))

(defn rembero [x l out]
  (fresh [head tail]
    (conso head tail l)
    (conde [(== x head) (== out tail)]
           [(fresh [new-out]
              (conso head new-out out)
              (rembero x tail new-out))])))

(defn permuteo [a b]
  (conde [(emptyo a) (emptyo b)]
         [(fresh [head tail b-tail]
            (conso head tail a)
            (rembero head b b-tail)
            (permuteo tail b-tail))]))

(defn beforeo [x y l]
  (fresh [head tail]
    (conso head tail l)
    (conde [(== x head) (fresh [more-tail]
                          (rembero y tail more-tail))]
           [(beforeo x y tail)])))

(defn not-adjacento [x y l]
  (fresh [head tail more]
    (conso head tail l)
    (resto tail more)
    (conde [(== x head) (membero y more)]
           [(== y head) (membero x more)]
           [(not-adjacento x y tail)])))

(run* [tenants]
  (fresh [a b c d e]
    (== [a b c d e] tenants)
    (permuteo tenants '[Cooper Baker Fletcher Miller Smith])
    (!= e 'Baker)
    (!= a 'Cooper)
    (!= a 'Fletcher)
    (!= e 'Fletcher)
    (beforeo 'Cooper 'Miller tenants)
    (not-adjacento 'Smith 'Fletcher tenants)
    (not-adjacento 'Fletcher 'Cooper tenants)))

;; ([Smith Cooper Baker Fletcher Miller])