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:
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
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'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:
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
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
first parameter of the
reduce, we can write for example:
append concatenates two lists and
simply replicates any given list: