src/sicp/ex2_32.clj

   1 (ns sicp.ex2_32
   2   (:use [clojure.test]))
   3
   4 (defn subsets [s]
   5   (if (empty? s)
   6     (list ())
   7     (let [r (subsets (rest s))]
   8       (concat r (map #(cons (first s) %) r)))))
   9
  10 (comment
  11 "
  12 Let s be '(1 2 3).
  13
  14 1. (subset '(1 2 3)) => (subset '(2 3)) => (subset '(3)) => (subset '())
  15 2. At this point subset returns.
  16 3. r becomes (). value of s is '(3).
  17 4. concat () with result of (map #(cons 3 %) '()) => (() (3))
  18 5. returns to previous call, where s is '(2 3).
  19 6. (map #(cons 2 %) '(() (3))) => ((2) (2 3))
  20 7. concat the above with previous r => (() (3) (2) (2 3))
  21 8. return to the previous call, where s is '(1 2 3)
  22 9. (map #(cons 1 %) '(() (3) (2) (2 3))) => ((1) (1 3) (1 2) (1 2 3))
  23 10. Append the above with previous value of r => (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
  24 "
  25 )