[Haskell-cafe] Re: Recursion in Haskell

[Benjamin Franksen]

P. R. Stanley wrote:
> Chaps,
> is there another general pattern for mylen, head or tail?
> mylen [] = 0
> mylen (x:xs) = 1 + mylen (xs)
> 
> head [] = error "what head?"
> head (x:xs) = x
> 
> tail [] = error "no tail"
> tail (x:xs)= xs

There are of course stylistic variations possible, e.g. you can use case
instead of pattern bindings:

mylen list = case list of
  []     -> 0
  (x:xs) -> 1 + mylen (xs)

As you see, this moves pattern matching from the lhs to the rhs of the
equation. Another very common 'pattern' is to factor the recursion into a
generic higher order function

fold op z []     = z
fold op z (x:xs) = x `op` (fold op z xs)
 -- parentheses not strictly necessary here, added for readability

and define mylen in terms of fold

mylen = fold (+) 0

You also have the possibility to use boolean guards as in

mylen xs
  | null xs   = 0
  | otherwise = 1 + mylen (tail xs)

(Although here we use the more primitive functions (null) and (tail) which
in turn would have to be defined using pattern matching. Pattern matching
is the only way to examine data of which nothing is known other than its
definition.)

Lastly, there are cases where you want to use nested patterns. For instance,
to eliminate successive duplicates you could write

elim_dups (x:x':xs) = if x == x' then xs' else x:xs'
  where xs' = elim_dups (x':xs)
elim_dups xs = xs

Here, the first clause matches any list with two or more elements; the
pattern binds the first element to the variable (x), the second one to
(x'), and the tail to (xs). The second clause matches everything else, i.e.
empty and one-element lists and acts as identity on them.

> This pattern matching reminds me of a module on formal spec I studied
> at college.

As long as your code doesn't (have to) use a tricky algorithm (typically if
the algorithm is more or less determined by the data structure, as in the
above examples) then it is really like an executable specification.

Cheers
Ben