How to Sum a Sequence?
Christian
For those unfamiliar, Project Euler Problem 2 states: find the sum of
all even-valued fibonacci terms that are less than four million.
Let's assume that I have the code to fill the vector:
(def fib-seq
((fn rfib [a b]
(lazy-seq (cons a (rfib b (+ a b)))))
0 1))
(def fib-vec
(into [] (filter even? (take 35 fib-seq))))
Many people reading the Clojure Samples will be familiar with the
first sample. My own implementation did not want the 'take' function
to work. However, that is a question for another day. Assume that the
magic number 35 in the second function does indeed give me all even-
valued fibonacci terms under four million. (I did not know how to
specify a predicate depending on the value of (fib-seq) to check if
the value is under 4 million.)
With the function '(reduce + (fib-vec))' I effortlessly summed up all
values in the vector. This is peculiar, because I first wanted to
write a function that does this for me, but to no avail.
(defn answer []
(let [ansVec [0]]
(while (not-empty fib-vec)
(conj ansVec (+ (last ansVec) (last fib-vec)))
(into fib-vec (pop fib-vec)))))
This function never terminates. Why not? Where am I thinking wrong?
Andreas Kostler
What you're trying to do is to build up a vector with the last element of the vector being the answer to your problem:
(last answer)
=> 4613732
You're trying to use cons (conj) to build up that list.
Now, your function below never terminates because you're:
a) Not actually building up the ans-vec
b) Not actually changing fib-vec to be closer to termination
Clojure datastructures are immutable. conj returns a new seq with the second argument conj(s)ed onto the old sequence without changing the old seq e.g.:
(def v [1 2 3])
(conj v 4)
=> [1 2 3 4]
but:
v
=> [1 2 3]
The same applies to into.
The closest I can think of you're trying to achieve is:
(defn answer []
(loop [ans-vec [0] fib-v fib-vec]
(if (empty? fib-v)
ans-vec
(recur (conj ans-vec (+ (last ans-vec) (last fib-v))) (pop fib-v)))))
Now you're actually building up ans-vec in a tail-recursive fashion while changing fib-v to be closer to termination.
Having said that, what you really want is (reduce + fib-vec) ;)
Andreas
P.S. To get your head around basic recursion dig into "The little Schemer" by Friedman and Felleisen
> --
> 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
************www.leica-geosystems.com*************
when it has to be right, Leica Geosystems
Please consider the environment before printing this email.
Tassilo Horn
Hi Christian,
> For those unfamiliar, Project Euler Problem 2 states:
> find the sum of all
Sounds like (reduce + ...).
> even-valued fibonacci terms
Sounds like (filter even? ...)
> that are less than four million.
Hm, that's a bit more challenging. I think, you could go with
(for [fib (fib-seq) :while (< fib 4000000)]
fib)
Of course, this is all completely untested. :-)
Bye,
Tassilo
Christian
Thanks for your swift reply. I'll try to explain the reasoning behind
my code.
In the Clojure Reference I found the function into, which is described
like so:
Usage: (into to from)
"Returns a new coll consisting of to-coll with all of the items of
from-coll conjoined."
I'm currently reading the book "Programming Clojure". In it, the
author has a chapter on binding which states that vectors are indeed
immutable. I'm not sure if this is a problem of scope, but I thought
that I could coerce fib-vec into receiving a new vec and throwing the
old one away (making the old one available for deletion from the GC).
That is why I used 'into fib-vec'. I thought it would re-bind fib-vec
to itself, but with one element less. I used the same idea with
ansVec.
Could you perhaps tell me why it cannot do that? Rather, is this
behavior possible in Clojure?
PS: Thanks for the book-tipp! I'll be sure to check it out.
On Mar 20, 10:48 am, Andreas Kostler
Andreas Kostler
On 20/03/2011, at 8:25 PM, Christian wrote:
> Hello Andreas!
>
> Thanks for your swift reply. I'll try to explain the reasoning behind
> my code.
>
> In the Clojure Reference I found the function into, which is described
> like so:
>
> Usage: (into to from)
> "Returns a new coll consisting of to-coll with all of the items of
> from-coll conjoined."
This is exactly what's happening:
(def v [1 2 3])
(into v (pop v))
=> [1 2 3 1 2]
However,
v
=> [1 2 3]
It does not mutate the original vector. The same applies for conj.
> I'm currently reading the book "Programming Clojure". In it, the
> author has a chapter on binding which states that vectors are indeed
> immutable. I'm not sure if this is a problem of scope, but I thought
> that I could coerce fib-vec into receiving a new vec and throwing the
> old one away (making the old one available for deletion from the GC).
> That is why I used 'into fib-vec'. I thought it would re-bind fib-vec
> to itself, but with one element less. I used the same idea with
> ansVec.
See above. into doesn't rebind it's arguments. Rather it returns a sequence which contain the second argument added to the elements of the first.
It doesn't physically alter the first argument.
>
> Could you perhaps tell me why it cannot do that? Rather, is this
> behavior possible in Clojure?
>
> PS: Thanks for the book-tipp! I'll be sure to check it out.
>
All this is intrinsic Clojure behaviour. Clojure is unique in this way. You will find that other flavours of Lisp allow mutable data (e.g. setf in common lisp).
Thassilo provided a more idiomatic solution to your problem.
Andreas
--
"Test-driven Dentistry (TDD!) - Not everything should be test driven"
- Michael Fogus
--
**********************************************************
Andreas Koestler, Software Engineer
Leica Geosystems Pty Ltd
270 Gladstone Road, Dutton Park QLD 4102
Main: +61 7 3891 9772 Direct: +61 7 3117 8808
Fax: +61 7 3891 9336
Email: andreas....@leica-geosystems.com
Daniel Werner
> valued fibonacci terms under four million. (I did not know how to
> specify a predicate depending on the value of (fib-seq) to check if
> the value is under 4 million.)
(take-while #(< % 4000000) ...)
Daniel
Christian
I've tested your code and looked at the Clojure Documentation for
'for'. Given that, I have written
(reduce +(filter even? (for [fib (fib-seq) :while (< fib 4000000)]
fib)))
This gives me the error 'clojure.lang.LazySeq cannot be cast to
clojure.lang.IFn'.
I think this is because fib-seq is a var, not a function (although I
was hard-pressed finding out what IFn stood for.) When I omit the ()
with [fib (fib-seq)...], the program works just as expected.
I would like to thank you for this suggestion and the way you
translated the problem statement into code! Do you have any resources
or books that help with such things? (Taking a problem and solving it
the way you did)
On Mar 20, 11:18 am, Tassilo Horn <tass...@member.fsf.org> wrote:
Michael Wood
On 20 March 2011 17:47, Christian <soulb...@gmail.com> wrote:
> Hello Tassilo!
>
> I've tested your code and looked at the Clojure Documentation for
> 'for'. Given that, I have written
>
> (reduce +(filter even? (for [fib (fib-seq) :while (< fib 4000000)]
> fib)))
Or using Daniel's suggestion:
(reduce + (filter even? (take-while #(< % 4000000) fib-seq)))
> This gives me the error 'clojure.lang.LazySeq cannot be cast to
> clojure.lang.IFn'.
>
> I think this is because fib-seq is a var, not a function (although I
> was hard-pressed finding out what IFn stood for.) When I omit the ()
> with [fib (fib-seq)...], the program works just as expected.
Yes, that's correct. IFn means something that implements the "Fn"
interface, i.e. it acts like a function. There are things in Clojure
which are not really functions, but can be used like functions.
e.g.: ({:foo "bar"} :foo)
or: (:foo {:foo "bar"})
--
Michael Wood <esio...@gmail.com>
Tassilo Horn
Hi Christian,
> I would like to thank you for this suggestion and the way you
> translated the problem statement into code!
Thanks for the compliment. :-)
> Do you have any resources or books that help with such things? (Taking
> a problem and solving it the way you did)
I think, my suggestions are not specific to clojure, but they apply to
any functional language. All of them have functions for filtering
sequences, applying a function to each item, reducing, and so on. Once
you know these basic functions, most computation can be expressed by
composing these in some way.
Bye,
Tassilo
Andreas Kostler
>> Do you have any resources or books that help with such things? (Taking
>> a problem and solving it the way you did)
>
> I think, my suggestions are not specific to clojure, but they apply to
> any functional language. All of them have functions for filtering
> sequences, applying a function to each item, reducing, and so on. Once
> you know these basic functions, most computation can be expressed by
> composing these in some way.
the CLisp and Scheme community provide. Peter Seibels Practical Common Lisp and
The Little Schemer, The Seasoned Schemer, and of course SICP not only teach you
how to use a Lisp which is 'simpler' than Clojure (not in terms of syntax) - this is especially
true for Scheme (not so much CLisp) but they also teach you how to recognise certain patterns that occur in
functional programs.
Once you know how those patterns match to the sequence functions you can start replacing them and
writing more concise code. That was my path anyway and I'm still learning :)
It's fun though, don't get frustrated :) This community is very helpful so don't hesitate and ask. There's no dumb
questions, you know the saying.
Andreas
Mike Meyer
Christian <soulb...@gmail.com> wrote:
> Hello Tassilo!
>
> I've tested your code and looked at the Clojure Documentation for
> 'for'. Given that, I have written
>
> (reduce +(filter even? (for [fib (fib-seq) :while (< fib 4000000)]
> fib)))
>
> This gives me the error 'clojure.lang.LazySeq cannot be cast to
> clojure.lang.IFn'.
>
> I think this is because fib-seq is a var, not a function (although I
> was hard-pressed finding out what IFn stood for.) When I omit the ()
> with [fib (fib-seq)...], the program works just as expected.
Since nobody answered the implied question: yes, you're right. The fix
is to just remove the ()'s from fib-seq to reference it directly, like
so:
(reduce + (for [fib fib-seq :while (< fib 4000000) :when (even? fib)] fib))
Note that I replaced the filter with the for loops :when test. No real
reason, it just feels more natural to use what for offers since you
started with it. Personally, I'd probably use Daniel's
filter/take-while solution.
<mike
--
Mike Meyer <m...@mired.org> http://www.mired.org/consulting.html
Independent Software developer/SCM consultant, email for more information.
O< ascii ribbon campaign - stop html mail - www.asciiribbon.org