strange bug in range or lazy-seq?
SpiderPig
I tried experimenting with lazy sequences and wrote this program
(def nums (cons 2 (lazy-seq (map inc nums))))
(def primes (cons (first nums)
(lazy-seq (->>
(rest nums)
(remove
(fn [x]
(let [dividors (take-while #(<= (* % %) x)
primes)]
(some #(= 0 (rem x %)) dividors))))))))
It works fine. However if I redefine nums like this
(def nums (drop 2 (range)))
It gives me a wrong result
e.g. (take 5 primes) is (2 3 5 7 9)
I don't see how that can be.
I put in a println to see where the problem is
I inserted this line before the "some" function call.
(println (str "x = " x ", dividors = " (seq dividors)))
If I then define nums as (drop 2 (range))
and write (take 5 primes) I get this output
(x = 3, dividors =
x = 4, dividors = (2)
x = 5, dividors = (2)
x = 6, dividors = (2)
x = 7, dividors = (2)
x = 8, dividors = (2)
x = 9, dividors = (2)
x = 10, dividors = (2)
x = 11, dividors = (2)
x = 12, dividors = (2)
x = 13, dividors = (2)
x = 14, dividors = (2)
x = 15, dividors = (2)
x = 16, dividors = (2)
x = 17, dividors = (2)
x = 18, dividors = (2)
x = 19, dividors = (2)
x = 20, dividors = (2)
x = 21, dividors = (2)
x = 22, dividors = (2)
x = 23, dividors = (2)
x = 24, dividors = (2)
x = 25, dividors = (2)
x = 26, dividors = (2)
x = 27, dividors = (2)
x = 28, dividors = (2)
x = 29, dividors = (2)
x = 30, dividors = (2)
x = 31, dividors = (2)
2 3 5 7 9)
That just doesn't make any sense. Can anyone explain this?
btw, I use clojure 1.2.0
Alan
suggestions that don't address your problem :)
(drop 2 (range)) is the same as (iterate inc 2), and the same as your
convoluted lazy-seq, except that the iterate works here, while for
some reason the range doesn't.
You might consider zero? instead of = 0.
Sam Roberton
> (def primes (cons (first nums)
> (lazy-seq (->>
> (rest nums)
> (remove
> (fn [x]
> (let [dividors (take-while #(<= (* % %) x)
> primes)]
> (some #(= 0 (rem x %)) dividors))))))))
>
> It works fine. However if I redefine nums like this
> (def nums (drop 2 (range)))
>
> It gives me a wrong result
> e.g. (take 5 primes) is (2 3 5 7 9)
I don't have a complete answer, but...
Using your first version (cons and lazy-seq):
user> (take 25 primes)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)
Using your second version (range):
user> (take 25 primes)
(2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 37 41 43 47 53 59 61 67 71)
Notice that the range version has every odd number right up until 31,
then it switches to starting to get the primes correct from there on.
So now I'm suspicious. A quick look at the source for (range) and
note it's doing chunking, with 32-item chunks:
(defn range
...
([start end step]
(lazy-seq
(let [b (chunk-buffer 32)
comp (if (pos? step) < >)]
(loop [i start]
(if (and (< (count b) 32)
(comp i end))
(do
(chunk-append b i)
(recur (+ i step)))
(chunk-cons (chunk b)
(when (comp i end)
(range i end step)))))))))
Quite a numerical coincidence... So is it possible that the
difference is in how the lazy sequences are being called on to produce
their next item? Perhaps range, since it has a next one available and
pre-calculated already, offers its up more willingly than your
hand-rolled lazy-seq? Figuring the details of that out is beyond my
limited capabilities at the moment, but it seems worth investigating.
Finally, for interest in figuring out exactly what the two different
behaviours are:
(def right-nums (cons 2 (lazy-seq (map inc right-nums))))
(def right-primes (cons (first right-nums)
(lazy-seq (->>
(rest right-nums)
(remove
(fn [x]
(let [dividors (take-while #(<= (* % %) x)
right-primes)]
(some #(= 0 (rem x %)) dividors))))))))
(def wrong-nums (drop 2 (range)))
(def wrong-primes (cons (first wrong-nums)
(lazy-seq (->>
(rest wrong-nums)
(remove
(fn [x]
(let [dividors (take-while #(<= (* % %) x)
wrong-primes)]
(some #(= 0 (rem x %)) dividors))))))))
(def wrong-answers
(filter (fn [x]
(not (some #(= x %)
(take-while #(<= % x) right-primes))))
wrong-primes))
user> (take 2 wrong-answers)
(9 15)
user> (take 3 wrong-answers)
(9 15 21)
user> (take 5 wrong-answers)
(9 15 21 25 27)
user> (take 6 wrong-answers)
<... much time passes, I get bored, Ctrl-C ...>
; Evaluation aborted.
Hope this helps?!
Stuart Halloway
The functions range, rest, and remove are chunk-aware, so the range-based version of primes consumes a bunch of numbers before its changes become self-visible. Other functions, such as iterate, are not chunked, so the results are visible to primes sooner.
In most domains it is rare to have definitions with *this* kind of self-reference. When you do have it, your best bet is to take explicit control over the laziness by using recur and/or lazy-seq directly. The example below (simplified from contrib) demonstrates this approach to primes:
(def primes
(concat
[2]
(let [primes-from
(fn primes-from
[n]
(if (some #(zero? (rem n %))
(take-while #(<= (* % %) n) primes))
(recur (+ n 2))
(lazy-seq (cons n (primes-from (+ n 2))))))]
(primes-from 2))))
This approach also saves memory over having a separate nums collection--nums is fully (and unnecessarily) realized in memory in the implementations below.
Hope this helps,
Stu
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
babui
I've tried your definition
> (def primes
> (concat
> [2]
> (let [primes-from
> (fn primes-from
> [n]
> (if (some #(zero? (rem n %))
> (take-while #(<= (* % %) n) primes))
> (recur (+ n 2))
> (lazy-seq (cons n (primes-from (+ n 2))))))]
> (primes-from 2))))
user=> java.lang.IllegalStateException: Var user/primes is unbound.
(NO_SOURCE_FILE:27)
Any idea of what is going on?
Thanks.
JM
Jason Wolfe
On Oct 11, 6:56 pm, Stuart Halloway <stuart.hallo...@gmail.com> wrote:
> When a var's definition has a "lazy reference" to itself, as primes does below, then your results will be dependent on the lazy/chunky/strict-ness of the calls leading to the lazy reference.
Euler problems, at best this behavior seems very confusing. Everywhere
else in Clojure (that I know of) seqs are immutable, so it is strange
to observe them changing out from under you here. Perhaps it could be
an error to try to get the next of a lazy seq from within the
computation of that next, rather than just getting nil?
In fact, I can force a potentially more severe bug by modifying the
example slightly, making nums finite and computing the hash of
"primes" within the let:
(def nums (drop 2 (range 100)))
(lazy-seq (->>
(rest nums)
(remove
(fn [x]
(let [dividors (take-while #(<= (* % %) x)
primes)]
primes:
user> (take 5 primes)
33
user> primes
(2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 37 41 43 47 53 59 61 67 71
-2057877582
user> (contains? #{primes} (vec primes))
false
-Jason
SpiderPig
clojures behavior in this case,
Try running this code:
(def nums (drop 2 (range)))
(lazy-seq (->>
(rest nums)
(remove
(fn [x]
(let [dividors (take-while #(<= (* % %) x)
primes)]
It prints out:
(primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
must have length 1 and that should be impossible no matter how chunked
it is. It's hard to believe that that is intended behavior.
I don't insist that a recursive lazy definition needs to work. It
could also throw an error. But simply giving incorrect and
unpredictable results can't be a good solution in my opinion.
Stuart Halloway
(def primes
(concat
[2]
(lazy-seq
(let [primes-from
(fn primes-from
[n]
(if (some #(zero? (rem n %))
(take-while #(<= (* % %) n) primes))
(recur (+ n 2))
(lazy-seq (cons n (primes-from (+ n 2))))))]
(primes-from 3)))))
Stu
Paul Mooser
occurs (where the range-based version of primes consumes numbers
before they are visible). This really looks like a case where side
effects and implementation details are causing what appear to be
strange behaviors, based on multiple things that appear to be
equivalent (but which clearly are not). I've never gotten things set
up yet to be able to debug into clojure internals - maybe this would
be a good excuse to do so.
Stuart Halloway
As a workaround, eliminate the lazy intermediary "nums" sequence, e.g.
(def primes
(concat
[2]
(lazy-seq
(let [primes-from
(fn primes-from
[n]
(if (some #(zero? (rem n %))
(take-while #(<= (* % %) n) primes))
(recur (+ n 2))
(lazy-seq (cons n (primes-from (+ n 2))))))]
(primes-from 3)))))
Stu