[Haskell-cafe] Recursion in Haskell

[Donald Bruce Stewart]

prstanley:
> Hi
> I understand the basic principle of recursion but have difficulty 
> with the following:
> -- a recursive function
> -- for calculating the length of lists

> myLen [] = 0
> myLen (x:xs) = 1 + myLen xs

So this is a definition for the 'length' function on lists.

The list data structure is defined as:

    data [a]   = []   |   a : [a]

Some specific lists:

    Prelude> []
    []
    Prelude> 1 : []
    [1]
    Prelude> 1 : 2 : []
    [1,2]

Now, functions can "pattern match" on their arguments, to access the
fields inside the data structure. Pattern matching lets you take apart
data structures.

For example, we can implement the head and tail functions on lists as:

    head []     = error "empty list"
    head (x:xs) = x

    tail []     = error "empty list"
    tail (x:xs) = xs

Note how we write a case for both variants of the list data type, one
case for the empty list, and one case for the cons node.

Now, we are in a position to write the length function on lists:

Either, a list is empty, in which case its length is 0:

    length []  = 0

or, the inductive case, it contains at least one value, and the tail of a list.
Then the length is 1 + the length of the tail:

    length (x:xs) = 1 + length xs

And that's it. You can avoid naming variables in patterns that you don't
use, with the wildcard pattern:

    length (_:xs) = 1 + length xs

Cheers,  
    Don