On 18 Mar 2009, at 08:36, The_Polymorph at rocketmail.com wrote:
>
> Hi Adrian,
>
> Thanks for the explanations. Could we perhaps examine one recursive
> example in detail, i.e., step-by-step, as I'm still confused? Maybe
> the following program from chapter 2 of
> http://book.realworldhaskell.org?
>
> myDrop n xs = if n <= 0 || null xs
> then xs
> else myDrop (n - 1) (tail xs)
In this example, I'm gonna use the "~>" symbol to mean "reduces to",
that is, if you perform one more evaluation step, you get this. We're
going to try and evaluate myDrop 2 [1,2,3,4]
myDrop 2 [1,2,3,4]
{ Reduce myDrop 2 [1,2,3,4] to its right hand side as defined
above }
~> if 2 <= 0 || null [1,2,3,4] then [1,2,3,4] else myDrop (2-1) (tail
[1,2,3,4])
{ Reduce 2 <= 0 to False }
~> if False || null [1,2,3,4] then [1,2,3,4] else myDrop (2-1) (tail
[1,2,3,4])
{ Reduce null [1,2,3,4] to False
~> if False || False then [1,2,3,4] else myDrop (2-1) (tail [1,2,3,4])
{ Reduce False || False to False }
~> if False then [1,2,3,4] else myDrop (2-1) (tail [1,2,3,4])
{ Reduce the if expression to its else branch }}
~> myDrop (2-1) (tail [1,2,3,4])
{Reduce myDrop (2-1) (tail [1,2,3,4]) to its right hand side as
defined above }
~> if n <= 0 || null xs then xs else myDrop (n - 1) (tail xs) where n
= (2-1); xs = tail [1,2,3,4]
{ Reduce 2 - 1 to 1 }
~> if n <= 0 || null xs then xs else myDrop (n - 1) (tail xs) where n
= 1; xs = tail [1,2,3,4]
{ Reduce 1 <= 0 to False }
~> if False || null xs then xs else myDrop (n - 1) (tail xs) where n =
1; xs = tail [1,2,3,4]
{ Remove superfluous definition of n (there's only one use of it
now) }
~> if False || null xs then xs else myDrop (1 - 1) (tail xs) where xs
= tail [1,2,3,4]
{ Reduce tail [1,2,3,4] to [2,3,4] }
~> if False || null xs then xs else myDrop (1 - 1) (tail xs) where xs
= [2,3,4]
{ Reduce null [2,3,4] to False }
~> if False || False then xs else myDrop (1 - 1) (tail xs) where xs =
[2,3,4]
{ Reduce False || False to False }
~> if False then xs else myDrop (1 - 1) (tail xs) where xs = [2,3,4]
{ Reduce if expression to its else branch }
~> myDrop (1 - 1) (tail xs) where xs = [2,3,4]
{ Remove superfluous definition of xs as there's only one use of
it now }
~> myDrop (1 - 1) (tail [2,3,4])
{ Reduce myDrop (1 - 1) (tail [2,3,4]) to its right hand side as
defined above }
~> if n <= 0 || null xs then xs else myDrop (n - 1) (tail xs) where n
= (1 - 1); xs = tail [2,3,4]
{ Reduce 1 - 1 to 0 }
~> if n <= 0 || null xs then xs else myDrop (n - 1) (tail xs) where n
= 0; xs = tail [2,3,4]
{ Reduce 0 <= 0 to True }
~> if True || null xs then xs else myDrop (n - 1) (tail xs) where n =
0; xs = tail [2,3,4]
{ Remove superfluous definition of n, as its only used in one
place now }
~> if True || null xs then xs else myDrop (0 - 1) (tail xs) where xs =
tail [2,3,4]
{ Reduce True || anything to True }
~> if True then xs else myDrop (0 - 1) (tail xs) where xs = tail [2,3,4]
{ Reduce if expression to its then branch }
~> xs where xs = tail [2,3,4]
{ Remove superfluous definition of xs, as it only appears once }
~> tail [2,3,4]
{ Reduce tail [2,3,4] to [3,4] }
~> [3,4]
Hope that helps
Bob