Andrew Bromage:
Pattern matching on the LHS of a function definitions looks, for all the world, like a set of rewrite rules. That's because, in some sense, they are.
In this definition:
f (x:xs) = 1 + f xs f [] = []
Intuitively, the first rule should only "fire" if the expression being evaluated conforms to the left-hand side.
But beware that even though they can be seen as rewrite rules, there is a difference in that a term rewrite system allows all possible orders of applying rewrite rules, whereas Haskell specifies a top-down order in which the rules are tried. This can make a difference if patterns overlap, so several patterns can match a given argument. In the given example the patterns do not overlap though, so this can indeed be seen as a little term rewriting system defining f. Björn Lisper