Fibonacci and Factorial

The next example is the Fibonacci series.  I had a feeling this would appear sooner or later.  What, haven't we done the factorial function yet?  I've been writing software on and off for thirty odd years and, incredibly, seem to have go this far without ever needing a Fibonacci number. Or a factorial function.

Anyway the trick with the Fibonacci series - and I remember this from Halloway's book - is to generate the numbers in pairs, so each element contains enough information go make the next one - so if one element is [a b], the next one is [b (+ a b)].  Your vector pair is a two number wide window into the Finonacci sequence, which flows through your windows from right to left.  Start with [0 1] and iterate this transformation and behold:


user=>(take 20 (iterate (fn [[a b]] [b (+ a b)]) [0 1]))
([0 1] [1 1] [1 2] [2 3] [3 5] [5 8] [8 13] [13 21] [21 34] [34 55] [55 89] [89
144] [144 233] [233 377] [377 610] [610 987] [987 1597] [1597 2584] [2584 4181]
[4181 6765])


We want only the second number from each pair to solve the puzzle, so we  map second:


#(map second
  (take %
    (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
 


Clojure helps us to keep this concise.  It you pass a vector such as [0 1] to a function with a parameter list like [x] then x is set to the value of the vector within the body of the function, and you would have to winkle out the values 0 and 1 explicitly:  however, if you change the parameter list to this [[a b]] then the vector is opened up when the function is called, and within the body of the function a will be 0 and b will be 1.  You can do the same trick with other data structures.

A Palidrome detector will obviously work by comparing an object with the reverse of the object - - but hang on, take the hint - - (reverse) returns a seq - therefore you have to compare the reverse of the object with the seq of the object, like this:


#(= (reverse %) (seq %))


To work out a Factorial looks like a gift: you reduce the list of numbers from 1 to x by multiplying them together - you get the sequence of numbers from 1 to x from the function range - so factorial % comes out as


#(reduce * (range 1 %))


Wrong.  Too confident.  In fact the function (range) does not include its upper limit - so the factorial needs to be:


#(reduce * (range 1 (inc %)))