Tuesday, February 09, 2016

Practice Makes Perfect

In the previous few posts there’s been a lot of information, at least from my perspective. This knowledge alone won’t be enough to really get a feel for what it’s like to write code in F#, especially as most of the snippets you’ve seen have been adapted from the book I’ve been going through.

As such, I’ll be backing up what I’ve taken from the book by going through some exercises from the Programming Languages course run by the University of Washington. This is the same syllabus used on Coursera, and so all the lectures videos, notes and problems are free to access online.

The astute observer will note that the course uses ML, not F#. As it turns out this isn’t a huge problem — F# originated from ML and so whilst there are syntactic differences, the similarities prevail,

To get started, I went through the first week’s notes, watched the videos, and completed the exercises. I won’t list all of the solutions here (I’ve put them on GitHub along with a few ‘tests’ that I wrote). However, there were some things that cropped up again and again that I wanted to share.


The Power of Pattern Matching

I was true to the spirit of the exercises, which meant only using features that I had been exposed to in the preceding course notes. This essentially meant not using things like pattern matching, and definitely not using any loops, which left me slightly unsure of how to approach the first question.

So, I brute-forced it:

(* Question 1 : Write a function is_older that takes two dates and evaluates to true or false. It evaluates to true if the first argument is a date that comes before the second argument. (If the two dates are the same, the result is false.) *)

type Date = { Year : int; Month : int; Day : int }

let is_older (firstDate : Date) (secondDate : Date) =
  let compareInts x y = if x < y
                    then 1
                    else if y > x
                    then -1
                    else 0
  in
  if compareInts firstDate.Year secondDate.Year = 1 then true
  else if compareInts firstDate.Year secondDate.Year = -1 then false
  else if compareInts firstDate.Month secondDate.Month = 1 then true
  else if compareInts firstDate.Month secondDate.Month = -1 then false
  else if compareInts firstDate.Day secondDate.Day = 1 then true
  else false

Horrible, right? I’m sure there is a neater way to do it, but this one works…

The other quirk was that you can’t index into n-tuples in F# using the #foo notation in ML, and so I had to define a record type for Date, whereas I suspect the point of the course was to use a tuple of (int * int * int) and access the relevant bits using #1, #2 and #3.


Recursive by default

The next thing that struck, and really continued throughout the exercises, was the idea that the correct way to access the elements of a list was one by one, using recursion. For someone coming from the ‘mixed-mode’ world of the C# List<T> (which has both an array and a linked list to give the dual benefit of constant-time access and logarithmic-time copying), this took a while to get my head around.

In this case I do really mean a while, and I must have taken over half an hour to complete the second (trivial!) exercise:

(* Question 2: Write a function number_in_month that takes a list of dates and a month (i.e., an int) and returns how many dates in the list are in the given month. *)

let number_in_month (dates : Date list) (month : int) =
  let rec number_in_month_impl (dateList : Date list) =
    if List.isEmpty dateList then 0
    else let headIsInMonth = if (List.head dateList).Month = month then 1 else 0
         in headIsInMonth + number_in_month_impl (List.tail dateList)
  in number_in_month_impl dates

This fairly easy-to-understand question turns into a surprisingly nuanced answer (at least the way I did it!). I was surprised that:

  • It really is possible to take the first element of a list, do something with it, and then recurse on the remainder.
  • Despite this, we have to explicitly declare a binding with the rec keyword to signal to F# that we want to use recursion. To me this is extremely unnatural, and I forgot to write rec several times over the course of doing all the exercises. Does the language really need to be told that this thing is recursive? Surely it can infer the fact.
  • The most ‘natural’ pattern for me to implement the recursive part was with an inner routine. When I recursed the outer routine, I ended up with lots of calls to number_in_month dates_tail month, where the value of month didn’t change from iteration to iteration. A quick refactor made it easy to strip the recursive part down to the necessary bones — passing in a smaller list each time.

Once I’d bemoaned the lack of pattern matching and got my head around crafting recursive function, most of the rest of my solutions bore a similar hallmark to those shown. I particularly liked creating nested recursive functions to deal with cases when you need to iterate over two lists — rather than nested for loops in C#, we simple define an ‘inner’ function that recurses over the inner list and call it from an ‘outer’ function which recurses over the outer list. Simple, and much easier to test and reason about.


Suggestions please!

As a total novice to F#, I’m certain that these implementations are utterly horrible. If anyone is reading this and has ideas of how to improve the functions, please either leave me a comment or send me a tweet @malformedfawn! This goes for all of the solutions, not just those copied into this post :)

Next time I’ll finish writing up my thoughts on Chapter 5 of The Book of F#, and then probably do another round of these exercises.

3 comments:

  1. Hi Doug,

    Here are two (no pattern matching!) solutions:

    1) You've accidentally defined a Date type with structural comparison by default (like most F# types), so you can cheat and just write:

    let isOlder date1 date2 = date1 < date2
    (or even "let isOlder = (<)")

    2) I think the idiomatic answer is to use higher order functions not recursion:

    let numberInMonth month dates =
    dates |> List.sumBy (fun d -> if d.Month = month then 1 else 0)

    Re. the 'rec' keyword - the compiler is strictly top->bottom, left->right except in a very few key places. Without the rec keyword it would have to assume every function could be recursive, which would make it much more complicated and you'd lose nice things like error locality (red squiggly lines appear in the right place) and variable shadowing. Also, as I mentioned above, recursion is actually pretty rare in 'real' F# code so it's probably the right design trade off.


    -Paul

    ReplyDelete
  2. A couple of style things...

    * I really would go read the pattern matching chapter. Working with lists without it is horrible (as you've probably noticed!). Also you're missing out on the compiler's help to check all your matches are exhaustive which is a huge bug catcher.

    * With patterns you'll massively cut down your nested if-then blocks (they're a bit of a code smell).

    * See if you can make your recursive functions tail recursive. A tail recursive version of #2 might be:

    let numberInMonth month dates =
    ____rec loop count dates =
    ________match dates
    ________| [] -> count
    ________| head::tail ->
    ____________if head.Month = month then loop (count + 1) tail
    ____________else loop count tail
    ____loop 0 dates

    Tail recursive functions don't allocate extra stack frames. To see the difference try passing a million dates to each version.



    -Paul

    ReplyDelete
    Replies
    1. Thanks for the comments Paul - I'm just coming back to them now in the wake of having gone through sections on pattern matching and everything seems a lot clearer! For some reason I wasn't notified that the post had received comments, when I'm looking into now.

      I've one small question on patterns: would you typically use the 'when' condition of use an 'if then else', e.g

      match x with
      | (a,b) when a > b -> ...
      | (a,b) when a < b -> ...

      or

      match x with
      | (a,b) -> if a > b then ... else ...

      The course was quite good in the way that it 'revealed' certain features as it went along, so it made you think that your old code was terrible and that you've suddenly improved it (until you learn the next new thing)

      I'm currently writing the next blog with a definite slant towards tail recursion, so if you want time to read that then help with the Modulo Cons bits would be great!

      Doug

      Delete