Necessary and Sufficient

This puzzle requires that we find the first Fibonacci number with 1000 digits.

Given what we have already created in problem 2 it is a fairly simple problem to solve. All we need to do is to introduce a new function that checks the digit count:

Note that I'm being explicit about the type of the parameter because I want it to use BigIntegers.

Now the problem is solved by filtering out all elements in the infinite list that don't have 1000 digits and with the resulting sequence taking the first element (Seq.head) and then bailing out.

This problem requires that we calculate the sum of the all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Using F# this is a fairly simple problem to solve. We need 3 things:

• A function that generates Fibonacci numbers
• A function that determines if a number is even
• A function that determines if a number is less than another number

Clearly the last 2 parts of this are fairly trivial. You could use anonymous functions (lambdas) but since I suspect I'll need these functions again in future I've defined them as named functions in their own right. In F#, the code for these 2 functions looks like this:

Now for the Fibonacci number generator. From the definition of Fibonacci numbers it is fairly easy to come up with a recursive function as follows:

Or if you prefer pattern matching syntax that better deals with boundary conditions, something like this might look better:

However, both of these functions suffer from performance problems because they repeatedly calculate the same Fibonacci numbers. The answer to this problem is, of course, memoization. Adding this the code would like a little better:

but there is also another issue to consider. We do not know how many numbers we will need. In this situation it's best to use a sequence rather than a finite list. A sequence is a logical series of elements all of one type. Individual sequence elements are computed only as required (lazy evaluation), so a sequence can provide performance improvements compared to a list in situations where not all the elements are used, and a sequence can produce an infinite list.

Here, Seq.unfold generates a sequence from a computation function that takes a state and transforms it to produce each subsequent element in the sequence. Because each element in the Fibonacci sequence is the sum of the previous two Fibonacci numbers, the state value is a tuple that consists of the previous two numbers in the sequence. The initial value is (1,1), the first two numbers in the sequence. The I suffix is used to denote a BigInteger type.

We can now compose all these functions to solve the problem. We simply iterate over the sequence (infinite list) until we reach our termination criteria (the Fibonacci number exceeds 4 million), summing the numbers as we go.

One final note...there is a closed-form solution to calculating the n-th Fibonacci number.

If you don't want a recursive formula you can use this approach.

QED.

A while ago I reviewed basic sorting algorithms in Java and C#. I've been playing a lot with F# over the past 6 months so I'd thought it would be worthwhile whipping up the same algorithms in F#.

The earlier posts with Java and C# implementations are here:
Sorting Fundamentals: Part 1
Sorting Fundamentals: Part 2

Bubble Sort

Everyone knows this is an inefficient algorithm but none-the-less it has "educational value". In my F# implementation I've defined 2 recursive functions, sink and outer. Both functions accept a list and return a new list. The sink function makes a single pass through the list sinking the largest value to the rightmost/last position in the list using simple pattern matching semantics. In lines 7-8 the cons operator (::) is used to separate the first 2 items in the list from the remainder of the list so a greater than pairwise comparison can be make on the leading pair. Note that lists, and indeed all identifiers not explicitly marked as mutable, are immutable so a new list is created rather than returning the original list. In other words, it is not in-place.

The second function, outer, is logically equivalent to the outer loop in the C#/Java implementation that you've no doubt seen before. We pass a list and the list size to this function. The function sinks one value using the function described above, then calls itself recursively on a new list that is a copy of the original list but has one fewer items - the "sunken" element is removed from the end.

Insertion Sort

The insertion sort algorithm works by inserting each item into an already sorted sub-list. In F# I've implemented it using 2 recursive functions, insert and insertionSort. Both functions take a list and return a new list. The insert function takes an item and a list and creates a new list which is a copy of the one passed but it inserts the passed item into the new list. This function is designed to take a sorted list or an empty list - which then becomes a sorted list.

The insertionSort function picks off the first item in the list and inserts it into the already-sorted sublist .

QuickSort

The quicksort algorithm is a classic divide-and-conquer algorithm. It selects a pivot from the list then creates 2 sub-lists containing all items less than, and greater than the pivot. The result is a new list which is the concatenation of the less-than list, the pivot, and the greater-than list. And, in order to sort the 2 sub-lists it calls itself recursively.

#light

open System

let rec quickSort ls =

  match ls with

  | [] -> []

  | p::r -> 

     quickSort [for i in r do if (compare i p) <= 0 then yield i] 

     @ [p] 

     @ quickSort [for i in r do if (compare i p) > 0 then yield i]          

let mylist = [3;5;1;2;2;78;9;8;43;5;-6]

let mylistsorted = (quickSort mylist)

print_any mylistsorted

Console.ReadLine() |> ignore

MergeSort

Of all the sort algorithms, quicksort is perhaps the most amenable to functional programming as it can exploit parallelization. If I had 10 billion records in numerous files over many machines a modified version of mergeSort is what you'd want top use, but that's a topic for another post...

As you can see, F# code is succinct and highly expressive. I liken it to Python in it's terseness without the performance penalty! The beauty of F# is a lightweight syntax where whitespace is used instead of block- and scope-defining curly braces, and the clever use of type inference within a strongly-typed type system, so I needn't get bogged down defining explicit types which makes the code's purpose clearer.