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