Listing unique DAG parents with core.logic

Question

Here's a (hopefully) simple logical program I've been stuck with for a while.

I have a DAG represented by an edge relation in core.logic, when generating the list of parent nodes, I get duplicates when I have "diamond shapes" in the graph (I'm not talking about cycles here).

Is there any way to generate a distinct list of parents in this case (by re-writing parento or similar)?

(defrel edge a b)
(fact edge :a :b)
(fact edge :a :c)
(fact edge :b :d)
(fact edge :c :d)

(defne parento [x y]
  ([x y] (edge y x))   
  ([x y] (fresh [z]
           (edge z x)
           (parento z y))))

(run* [q] (parento :d q))
;; => (:b :c :a :a)

I want to get (:b :c :a) and I want to do it inside the run* statement (i.e. wrapping the result in a set is not what I'm aiming for).

Also, adding "^:tabled" to parento seems to do the trick, but I don't want the memoization that tabled introduces.

dnolen dnolen · Accepted Answer · 2012-09-26T20:34:07

There is no way to do this without leaving relational programming if you define individual facts for the edges as you've done. One solution is to simply pass the whole list of results to Clojure's set constructor. The other option is to work on all the nodes in one pass in your logic program.

It might be helpful to look at existing Prolog solutions to this problem and translating what you find.

Listing unique DAG parents with core.logic

1 Answers