The Problem : What is the first term in the Fibonacci sequence to contain 1000 digits?
The sweet solution :
#light
open System
let fib =
(1I,1I) |> Seq.unfold ( fun (sqEntry, acc) -> Some (acc, (acc, acc + sqEntry)) )
|> Seq.filter (fun x -> x.ToString().Length = 1000)
|> Seq.nth 0
print_any fib
Console.ReadLine()
ahh... such power and elegance....
Let me breakdown the solution
(1I,1I) |> Seq.unfold ( fun (sqEntry, acc) -> Some (acc, (acc, acc + sqEntry)) )
This line creates an inifinite list of fibonacci numbers using Seq.unfold. Let me say that again, it creates a in INFINITE list. How is that possible, you'd ask ? The reason is that F# performs Lazy Evaluation. By that, I mean the program will perform only the computation it needs to do. So in our case, the program will actually compute only the parts of the list that it will need. Here we used Seq.unfold to perform the computation. The unfold function creates a list and uses an accumulator to maintain the state between computations. The accumulator in this case is the tuple that contains the last 2 entries of the sequence
Seq.filter( fun x -> x.ToString().Length = 1000
This line applies the filter function to the sequence. This function returns a subset of the original list that matches the condition. In this case, the resulting list will contain only those numbers that is made up 1000 digits.
Seq.nth 0
This line retrieves the nth element in the sequence. Since the problem ask for the 1st term, naturally we retrieved the 0th element.
And finally the construct that ties everything together and makes the code such a wonder to look at is the
|> (the Pass-forward operator)
As its name implies, it passes forward the argument behind it to the function in front of it. So the solution in essence means
Pass the tuple (1I, 1I) to Seq.Unfold, then pass the resulting infinite list to Seq.filter, then pass the filtered list to Seq.nth which finally retrieves the 1st element!
Print | posted on Friday, January 18, 2008 5:24 PM