I have been bitten by this `thunk` overflow many times in Haskell but
rarely in Clojure
Just to play with sieve (no optimization, just test and play with
functions),
I have tried to pile up function calls, but of course recursion of
unrelated functions usually ends with a stackoverflow (trampoline seems
hard to use in this case).
(defn siev1 [i n pred]
(if (> i (/ n 2))
(remove pred (range 2 (inc n)))
(recur (inc i) n (fn [x]
(or (pred x)
(and (> x i) (zero? (rem x i))))))))
(last (siev1 2 50000 (fn [x] false))) ;; stackoverflow
But if jvm can't keep all in a stack, why not use a vector to keep
predicates in the heap
(defn some-p [preds x]
(when-let [pred (first preds)]
(if (pred x) x (recur (next preds) x))))
(defn siev2 [i n preds]
(if (> i (/ n 2))
(remove #(some-p preds %) (range 2 (inc n)))
(recur (inc i) n (conj preds #(and (> % i) (zero? (rem % i)))))))
(last (siev2 2 50000 []))
49999
Clojure is always fun to play
and I have not even try reducers yet :)
-
kawas
Le jeudi 5 septembre 2013 09:01:01 UTC+2, Cedric Greevey a écrit :
>
> Deeply nested lazy seq generation? Try wrapping the main sequence in a
> doall at each iteration of the outer loop.
>
>
> On Wed, Sep 4, 2013 at 11:53 PM, John Gabriele <[email protected]<javascript:>
> > wrote:
>
>> I tried implementing the sieve of Eratosthenes in Clojure. The approach
>> is to loop while (A) keeping my current list of numbers which have not yet
>> been eliminated, and (B) keeping track of the number I'm "on" (checking for
>> multiples thereof).
>>
>> Here's what I came up with (in a foo.clj file):
>>
>> ~~~clojure
>> (declare remove-multiples-of)
>> (declare next-one-after)
>>
>> (defn main
>> [max-num]
>> (let [starting-nums (range 2 max-num)]
>> (loop [new-nums (remove-multiples-of 2 starting-nums)
>> new-num (next-one-after 2 new-nums)]
>> (if (or (nil? new-num)
>> (> new-num (* 0.5 max-num)))
>> new-nums
>> (recur (remove-multiples-of new-num new-nums)
>> (next-one-after new-num new-nums))))))
>>
>> (defn remove-multiples-of
>> "Removes all multiples of n (but not $n * 1$) from xs."
>> [n xs]
>> (remove (fn [x] (and (> x n)
>> (zero? (rem x n))))
>> xs))
>>
>> (defn next-one-after
>> "It's assumed that xs is an ordered sequential collection of positive
>> integers, and that n is among xs. Returns the element right after n,
>> unless
>> n is the last element --- if that's the case, just returns nil."
>> [n xs]
>> (second (drop-while (fn [x]
>> (not= x n))
>> xs)))
>>
>> ;;---------------------------
>> (println (last (main 5000)))
>> ~~~
>>
>> Running that (via `lein exec foo.clj`), it appears to work.
>>
>> However, if I change that 5000 to 50000, I get a long
>> disapproving-looking stack trace starting with
>> java.lang.StackOverflowError. Why is it overflowing?
>>
>> Thanks!
>>
>> --
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Clojure" group.
>> To post to this group, send email to [email protected]<javascript:>
>> Note that posts from new members are moderated - please be patient with
>> your first post.
>> To unsubscribe from this group, send email to
>> [email protected] <javascript:>
>> For more options, visit this group at
>> http://groups.google.com/group/clojure?hl=en
>> ---
>> You received this message because you are subscribed to the Google Groups
>> "Clojure" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected] <javascript:>.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>
>
>
--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
