On 18 Mar 2009, at 08:36, The_Polymorph@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