Chris Eidhof chris at eidhof.nl
Sun Feb 18 02:47:42 EST 2007

```The definition of myLen says:

> myLen [] = 0
The length for an empty list is zero

> myLen (x:xs) = 1 + myLen xs
The length of a list containing x and some other stuff (xs) is 1 +
(the length of the other stuff).

So basically, if you've got a list [1,2,3], it will try to do this:

> myLen (1:[2,3]) = 1 + myLen [2,3]
The length of [1,2,3] is 1 + the length of [2,3]

> myLen (2:[3]) = 1 + myLen [3]
The length of [2,3] = 1 + the length of [3]

> myLen (3:[]) = 1 + myLen []
This is the tricky part, now the other case of myLen is being called:

> myLen [] = 0
Here you can see that it won't recurse anymore. Now there is going to
be some replacement:

> myLen (3:[])
can now be calculated, because "myLen []" is now known (0). Because
we know this,

> myLen (2:[3])
can now be calculated too, because we know that myLen [3] is 1. And
so on.

I think the trick here is to see that "[1]" is exactly the same as "1:
[]". Once you grasp this, the rest will probably easy.

Good luck!

-chris

On 17 Feb, 2007, at 19:32 , P. R. Stanley wrote:

> 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
> What's happening here?
> Top marks for a comprehensive jargon-free explanation.