3
\$\begingroup\$

Problem

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

My solution

-- Formula for finding n-th Fibonacci number
fibonacci 1 = 1
fibonacci 2 = 2
fibonacci n
    | n >= 3    = fibonacci (n - 1) + fibonacci (n - 2) 
    | otherwise = fibonacci 2 + fibonacci 1

-- Intermediate code: list of first 32 Fibonacci numbers
fibonacciList = [fibonacci i | i <- [1..32]]

-- list of even Fibonacci numbers from fibonacciList
evenFibonacci = [eF | eF <- fibonacciList, eF `mod` 2 == 0]

-- list of evenFibonacci from fibonacciList not exceeding 4 million
evenFibonacci' = [eF' | eF' <- evenFibonacci, eF' <= 4000000]

-- sum of the even fibonacci numbers not exceeding 4 million
sumEvenFibonacci' = sum evenFibonacci'

-- display the result
main = print sumEvenFibonacci
\$\endgroup\$
4
\$\begingroup\$

Your fibonacci function is veryyyyyy slow. Why? Well

fibonacci 5 = fibonacci 3 + fibonacci 4
            = fibonacci 1 + fibonacci 2 + fibonacci 2 + fibonacci 3
            = 1 + 2 + 2 + fibonacci 1 + fibonacci 2
            = 8

Do you see what's wrong? That's right, you computed fibonacci 3 two times. So, for high values of n, you are going to compute it a lot! The naive linear fibonacci is usually written as fibonacci = 0 : 1 : (zipWith (+) fibonacci (tail fibonacci)) and is explained here: https://stackoverflow.com/questions/43486880/take-n-with-zipwith-and-tail

Another tip: Do not overuse list comprehension, it tends to get very unreadable fast. For instance your:

evenFibonacci' = [eF' | eF' <- evenFibonacci, eF' <= 4000000]

Is misleading because it wouldn't work if evenFibonacci is infinite (but it really should). I believe that is why you declared fibonacciList as finite, while there wasn't any reason to. So how could we make it so it does? Well we know evenFibonacci is strictly increasing, so we could take advantage of it:

evenFibonacci' = takeWhile (<= 40000) evenFibonacci

Similarilly fibonacci <$> [1 .. 32] is even shorter than your version. (I'll let you rewrite evenFibonacci on your own ;) )

Finally I advise you not to do so many variable declarations, declarations are fine when those variables can be standalones, but it isn't really the case of your evenFibonacci'. You really should either compose variables or use some where

Have fun!

\$\endgroup\$
  • \$\begingroup\$ Does Haskell not memoize implicitly? So for the first point the computation is actually only done once? \$\endgroup\$ – Dair Apr 22 '17 at 1:48
  • \$\begingroup\$ It doesn't. You need to tell Haskell what to memoize and how. So for instance f = heavyComputation 12 + heavyComputation 12 is twice as slow as f = a + a where a = heavyComputation 12. This is why the version I gave for fibonacci is faster, every answers are stored in memory (ie. In the list). (Although, ghc may or may not optimise things away) \$\endgroup\$ – snow_lemurian_snow Apr 22 '17 at 1:59
  • \$\begingroup\$ My bad, for some reason I though GHC optimized the stuff for implicit recusion, checked the docs. You are certainly correct. \$\endgroup\$ – Dair Apr 22 '17 at 2:01
2
\$\begingroup\$

Some room for improvement:

Fibonacci

This is more of a preference, but I find this style more readable. What do you think?

fibonacci n | n == 1 || n == 2 = n
            | n >= 3           = fibonacci (n - 1) + fibonacci (n - 2)
            | otherwise        = 0

Fibonacci List

-- Intermediate code: list of first 32 Fibonacci numbers
fibonacciList = [fibonacci i | i <- [1..32]]

I like what you are doing here, but I feel like you are doing too much work. It seems to me that what you actually wanted to do here is to generate a list numbers from 1 to 32, but you want to transform (map) those numbers from simple integers to corresponding Fibonacci number. Well I think you got my hint there, the function you are looking for is called map.

What does map do? Well let's first look at the signature for map

Prelude> :t map
map :: (a -> b) -> [a] -> [b]

What this says is that map takes a function going from a => b as it's first parameter, followed by a list of type a, then it returns a list of type b. This is exactly what you need. You already have a function that takes simple meager integers and transforms them into fibonacci numbers, and you have a list of integers, so all that is needed now is to call map with these inputs and have it do the work. So here goes

map fib [1..32]

A beauty!

Even Fibonacci

-- list of even Fibonacci numbers from fibonacciList
evenFibonacci = [eF | eF <- fibonacciList, eF `mod` 2 == 0]

Here we have another common haskell gem not being recognized for what it's worth. It looks like what you want to do here is to scrutinize a list and take only (filter) the even values from such a list. Again I left just there another hint. The Haskel gem you seek is called filter and here is the signature:

Prelude> :t filter
filter :: (a -> Bool) -> [a] -> [a]

How do we interpret this? Simple, filter is a function that takes a function which goes from a => Bool and a list of type a, then it returns another list of the same type.

How is this different from map? Notice that firstly the first parameter of map is a function that returns a generic type, however in the case of filter, the first parameter always returns Bool. Moreover, something that may not yet be obvious is that the length of the list returned by map is always equal to the length of the original list given to it, but this is not always true for filter.

Anyways, let us replace that function you have, with filter:

filter (\f -> f `mod` 2 == 0)

And now for the list to give to filter, we can reuse the original map solution to fix this

filter (\f -> f `mod` 2 == 0) $ map fib [1..32]

Shweet!

Even Fibonacci 2

The second evenFibonacci method you have is doing something else that is not immediately obvious. I think I understand what you wanted to do there being that you want to take only the first fibonacci numbers whose value does not exceed 4,000,000. However, you are still using what I would still consider a filter. The problem with your filter currently is that it does not ever stop filtering, so even if your fibonacci numbers are larger than 4,000,000, the filter will continue to filter but everything will return false. Lucky for you, haskell is lazy in that you can pretty much stop-the-world if things get too out of hand so you never get to see the effect of this, however imagine if you had an infinite list and needed this computation to stop once the values get large.

Ok let me introduce takeWhile, with the signature:

Prelude> :t takeWhile
takeWhile :: (a -> Bool) -> [a] -> [a]

I know it looks a lot like filter, but the distinction is in the name (if you are an English speaker) or the use once you read the documentation. takeWhile differs from filter in that once the function (first arguement) returns false, takeWhile quits. This is exactly what you need here to ensure that once the numbers start getting larger than 4,000,000 your function does not continue to evaluate more values.

So let's implement this:

takeWhile (< 4000000)

Combining with the previous 2, we have,

filter (\f -> f `mod` 2 == 0) $ takeWhile (< 4000000) $ map fib [1..32]

Main

Yea, I skipped sumEvenFibonacci because that one is ok..for now. What is wrong with main? Well nothing really except that it is too short. There is no build up, no suspense, nothing!.

Let's change that.

main can actually be changed to compose everything we already have. The goal of this program is to

  1. generate a list of fibonacci numbers
  2. take only the first few that do not exceed 4,000,000
  3. filter those ones to include only the even ones
  4. sum them all together
  5. and finally print the value.

So like I said, let us compose main to look just the way I described it. To compose functions in haskell, you have to make use of the . (composition function). So starting from the bottom, let's go:

main :: IO()
main = print . sum . filter (\f -> f `mod` 2 == 0) . takeWhile (< 4000000) . map fib $ [1..32]

And voila! Happy days.

I hope you took note of how our numbered list 1-5 was applied in reverse. This captures the essence of programming in purely functional languages like haskell vs something like C++. In procedural languages, if you say you want to do something, you start from step 1, and carry along to step End. The opposite is true in functional programming.

Cheers.

\$\endgroup\$
2
\$\begingroup\$

I see two ways of making your program faster. You can improve your haskell, and you can improve your algorithm.


If you calculate the first n Fibonacci numbers using your recursion, you end up calculating fib k n-k times. To avoid this, you can use memoization. In haskell, one of the easiest ways to do that is to use laziness. Rewrite fibonacci like so.

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

Now fibs is the list of Fibonacci numbers. Where the nth number will only be calculated if there's demand for it.


Look at the first few term terms of this list. You can notice a pattern: an even number followed by two odd numbers, followed by one even number, etc.

So it's enough to add up every third Fibonacci not greater than 4000000. Using laziness, you can do this neatly like so.

sum . takeWhile (<= 4000000) . map head . iterate (drop 3) $ fibs

If you specify that you want to use Ints, then the program will be faster. This is because by default Haskell would use Integers, which can hold very large numbers, but as a trade-off they are slower to operate on.


Implementing these two things, the result is the following.

fibs :: [Int]
fibs = 0:1:zipWith (+) fibs (tail fibs)

main :: IO ()
main = print . sum
             . takeWhile (<= 4000000)
             . map head
             . iterate (drop 3) $ fibs

Of course you can still make this faster with a better algorithm.

\$\endgroup\$
  • \$\begingroup\$ iterate fib and map fib [1..] do very different things. Also, iterate fib $ 0 won't return more than 0 and the loop forever. \$\endgroup\$ – Zeta Apr 22 '17 at 6:53
  • \$\begingroup\$ Naturally that's what I mean to write. The funny thing is that there was an edit suggested to replace iterate fib $0 with map fib [0..], which was rejected, because "it clearly went against the author's intents". Yeah, I surely meant to write a list of infinite zeros... I can only laugh at these kind of things. \$\endgroup\$ – Andrew Apr 22 '17 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.