Euler Up

My goal du jour is to solve some Euler problems.  I’ve been through this once before with scala, so the problems themselves are clear.  Just doing the same thing with haskell is in question.

I am tackling euler #2:  http://projecteuler.net/index.php?section=problems&id=2 Sum up all even values in the fibonacci sequence below 4 million.

Here is the core of my solution, a sequence that produces fibonacci numbers.  I wish I had a ‘zipWith’ function in scala; it sure cleans up the the ‘tuple bubble’ problem (see the end of this post).

• fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Here is how it works:  The first two values are defined zero and one.   All subsequent values are produced by a sequence generated by zipWith().  This function takes two sequences and produces a third sequence.  In this case the two inputs are the fibonacci numbers and the fibonacci numbers SKIPPING the first element (=tail).  We apply the plus operation to each pair of values from the two sequences.  The result is that zipWith() produces first (0+1) … then (1+1) … then (1+2) …  and so on.  This wonder works due to the magic of lazy loading (as in, don’t do no work until you need a number).

The rest of the solution is fairly prosaic.  Take all fibonaccis beneath some limit:

• fiblist limit = takeWhile (<limit) fibs

Take the stream of fibonaccis, filter out the evens:

• evenlist limit = filter even ( fiblist limit )

Sum up all values in the fibonacci stream:

• solve limit = foldr (+) 0 (evenlist limit)

Print the solution:

• main = print ( solve 4000000 )

Of course the commands are ass-backwards from my euler-002.hs file.  Main comes first, and the fibs definition is last.  And we could pump most of it into a single line … but who can read that?

What is this ‘tuple bubble’?   In scala the closest thing to zipWith() is the zip().  You can combine two streams, but instead of applying a function to paired elements, it produces a stream of tuples.  A tuple is an object, so it uses up memory and processing power.  Rudimentary benchmarking in scala show that traversing two arrays and applying a function is up to 40 times faster than producing a tuple and then processing it.

So I think my next mini-project will be to build a zipWith() for scala.  Meet me over in my other blog to see the results.
http://fwhaslam.wordpress.com/2010/04/21/zipwith-challenge/