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