Why Functional Programming Matters in F#

Building Reduce and Map from the Ground Up with 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:

Nothing too fancy going on here. Let's now consider a similar function that instead multiplies together all the items in a list:

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'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:

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's see how the F# interactive interprets the new function we've just created and an example of usage:

And we now consider cons as our f function, first parameter of the reduce, we can write for example:

where append concatenates two lists and copy simply replicates any given list:

Updated: