Tree search in Clojure core.logic

Question

I've been puzzled by a modelisation problem for some time and I have to confess I have no idea how I could "properly" solve it in core.logic.

It is very easy to state: given a tree (acyclic unidirectional oriented graph) and a vertex in it, how do you use core.logic to define a goal which allow a lvar to be any reachable vertex from the given vertex?

I've started out with something as simple as possible:

(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]))

Given this configuration, I aim at defining a goal which allows a lvar to take values in ['a 'b 'c 'd]. It's straightforward to get reachable vertices with "1 hop":

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

and you can add variables for 2 hops and so on but... can it be generalized? I've thought to define a list of lvar with something like

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

but several attempts later, I must confess I'm not sure it's the correct way to go.

Answer 1

(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]))

The recursive goal:

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

Testing

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