Understanding Performance and Constraints in core.logic

question.markdown

Clojure 1.3.0 core.logic 0.6.8

This is the base code for which all the run calls use.

(use 'clojure.core.logic)

(defne all-in [x mems]
  ([[?a . ?b] mems]
    (membero ?a mems)
    (all-in ?b mems))
  ([() _]))

(defn listofo [predo l]
  (conde
   ((emptyo l) s#)
   ((fresh [a]
           (firsto l a)
           (predo a))
    (fresh [d]
           (resto l d)
           (listofo predo d)))))

(defrel cocktail n)
(fact cocktail :martini)
(fact cocktail :martinez)
(fact cocktail :manhattan)
(fact cocktail :ginmule)

(defrel ingredient i)
(fact ingredient :a)
(fact ingredient :b)
(fact ingredient :c)
(fact ingredient :d)


(defrel ingredients n i)
(fact ingredients :martini [:a :b])
(fact ingredients :martinez [:a :b :c])
(fact ingredients :manhattan [:b :d])
(fact ingredients :ginmule [:c :b])

(defn ingredient-predo [i]
  (fn [c]
    (fresh [a]
      (ingredients c a)
      (all-in a i))))

(defn all-ingredients-covered [c i]
  (listofo (ingredient-predo i) c))

This runs fine

(run 2 [q]
  (fresh [c i]
    (listofo cocktail c)
    (listofo ingredient i)
    (all-ingredients-covered c i)
    (!= c '())
    (!= i '())
    (== q [c i])))
;; => ([(:ginmule) (:c :b)] [(:ginmule) (:b :c)])

So does this

(run 1 [q]
  (fresh [c i]
    (listofo cocktail c)
    (listofo ingredient i)
    (all-ingredients-covered c i)
    (== c [:martini])
    (== q [c i])))
;; => ([(:martini) (:a :b)])

This either runs forever, or takes a long time (> 5 minutes) to finish

(run 1 [q]
  (fresh [c i]
    (listofo cocktail c)
    (listofo ingredient i)
    (all-ingredients-covered c i)
    (== c [:martini :manhattan])
    (== q [c i])))

My intuition says this should be quick, but it doesn't finish in ~ 5 minutes (or OOM's)

(run 1 [q]
  (fresh [c i]
    (listofo cocktail c)
    (listofo ingredient i)
    (== c [:martini :manhattan :ginmule :martinez])
    (== i [:a :b :c :d])
    (all-ingredients-covered c i)
    (== q [c i])))

Other questions

1. How can I make the list of ingredients and cocktail names a set instead of a list (or at least a unique list)?
2. Is there a better way to describe the problem to answer a question like, "what list of N ingredients makes the most different cocktails?"

Here's one possible version of alldiff:

(defne alldiff [lst]
[['()]]
[[[f]]]
[[[f s . r]] (!= f s) (alldiff (lcons f r)) (alldiff (lcons s r))])