Generates lists of size M containing natural numbers which add up to N

notes.clj

;; list comprehensions are often used as a poor man's Prolog
;; consider the following, it has only one solution 
;; [1 1 1 1 1 1 1 1 1 1] yet we actually consider 10^10 possibilities

(for [a (range 1 11)
      b (range 1 11)
      c (range 1 11)
      d (range 1 11)
      e (range 1 11)
      f (range 1 11)
      g (range 1 11)
      h (range 1 11)
      i (range 1 11)
      j (range 1 11)
      :when (= (+ a b c d e f g h i j) 10)]
  [a b c d e f g h i j])

;; compare to, which returns instantly

(sum-list 10 10)

sum-list.clj

(defn sumo
  ([l n] (sumo l 0 n))
  ([l acc n]
     (matche [l]
       ([[]] (fd/== acc n))
       ([[x . r]]
          (fresh [nacc]
            (fd/in x (fd/interval 1 n))
            (fd/+ acc x nacc)
            (sumo r nacc n))))))

(defn sum-list [m n]
  (run* [q] (== q (lvars m)) (sumo q n)))

;; (every? #(and (= (count %) 5) (= (reduce + %) 10)) (sum-list 5 10)) => true

Nice.

It should be

(defn sum-list [m n]
  (run* [q] (== q (lvars m)) (sumo q n)))

right? Or am I missing something?

@kingtim Confirmed!

@kingtim @mrb, fixed thanks!

In fairness to the list comprehension approach, it can be made much faster:

(for [a (range 1 11)
      b (range 1 (- 11 a))
      c (range 1 (- 11 a b))
      d (range 1 (- 11 a b c ))
      e (range 1 (- 11 a b c d))
      f (range 1 (- 11 a b c d e))
      g (range 1 (- 11 a b c d e f))
      h (range 1 (- 11 a b c d e f g))
      i (range 1 (- 11 a b c d e f g h))
      j (range 1 (- 11 a b c d e f g h i))
      :when (= (+ a b c d e f g h i j) 10)]
  [a b c d e f g h i j])

@drcabana thanks for adding that, a nice way to demonstrate pruning the search.