Advent of Code 2019 - the 13 Days of Christmas

May 12, 2020

In the first article of this series, I prophesied that my initial enthusiasm for the project would soon burn out. Well, five months in, I’ve only solved 13 days of the advent of code. What can I say, I was right! To be fair, I’ve had a pretty full January and February, and, well, March and April haven’t been the best for just about everyone.

Anyway, I’m well and truly in the “glacial progress” phase of this little project. After a rather brutal start, I picked up enough OCaml to solve the first 10 problems or so. Now I’m fluent enough in the language to solve the new problems, but not fluent enough to solve them the way I would like.

This doesn’t provide enough incentive to learn more of the language, but it is sufficiently frustrating that working on new problems has turned into a chore. Hence, glacial progress.

So what OCaml look like now that I’ve learned enough to be competent (for Dunning-Kruger values of competence)?

Batteries not included

Coming from Python, the OCaml standard library feels austere, both in terms of features and expressiveness.

OCaml’s standard library is minimalist; you quickly need to reach for external libraries to carry out even fairly basic tasks. How basic? Well, here’s an apples-to-oranges (or in this case, camel-to-python) comparison: OCaml includes 70 modules in the core library, whereas Python has 240. You go a lot further with Python’s standard lib.

Then there’s the matter of OCaml’s sparseness compared to Python’s richer syntax. Obviously these things are subjective: one person’s expressiveness is another’s syntactic sugar. But for me Python strikes a nice balance between expressiveness and simplicity, and OCaml is decidedly on the “less is more” end of the scale. Here is what it takes to read a file using OCaml’s standard lib (as per the first answer in Stack Overflow):

let read_file filename =
  let lines = ref [] in
  let chan = open_in filename in
    try
      while true; do
        lines := input_line chan :: !lines
      done; !lines
    with End_of_file ->
      close_in chan;
      List.rev !lines

Compare this to Python’s with syntax:

def read_file(filename):
    with open(filename) as f:
        return [l for l in f]

You can also refer to last post’s example on how to print an int list if you want to flog this particular dead camel a bit more.

The immediate consequence is that even trivial tasks are fairly involved compared to Python’s “batteries included” model. This in turn means that it’s not practical to write OCaml without using a supplemental library to complete the standard lib. Unfortunately, there’s more than one of these, so you need to spend some brain budget choosing your standard lib.

I’ve so far resisted using any 3rd-party libraries, mostly because I don’t want to have to figure out how to import them. But that often means reinventing the wheel (well, copy-pasting the wheel from Stack Overflow to be honest). For what it’s worth, if I had to use one I’d probably go with Jane Street’s Core library.

Playing with matches

One of my impetus for trying OCaml was the match syntax. It feels very natural; in fact, I use it a lot in pseudo-code. Match plays well with variant types (another awesome feature) and it’s a natural fit for recursive functions.

Here is an almost-toy example of matching, from one of the first problems I solved.

let rec digits = function
  | 0 -> []
  | n -> (n mod 10) :: digits (n / 10)

This function turns a number into a list of digits. The match syntax | defines the two possible input cases:

either a 0, in which case we return an empty list;
or any other number, from which we extract the leading digit, recurse on the remainder of the number and concatenate the results.

OCaml’s interpreter does a splendid job detecting unmatched cases. This is one of the (rare) cases when the error messages are informative and useful. Consider the code below:

(* equivalent to List.map List.tl but ignores empty lists and empty tails *)
let rec map_tl = function
  | []           -> []
  | []::xs
  | (_::[])::xs  -> map_tl xs
  | (_::xs)::xss -> xs :: map_tl xss

As the comment states, this method applies the tail function to all items of a list of list, skipping empty lists and singletons. How can we be sure that the match cases are exhaustive? Well, here’s what the interpreter tells me if I remove the second match ([]::xs, which handles empty lists):

Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
[]::_

A clear warning with a useful example to troubleshoot the problem. Ah, OCaml, if only all your error messages were as clear…

I like match so much that I often find myself rearranging arguments to write functions as a big match case on the last argument.

Making a hash of dictionaries

Maps are essential data structures. Python dictionaries in particular are the language’s workhorse. So it’s natural to reach for OCaml’s version, or in this case, versions: association lists, hash tables and maps all serve similar needs. So which should you use? ¯\_(ツ)_/¯

According to the official OCaml tutorial, you should use Maps; it’s the first entry under “Data structures” and it’s even explicitly labeled “(Dictionaries)”. Maps are the hip, immutable, FP version of a dictionary. Map is a “functor”! How cool does this sound?

Well, as you can guess, maps sound too impressive to do any actual useful work. Hash tables are probably what you want 90% of the time. They’re the working man’s dict: mutable, easy to set up and with better performance in most use cases. I wish OCaml had taken the mutable concept all the way and added direct element access and modification to hash tables. Something like the array syntax (tbl.(key) and tbl.(key) <- new_val) would be nice. And, of course, not pimping Map when what any normal programmer wants is a Hashtbl.

Put that in your pipe!

A perennial OCaml newbie question: why is there no function composition?

Combining functions and using the resulting function, e.g. in a List.map, is a very common pattern. We are, after all, talking about functional programming. And yet there’s no elegant way to do it in OCaml.

Here’s a simple example to illustrate my point. Imagine you have an int list and you want to print it, one element per line. Since OCaml doesn’t have a method to print an int and a newline (ignoring Printf.printf for this example) , you need to combine print_endline and string_of_int. You would conceivably write this as:

let _ = List.map (print_newline . string_of_int) l

Where . (or whatever syntax) would denote function composition. But there’s no such operator in OCaml. You have to explicitly define the combined function like so:

(* note that in the first line, the parentheses and the explicit argument are mandatory *)
let composed x = print_newline (string_of_int x)
let _ = List.map composed l

I don’t know about you, but I find this disappointing.

However, there’s a nifty pipe operator, |> , which alleviates some of the pain as long as you’re willing to reorganize the order of your functions. |> takes the output of the left-side operation and passes it as the input to its right-side argument. Here it is in action:

let max, spot = "day10.dat" 
  |> read_lines
  |> points_from_input
  |> count_all_visibles
  |> max_of_list

This code takes the string "day10.dat", passes it to read_lines, then passes the result of that operation to points_from_input, and so on until the last function max_of_list.

This is much more readable than the “normal” way of chaining these functions:

(* so many parentheses... *)
let max, spot = max_of_list (count_all_visibles (points_from_input (read_lines "day10.dat")))

I admit that at first I had a hangup about the pipe operator; passing the data from one function to another felt less “functional” than composing functions together. Now that I’ve gotten used to it, I can’t live without it.

Will that be all?

I have run out of puns for section titles, so I’ll stop here for today. Anyway, this blog post has been much too long in the writing and it’s past time I published it, incomplete as it is. I have a theory about my inability to make progress on this little adventure, which I’ve dubbed “the hype cycle of side project”. Stay tuned for more details in the next post.

Programming