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.

---

Thoughts

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.