Here is a roughly equivalent function generating the partitions as a sequence of sequences:
(defn bar
([n] (bar n n))
([n k]
(if (zero? n)
[[]]
(for [i (range 1 (inc (min n k))), tail (bar (- n i) i)]
(cons i tail)))))
For example,
(bar 5)
; ((1 1 1 1 1) (2 1 1 1) (2 2 1) (3 1 1) (3 2) (4 1) (5))
How lazy is bar?
for is lazy.- to make it lazier, wrap the body in a
lazy-seq.
I have my doubts about the above.
- The function recurses to depth
n.
- Wrapping the body in
lazy-seq I suspect just stacks up lazy
sequences, producing just as deep a recursive call stack on accessing the
first element.
Besides, the same tails are repeatedly computed; the more so since (bar n k) is the same for all k >= n.
If performance of this function is a specific concern, there are iterative algorithms with constant time per step. As @CharlesDuffy's comment implies, these can be re-jigged to produce lazy sequences.
Why gaze into the crystal ball when you can read the book?
The standard namespace clojure.math.combinatorics, hosted here, contains a partition function that produces a lazy sequence of the partitions of any sequence of objects - fast. Integer partition is where we count the elements of each partition of identical objects. They come out in reverse lexicographic order.
For example
(map #(map count %) (combo/partitions (repeat 5 :whatever)))
;((5) (4 1) (3 2) (3 1 1) (2 2 1) (2 1 1 1) (1 1 1 1 1))
No doubt the code can be stripped down to deal with just this case.
recurcall is pretty much exactly the same thing as having your state encapsulated for deferred (lazy) execution!