Functional Language Pit Part I: Introduction and F#
Welcome to the Pit.
In this series I'll try and explore idiomatic functional language usages with C# 3.0, F#, Ruby (IronRuby), Python (IronPython), and Scheme. I will provide a short description for each snippet just to get motivated, and will close the series with performance and numerical stability analysis.
Test Subject
Like any good test, there has to be a good test subject. Now, while I could do a dull iteration / manipulation of a list of ice-cream flavors, I picked something a bit more interesting and practical: Newton-Lagrange interpolation.
Interpolation, in short, is taking partial data of something, and 'filling in the blanks' based on known context rules.
In elementary geometry, we all know that it takes 2 points in space to define a single unique line. But it also takes 3 points to define a single unique parabola -- a 2nd degree polynomial, 4 points for a 3rd degree polynomial, and so on.
The Newton-Lagrange method of interpolation will interpolate all of the missing data based on those rules, with ,of course, a certain error. In practice, Cubic Splines and Bezier curves (yea, thats the Pen tool in Photoshop), use forms of interpolation similar to that.
Theory
No, I'm not going to bore you with the math. Basically what needs to be done, is (preferably) compute a table of divided differences - here done with recursion, and use that with the Horner multiplication scheme.
F#
1 #light
2 open System
3
4 let NewtonLagrange (X, Y, px) =
5 let rec divdif s e =
6 match s, e with
7 | n1, n2 when n1 = n2 -> List.nth Y n1
8 | _, _ -> (divdif (s+1) e - divdif s (e-1) ) / (List.nth X e - List.nth X s)
9
10 let divdifs = List.map (divdif 0) [0 .. X.Length-1]
11 List.fold_right2 (fun a b acc -> acc*(px - a) + b) X divdifs 0.0
12
13
14
15 let X = [-5.0 .. 1.0 .. 5.0]
16 let Y = List.map (fun x -> 1.0 / (cos(2.0*x) + x**2.0)) X
17 NewtonLagrange(X, Y, 3.16)
let X = [-5.0 .. 1.0 .. 5.0]
Range: let X = [<start> .. <step> .. <end>]. Note, that in order to help F# do a good deal of inference, I like to state double values as 0.0 explicitly.
(fun x -> 1.0 / (cos(2.0*x) + x**2.0))
Lambdas: (fun <params> -> <body>), returns a function object. remember, functions are first-class citizens in functional langauges.
List.map (divdif 0) [0 .. X.Length-1]
Curried functions: This is a hyped, not that straight forward concept to grasp by the imperative programmer. A curried function is a function object, where we allow parameters to be partially specified. A curried function does not carry or curry anything, its name is a tribute to Haskell Curry. So, how could this be possible?
Imaging a function Add. Lets drop to a psuedo-F# syntax for a moment. So Add x y -> x+y, currying on it, we say AddFive = Add 5. AddFive now represent an add function that looks like: Add 5 y -> 5 + y. And thats all there is to it.
In line 10, we say: divdif 0. This goes and returns to map a divdif function where the parameter s is always zero.
List.fold_right2 (fun a b acc -> acc*(px - a) + b) X divdifs 0.0
List comprehensions: folding "folding" is just like "accumulating" or "injecting" or what ever idiom a language might use, to describe applying an operation to an item, and accumulating it, for every item on a list. As an example consider accumulating X = [ 1 1 1 1], which is folded into "4" by the "sum" function. Here we use a fold_right2, which starts from the end of the list, using 2 lists, which suits the Horner multiplication scheme perfectly.
let divdifs = List.map (divdif 0) [0 .. X.Length-1]
List comprehensions: map a map takes a list, applies a function to every item, and returns a 'deformed' list, that represents the same list with the function applied to every item.
An example would be taking a list X = [ 1 2 3 ] and squaring every element into [ 1 4 9 ].
Let rec, line 5,
a "let rec" is a binding operation, that will let you use the bound entity, inside its own body. In other words, its the way we do recursion here, and you'll also recognize that from Scheme, and other functional languages.
match s, e with
| decomposition1 when guard -> (handle case)
| decomposition2 -> (handle case)
Pattern matching: this feature would seem just like a sophisticated switch-statement, but its not, its a totally, completly, different concept. To grasp it fully, you might want to look at Prolog, or more practically, Erlang. In essence, a match block in F# can help you pick apart a matchable argument and do case-handling effectively, most preferably expressing recursion.
Paying a price: using List.nth is O(n)!. We can always use an Array and say myarray.(0), but I wanted to go pure functional anyway.
Next up: C#3.0 and Ruby.