Tuesday, February 16, 2016

Modulo Cons

We’re back with the second week of the Programming Languages course run by the University of Washington.

Once more, here are links to the notes, videos, and exercises. My solutions are on GitHub.

Pattern Matching and Recursion

Doing this exercises drilled home a couple of ideas that we’ve seen before: using pattern matching makes code so much neater, record types are great for defining lightweight pseudo-classes, and thinking recursively is hard when you aren’t used to it!

The contents of the notes and video are actually extremely useful and I could write a pretty long-winded piece on them alone, but here I want to focus on what I got out of trying the exercises.

Tail Recursion Modulo Cons

This gem of a concept cropped up in the very first question that I tried, which was:

Write a function all_except_option, which takes a string and a string list. Return NONE if the
string is not in the list, else return SOME lst where lst is identical to the argument list except the string
is not in it. You may assume the string is in the list at most once.

It came down to a case of two helper functions. For now, let’s forget that we can loop through the list once to do all the processing, and do it in two steps: first, find out whether the supplied string is in the list (i.e. the Any method that takes a predicate); then, if it’s found we remove the item from the list.

To match this logic I wrote two helper functions. The first was fairly easy to make tail recursive:

let found s ss = 
  let rec found_impl sl = 
    match sl with
    | [] -> false
    | h::t -> if h = s then true else found_impl t
  in found_impl ss

The second I found much harder, and ended up fruitless:

let remove_when_found s ss = 
  let rec remove_when_found_impl sl = 
    match sl with
    | [] -> []
    | h::t -> if h = s then t else h :: remove_when_found_impl t 
  in remove_when_found_impl ss

After some Googling, I realised that this second function was tail recursive modulo cons. After quite a lot more Googling, it seemed like the presented solutions on the blogosphere were less than transparent, so I left the function vulnerable to a Stack Overflow Exception.

It seemed like such a small change between the goals of the functions at first: recurse over the same list, check the same predicate, but the difference that returning a bool vs a List makes is significant.

I will return to this example when I understand the concept a lot better, and hopefully be able to write an elegant tail recursive solution.


My first foray into using pattern matching was good fun. I’m sure that I did plenty of things wrong and will improve both style and efficiency over time, but for now I am happy getting used to the new syntax and way of thinking.

Recursion is something that I have yet to quite grasp in my head — perhaps it is because one uses it so frequently in production code, but perhaps I just need to endeavour.

Next time, week three, promising First-Class functions and Closures.

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