F#'n like a MLer

Dear reader, for those of you who have been following my tweets know
that I've been doing quite a bit of functional programming research
mainly in the ML family of functional languages, specifically Ocaml.

Greg Morriset

I've been learning a great deal about how to think and write like a functional programmer. So far the experience has been non-stop excitement and a lot of fun. In this post I want to take a break from the normal stuff related to how to do something in F# and share with you what I think is a more meaningful topic that I've recently learned from
Professor Greg Morrisett.
"How to Engineer a Function in ML"
It's worth noting that Greg has done an amazing job adapting this technique to ML from Matthias Felleisen who outlined this same technique in Scheme & Rackett which can be found in the classic book

How To Design Programs 

Even though the topic says ML I can tell you that it directly applies to F#. As I discover ML like techniques I quickly move from the top level (Ocaml REPL) to FSI to ensure that it works and makes sense.

The formula or recipe for how to engineer a function is actually not that difficult... "It's almost brainless"

Let's take an example from Greg's lecture to help illustrate this technique:

Given a list of pairs of integers, produce the list of products of the pairs.

e.g., Given [ (2,3); (4,7);(5,2) ] return [6;28;10]

The formula consists of the following 4 steps :

Note: In plain English write down the input data and the output data of the function. 

1) "Write down the types" or the function signature

This can be done a couple of ways in F# 

a)  let rec prods ( l : (int * int)  list ) = 

(*explicit - type after the : is the return type of the function*)

b) let rec prods ( l: (int * int) list ) : int list = 

2) "Examine the inputs of the function and start tearing them apart."
"Decompose the problem in to sub problems (usually by matching)"
From our example above how do we tear apart a list?
In general its the same two ways a list is constructed.
Empty List [ ] or Cons : : "So we get two patterns - which is automatic"

Note: pattern matches can nest which is what allows us 
to tear apart the tuple on the head : : tail pattern match

let rec prods ( l: (int * int) list ) : int list =
    match l with
    | [ ] ->
    | (x,y) : : tail ->

It's worth noting here that the above code is completely type directed.
Meaning - we can look at the types and know exactly how to write
the implementation of the function which is to satisfy the two cases.
We know that the return type is a list so that really narrows our
search space for what the possible code will be.
We can almost tell right away that one of these cases is going to involve
an empty list and the other a cons.

let rec prods ( l: (int * int) list ) : int list = 

    match l with

    | [ ] -> [ ]

    | (x,y) : : tail ->  ? 1 : : ? 2

Again, by looking at the types we're able to determine that we need integers to satisfy the return type.

So for the head we need a way to take the pair and produce an int. 

Likewise for the tail we need a way to produce an int list.

"We need something that can give us an int list - which is prods".

3) Reconstruct the types relative to the output or return type of the function.

let rec prods ( l: (int * int) list ) : int list = 

    match l with

    | [ ] -> [ ]

    | (x,y) : : tail ->  (x * y) : : prods tail

4) Finally, test the function to determine correctness. 

Note: Don't forget to test the empty list case. This is analogous to writing a failing test in TDD. 

That's it! I've found this technique to be very pragmatic. 

Greg put it perfectly when he said that "Looking at the types

and thinking in terms of types really narrows your search space

for what code you need to write, that power makes it easier

to write functions".

To all the F# and ML hakers out there...

-Develop with Passion