Today I've found myself reading again the excellent paper Why Functional Programming Matters, where the author describes the core activity of programming in a functional fashion in terms of "glueing functions together".
It's been a while since I last played around with F#. So I decided this would be a good time to refresh some of the core concepts by translating some of the examples from his paper into F#.
The paper starts off describing how a
reduce function could be devised, extrapolating a common behavior from a certain set of functions. Let's first consider a function to sum all the items in a list:
let add a b = a + b let rec sum l = match l with |  -> 0 | h::t -> add h (sum t)
Nothing too fancy going on here. Let's now consider a similar function that instead multiplies together all the items in a list:
let mul a b = a * b let rec product l = match l with |  -> 1 | h::t -> mul h (product t)
If you compare the structure of the two functions
product you can see that the two are very similar. The are only two differences between the two:
- The value being returned when an empty list is matched (0 vs 1).
- The function being applied between the head of the list and the application of the recursive function to the remaining of the list (
It's easy, then, to extrapolate a more general
reduce function, as follows:
let rec reduce f a l = match l with |  -> a | h::t -> f h ((reduce f a) t)
Let's consider all the pieces step by step:
reduceis a (recursive) function accepting a function
f, a value
aand a list
fis the function that we want to apply between two elements of the list (
mulin the two examples above)
ais the value that we want to return when
fis applied to the empty list (0 or 1 respectively), and
lis the actual list we want to operate on.
Let's try this new function in the interactive window:
> reduce;; val it : (('a -> 'b -> 'b) -> 'b -> 'a list -> 'b) > reduce add 0 [1;2;3];; val it : int = 6 > reduce mul 1 [1;2;3];; val it : int = 6
As you see, the compiler infers the types involved in
reduce as follows:
('a -> 'b -> b')is the description of f: a function that takes two arguments of type 'a and 'b and returns one item of type 'b (note that 'a and 'b may in some cases represent the same type, as with
'bis a parameter of the same type as the one returned by
'a listis a list of items the same type as the first argument of
'bis finally the return type of the whole reduction process
There's an interesting special case: when
'a list. That is, when
f has the following form: ('a -> a' list -> a' list). A function receiving an item and a list and returning another list. Can you think of any function like that? What about concatenating an item and a list?
let cons a l = a::l
Let's see how the F# interactive interprets the new function we've just created and an example of usage:
> cons;; val it : ('a -> 'a list -> 'a list) > cons 1 [2; 3];; val it : int list = [1; 2; 3] >
And we now consider
cons as our
f function, first parameter of the
reduce, we can write for example:
let append a b = reduce cons b a let copy l = reduce cons l 
append concatenates two lists and
copy simply replicates any given list:
> append;; val it : ('a list -> 'a list -> 'a list) > append [1;2] [3;4];; val it : int list = [1; 2; 3; 4] > copy;; val it : ('a list -> 'a list) > copy [1;2;3];; val it : int list = [1; 2; 3] >
In the following post we'll continue translating some more core functions from the "Why Functional Programming Matters" into F#. Stay tuned!