home blog lisp (new!) favorites

An error in ML that caused me much grief

October 19, 2016

I am in a Programming Languages class (COMP 105 at Tufts, if you’re curious). We are in the middle of a problemset to learn ML. In that problemset, we had to write several functions that deal with trees:

datatype 'a tree = LEAF
                 | NODE of 'a tree * 'a * 'a tree 

One of those functions was treeFoldr. treeFoldr has the following type:

('a * 'b -> 'b) -> 'b -> 'a tree -> 'b

So I naturally implemented it like:

fun treeFoldr f acc LEAF = ...
  | treeFoldr f acc NODE(left, d, right) = ...

When compiled, though, I got two errors I did not understand. First off was stdIn:173.5-180.10 Error: clauses don't all have same number of patterns. But after close inspection… wait, they totally do. That’s a lie! Each took a function, an accumulator (initial value), and a 'a tree! So this flummoxed me. I decided to look at the next error.

stdIn:174.21-174.25 Error: data constructor NODE used without argument in pattern. Super helpful, right? Because to me it looked like NODE had three arguments. But SML/NJ, MosML, and MLton all said it did not.

And of course, neither of these was super Google-able. None of the search results that came up seemed relevant.

After much waffling around, it occurred to me that that argument needs parentheses! SML thought that I was giving treeFoldr four arguments – a function, an accumulator, a poorly-formed 'a tree constructor, and a tuple.

So I fixed it by adding parentheses. The final result looks like this:

fun treeFoldr f acc LEAF = ...
  | treeFoldr f acc (NODE(left, d, right)) = ...

and fixes both errors.

Hopefully this post turns up in search results and helps people in the future.