Problem 2: Fibonacci

13 10 2009

Find the sum of all even fibonacci numbers not greater than 4000000

The fibonacci series has a simple recursive definition, just like factorial

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

As before, the Clojure solution is a simple application

(defn euler-2 [n]
    (loop [a 0 b 1 acc 0]
		(< n b) acc
		(even? b) (recur b (+ a b) (+ acc b))
		:else (recur b (+ a b) acc))))

(euler-2 4000000)

This works, but this is not a very reusable solution. Having to rewrite the same function each time for a specific case is not something you should be doing.

Storing a list of fibonacci terms is a great way to encapsulate them. Assume we already have this list, then the same problem can be very simply solved.

(reduce + (take-while #(< % 4000000) fibonacci-list))

take-while is a variation of the take function, take takes the first n terms in a list.

(take 3 (range 100))
=>(0 1 2)

take-while takes a predicate function and a list and returns a list of successive terms satisfying the function

(take-while #(< % 5) (range 100))
=>(0 1 2 3 4)

See how much simpler that is to understand and read. The problem is that the fibonacci series in an infinite series. You could  create a really large list but its impossible to know just how big is big enough. Fortunately Clojure has built in support for lazy-sequences.

Lazy-sequences are infinite lists which only generate terms when required. Clojure has a set of functions which can be used to create lazy-sequences, functions like repeat, cycle and iterate all generate lazy sequences.

warning: Do not evaluate an infinite sequence at the REPL as this will result in an infinite loop.

repeat is used to create finite or infinite sequences of the same term

(repeat 5 "F")
=>("F" "F" "F" "F" "F")

(repeat "F")
=>("F" "F" "F" ...)

cycle takes a list as argument an returns an infinite sequence of the list repeated.

(cycle (range 5))
=>(0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 ...)

iterate takes a function and value and returns a lazy sequence of x, (f x) (f  (f x)) …

(iterate inc 0)
=>(0 1 2 3 4 5 ...)

where inc is the increment function

Now onto something a little more basic. In Clojure lists are evaluated, that is, the first term is taken as a function and is applied to the remaining terms in the list.

There are times when you just want a list of terms without evaluation. This is what the quote function is for.

(+ 1 2 3)

(quote (+ 1 2 3))
=>(+ 1 2 3)

quote can also be written as the symbol ‘ before the start of the list.

'(1 2 3)
=>(1 2 3)

The concat function concatenates  its arguments which are lists

(concat '(1 2 3) '(4 5 6))
=>(1 2 3 4 5 6)

lazy-cat can be used to concatenate infinite lists

(lazy-cat '(0 1) (iterate inc 2))
=>(0 1 2 3 4 ...)

One more feature of Clojure to go before we implement the lazy fibonacci sequence

In Clojure, a function can take a variable number of arguments and also dispatch differently on the number of arguments called, this is known as polymorphism

(defn add
    ([a b]
	(+ a b)))

(add 1)

(add 1 2)

add if called with 1 argument returns the argument itself and if called with 2 returns the sum of the 2 terms.

Now onto the infinite fibonacci

(defn create-fibonacci-list
	(create-fibonacci-list 0 1))
    ([a b]
	(lazy-cat (list a b) (create-fibonacci-list b (+ a b)))))
(def fibonacci-list

The list function takes an arbitrary number of terms and creates a list out of them

(list 1 2 3 4)
=>(1 2 3 4)
(take 10 fibonacci-list)
=>(0 1 1 2 3 5 8 13 21 34)



One response

17 10 2009
Problem 7: Primes « The Philosophy and the Craft

[…] The prime numbers are intriguing, there is no pattern and no direct formula for the nth term in the series of primes. While an nth term formula would be enough for this problem, it would be far more useful to have an infinite, lazy list of primes like the fibonacci list in my earlier post. […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: