Eliminating duplicate results when querying a family tree with core.logic

Question

I'm modeling a family tree with core.logic. I would like to run* the queries and have them return all the results without duplication. Replacing all defn with def tabled gives me the results I expect (for now at least), and I know that condu and onceo can reduce the number of results, but I'm not sure if either of those are the best way to eliminate duplicates.

I'm particularly worried about my current approach because it seems like duplicate work to declare both the relations and the functions. I know that some of my relations are 'mutually recursive' (mothero and womano reference each other), but I did this because in the future I might add a new (defrel mother*), which should allow it to infer that a mother is both a parent and a woman.

(defrel man* person)
(defrel woman* person)
(defrel parent* child father)

(fact man* :Father)
(fact woman* :Mother)
(fact man* :Son)
(fact woman* :Daughter)
(fact parent* :Son :Father)
(fact parent* :Son :Mother)
(fact parent* :Daughter :Father)
(fact parent* :Daughter :Mother)

(defn mano [person]
(conde 
    [(man* person)]
    [(fresh [c]
        (fathero c person))]))

(defn womano [person]
(conde
    [(woman* person)]
    [(fresh [c]
        (mothero c person))]))

(defn parento [child person]
(conde
    [(parent* child person)]
    [(mothero child person)]
    [(fathero child person)]))

(defn fathero [child father]
(all
    (mano father)
    (parento child father)))

(defn mothero [child mother]
(all 
    (womano mother)
    (parento child mother)))

(defn siblingso [c1 c2 mother father]
    (all
        (mothero c1 mother)
        (mothero c2 mother)
        (fathero c1 father)
        (fathero c2 father)
        (!= c1 c2)))

(run 10 [q]
    (fresh [child parent]
        (parento child parent)
        (== q [child parent])))

(run 10 [q]
    (fresh [c1 c2 p1 p2]
        (siblingso c1 c2 p1 p2)
        (== q [c1 c2 p1 p2])))

Nicolas Buduroi Nicolas Buduroi · Accepted Answer · 2012-03-16T00:34:19

Not sure what exactly you are trying to achieve, but the goals (stuff ending in 'o') seems (as you said) redundant and they are. Also, you can't get parento to run with run* because there are no constraints on your queries. It will try to return an infinite list of child-parent pairs. Here are some example queries using your relations:

;; find all child-parent pairs
(run* [q] (fresh [c p] (parent* c p) (== q [c p])))
;=> ([:Daughter :Mother] [:Son :Mother] [:Daughter :Father] [:Son :Father])

;; find all child-father pairs
(run* [q] (fresh [c p] (parent* c p) (man* p) (== q [c p])))
;=> ([:Daughter :Father] [:Son :Father])

;; find all daughter-father pairs
(run* [q] (fresh [c p] (parent* c p) (man* p) (woman* c) (== q [c p])))
;=> ([:Daughter :Father])

;; some new facts
(fact parent* :grand-child :Son)
(fact parent* :great-grand-child :grand-child)

;; find all people who are grandparent
(run* [q] (fresh [c p gp] (parent* c p) (parent* p gp) (== q [gp])))
;=> ([:Mother] [:Father] [:Son])

And you can go on like that for a while. Logic programming makes a very powerful query language on its own even when used only with simple relations.

Update: Here's an example of brothero where the second argument should be the brother:

(defn brothero [a b]
  (fresh [f]
    (!= a b)
    (parent* a f)
    (parent* b f)
    (man* f)
    (man* b))))

(run* [q] (fresh [a b] (brothero a b) (== q [a b])))
;=> ([:Daughter :Son])

As you see I don't bother to define a parento goal as it is redundant. You should note that (!= a b) is required to not get pairs containing the same person twice and that there's a constraint on the parent to prevent doubling the answers. Obviously this example wouldn't work if you don't have the father recorded or for a man that has children from multiple women.

Eliminating duplicate results when querying a family tree with core.logic

2 Answers