clojure - Clojure core.logic 中的树搜索

Question

一段时间以来，我一直对模型化问题感到困惑，我不得不承认我不知道如何在core.logic.

很容易说：给定一棵树（非循环单向图）和其中的一个顶点，你如何使用core.logic来定义一个允许 lvar 成为给定顶点的任何可到达顶点的目标？

我从尽可能简单的事情开始：

(defrel vertex x)
(defrel child)
(def facts
  (pldb/db
    [vertex 'a]
    [vertex 'b] [child 'a 'b]
    [vertex 'c] [child 'b 'c]
    [vertex 'd] [child 'c 'd]))

鉴于这种配置，我的目标是定义一个目标，它允许 lvar 采用 ['a 'b 'c 'd] 中的值。使用“1 hop”获得可到达的顶点很简单：

(defn reachableo
  [a]
  (fresh [q]
    (child a q)))

你可以为 2 跳添加变量等等，但是......它可以概括吗？我想用类似的东西定义一个 lvar 列表

(let [vars (repeatedly lvar)]
  (map #(child (nth vars %) (nth vars (inc %)))
       (-> vars count dec range))
  (all
    ...))

但是经过几次尝试，我必须承认我不确定这是正确的方法。

Answer 1

感谢您的帮助！

其实我得到了

(defn order-relationo
  "Abstract the general pattern of a order relation in a logic, relational way."
  [relation x y]
  (conde
   [(relation x y)]
   [(fresh [z]
      (relation x z)
      (order-relationo relation z y))]))

(def kino
  "A goal where the two inputs x and y share kinship: x is an ancestor of y and
  y a descandant of x."
  (partial order-relationo child))

我问这个问题是因为我很久没有练习逻辑编程但现在我觉得它又来了^^

无论如何，非常感谢您的回答，这给了我一个额外的观点。

Answer 2

(pldb/db-rel vertex x)
(pldb/db-rel child parent child)
(def facts
  (pldb/db
    [vertex 'a]
    [vertex 'b] [child 'a 'b]
    [vertex 'c] [child 'b 'c]
    [vertex 'd] [child 'c 'd]))

递归目标：

(defn reachable° [from to]
  (l/fresh [v]
    (l/conde
      [(child from to)]
      [(child from v) (reachable° v to)])))

测试

=> (pldb/with-db facts
     (vec (l/run* [to] (reachable° 'a to))))
[b c d]