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

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