Hacker News Reader

Comment by anonymouz | Hacker News Reader

In the section "Functional programming for real" he states:

> Note that the order of the definitions is important: had we moved our base case at the bottom, the recursion would never finish because map(F, [H|T]) would always match (remember? an empty list is also a list with a head and a tail).

Which confuses me a bit, since I am used to the empty list not having a head (I am thinking for example of Haskell). Is it true that in Erland the empty list has a head? And what would it be? Some generic null object?

View on HN

He is right in that order is important when pattern matching. However, his premise - an empty list has a head and a tail - is incorrect, so in this case order does not matter:

  > [H] = []. 
    ** exception error: no match of right hand side value []
  > [H|T] = [].
    ** exception error: no match of right hand side value []

But when it comes to pattern matching, order is important:

  > Test = fun(Value) -> Value ; (hello) -> world end.
  > Test(hello).
  hello

As opposed to:

  > Test2 = fun(hello) -> world ; (Value) -> Value end.
  > Test2(hello). 
  world

---

For the sake of completeness it's worth mentioning that a list with a single item has both a head and a tail:

  > [H|T] = [1]. 
  [1]
  > H. 
  1
  > T. 
  []

(Which is why you need to have a function head that matches [], whether first or last in his example.)

For readability, it's nice to have the base case at the top. For performance (if performance is an issue) it's nice to have the base case at the bottom since all function heads are evaluated in order.

If you're looping over a million element list and your base case is first, it'll be checked a million times. If your base case is last, it'll only be checked once when your normal cases no longer match.

And to clear up your confusion, the writeup is wrong about empty lists matching on [H|T]:

   Eshell V5.10.1  (abort with ^G)
   1> [H|T] = [1, 2, 3, 4, 5].
   [1,2,3,4,5]
   2> [H2|T2] = [].
   ** exception error: no match of right hand side value []

The BEAM virtual machine is able to reorder most clauses based on need, and for most cases, a binary search will be done through all clauses. Exceptions include function clauses with guards, which cannot easily be reordered but still impact whether a clause will be used or not.

The VM will instead try to reorder the clauses up until the next guard clause, if possible.

You should mostly care about writing readable code and let the compiler and the VM do the rest.

Yep, I was wrong (fixed the post).

The empty list does not have a head, neither a tail, it's just an empty list.

I've replaced it with another example. Thanks for all the feedback by the way.

No, he is wrong in this case. It would work fine. What he probably meant to show is that a list with a single item also has a tail. Meaning if you wanted to do:

map(F, [H]) -> [F(H)]; map(F, [H|T]) -> [F(H) | map(F, T)].

Order does matter

Reply on news.ycombinator.com