Lazy sequence doesn't work in stack-consuming recursive calls

Question

I found a simple(but inefficient) solution to a problem which basically can be written like this in Clojure:

(defn make-someof [data]
  (fn sumf
    ([x n ds]
     (if (= n 1)
       (if (some #{x} ds) 1 0)
       (reduce + (for [m (filter #(< % n) ds)]
                   (sumf (- x m) (dec n) (disj ds m))))))
    ([x n] (sumf x n data))))

Which could be called like this:

((make-someof #{1 2 3 4 5 6}) 7 2)

But as it turns out, the form in the reduce section of the make-sumof function gets evaluated only once. (i.e. the filter form which has 6 values in it get iterated only for it's first value!)

I also tried using doall on the for form, thus forcing it to get computed, but the moment recursive call reaches the first form (when condition (= n 1) is held) the resulting expression (in this case 1 in the (if (some #{x} ds) 1 0) form) is returned as the result of the whole invocation chain.

It just doesn't make sense to me.
Maybe I'm making a big mistake or it's a bug in Clojure?

Note: This function is supposed to count the number of ways which the number 7 could be written as the sum of 2 other numbers from specific distinct numbers (in this case #{1 2 3 4 5 6}).

I'm rather interested in figuring out what's happening here, as this function could be written with a loop form.

Alex · Accepted Answer · 2015-10-22 18:06:45Z

2

Your filter predicate #(< % n) is meant to remove numbers from the set of available addends that are larger than the remaining target sum, but instead it's testing for addends that are less than the number of addends n. Try using #(< % x) instead.

answered Oct 22, 2015 at 18:06

Alex

14k1 gold badge40 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Diego Basch Over a year ago

BTW, your function counts 3 + 4 and 4 + 3 as two ways. Is that what you want? This would be easier to solve using math.combinatorics.

Aaron Harris Over a year ago

As an aside, you can also express your for statement using the :where condition, as (for [m ds :where (< m x)] ...). I think this is easier to read, and it might make this kind of error easier to spot. See here for more info.

Saeid Akbari Over a year ago

@Diego, Actually when 3 + 4 is counted, 4 + 3 returns 0 (thus doesn't count).

Saeid Akbari Over a year ago

@Diego, Yep, You're right. I didn't notice I fixed that in the second version I wrote!

Collectives™ on Stack Overflow

Lazy sequence doesn't work in stack-consuming recursive calls

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related