Why Functional Programming Matters in F#

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#.

Reduce

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 sum and 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 (add vs mul)

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:

• reduce is a (recursive) function accepting a function f, a value a and a list l.
• f is the function that we want to apply between two elements of the list (sum or mul in the two examples above)
• a is the value that we want to return when f is applied to the empty list (0 or 1 respectively), and
• l is 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 add and mul).
• 'b is a parameter of the same type as the one returned by f.
• 'a listis a list of items the same type as the first argument of f.
• 'b is finally the return type of the whole reduction process

.

There's an interesting special case: when 'b is '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 [] 

where 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]
>