[Haskell-cafe] Recursion in Haskell

[Chris Eidhof]

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.
> Thanks in advance
> Paul
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe