[Haskell-cafe] Recursion in Haskell

[Matthew Brecknell]

P. R. Stanley:
> 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

Benjamin Franksen:
> 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

Looks more like a sum than a length. Benjamin really meant something
like this:

mylen = fold (const succ) 0

Note, the Prelude already contains various fold functions, so you don't
have to write your own. The one corresponding to fold is "foldr".
(Benjamin just wrote it out to demonstrate the practice of extracting
and naming reusable computational structures as higher-order functions).

Now, can you write head as a fold? Would you want to? What about tail?