# Understanding recursion in Haskell.

 Classic List Threaded
3 messages
Reply | Threaded
Open this post in threaded view
|

## Understanding recursion in Haskell.

 Hi. As a Haskell beginner, I was wondering if someoneone could explain how the following programs function (pardon the pun)? maximum' :: (Ord a) => [a] -> a   maximum' [] = error "maximum of empty list"   maximum' [x] = x   maximum' (x:xs)       | x > maxTail = x       | otherwise = maxTail       where maxTail = maximum' xs take' :: (Num i, Ord i) => i -> [a] -> [a]   take' n _       | n <= 0   = []   take' _ []     = []   take' n (x:xs) = x : take' (n-1) xs zip' :: [a] -> [b] -> [(a,b)]   zip' _ [] = []   zip' [] _ = []   zip' (x:xs) (y:ys) = (x,y):zip' xs ys quicksort :: (Ord a) => [a] -> [a]   quicksort [] = []   quicksort (x:xs) =       let smallerSorted = quicksort [a | a <- xs, a <= x]           biggerSorted = quicksort [a | a <- xs, a > x]       in  smallerSorted ++ [x] ++ biggerSorted Thanks, Caitlin
Reply | Threaded
Open this post in threaded view
|

## Understanding recursion in Haskell.

 Am 18.03.2009 um 06:28 schrieb Caitlin: > > Hi. > > As a Haskell beginner, I was wondering if someoneone could explain   > how the following programs function (pardon the pun)? > This function takes some type which has an ordering defined, i.e. you   can compare its elements to one another > maximum' :: (Ord a) => [a] -> a it doesn't work for an empty list > maximum' [] = error "maximum of empty list" the maximum of a one element list is the lone element. this is the   base case which will be eventually reached by the recursion > maximum' [x] = x should the list have more than one element > maximum' (x:xs) compare the first element to the maximum of the other elements. if   it's greater, it's the maximum >     | x > maxTail = x otherwise the maximum of the other elements is the maximum of the   whole list >     | otherwise = maxTail how to compute the maximum of the other elements? just use this   function again. after a while we will only have one element left and   reach the base case above. >     where maxTail = maximum' xs > > This function takes a number and a list of some type a > take' :: (Num i, Ord i) => i -> [a] -> [a] first, ignore the list and check whether n is <= 0. in this case   return an empty list. this is the base case, that's eventually   reached by the recursion > take' n _ >     | n <= 0   = [] otherwise, check if the list is empty. this is another base case. > take' _ []     = [] if neither n<=0 or the list empty, take the first element, x, and put   it on front of the prefix of length (n-1) of the other elements. use   take' again, to get that prefix. after a while either n is 0 or there   are no more elements in the list and we reach the  base case > take' n (x:xs) = x : take' (n-1) xs > > Take two lists > > zip' :: [a] -> [b] -> [(a,b)] if either one of them is empty, stop > zip' _ [] = [] > zip' [] _ = [] otherwise prepend a tuple, build from the two first elements to the   zipped list of the other elements. after a while one of the lists   should become empty and the base case is reached. > zip' (x:xs) (y:ys) = (x,y):zip' xs ys > > > > quicksort :: (Ord a) => [a] -> [a] empty list -> nothing to do > quicksort [] = [] > quicksort (x:xs) = otherwise take the first element of the list and use it to split the   list in two halves. one with all the elements that are smaller or   equal than x, the other one with all those that are bigger. now sort   them and put x in the middle. that should give us a sorted whole. how   to sort them? just use quicksort again! after some splitting the   lists will become empty and the recursion stops. >     let smallerSorted = quicksort [a | a <- xs, a <= x] >         biggerSorted = quicksort [a | a <- xs, a > x] >     in  smallerSorted ++ [x] ++ biggerSorted -------------- next part -------------- A non-text attachment was scrubbed... Name: PGP.sig Type: application/pgp-signature Size: 194 bytes Desc: Signierter Teil der Nachricht Url : http://www.haskell.org/pipermail/beginners/attachments/20090318/9f494f3f/PGP.bin
Reply | Threaded
Open this post in threaded view
|

## Re: Understanding recursion in Haskell.

 In reply to this post by Caitlin-2 Caitlin rocketmail.com> writes: > As a Haskell beginner, I was wondering if someoneone could explain how >the following programs function > >maximum' :: (Ord a) => [a] -> a   >maximum' [] = error "maximum of empty list"   >maximum' [x] = x   >maximum' (x:xs)   >    | x > maxTail = x   >    | otherwise = maxTail   >    where maxTail = maximum' xs I'm a beginner too.  Let's say you call: maximum' [1, 2, 4] First of all, a list like [1, 2, 4] is actually of the form 1:2:4:[]. So you are really calling: maximum' 1:2:4:[] That function call matches the pattern in this definition: maximum' (x:xs)       | x > maxTail = x       | otherwise = maxTail       where maxTail = maximum' xs Lining up the function call with the function definition: maximum' (x:xs) maximum'  1:2:4:[] gives x = 1 and xs = 2:4:[].  Then the first condition("guard") in the function definition is examined: | x > maxTail         = x Because x = 1, the guard is equivalent to: | 1 > maxTail         = 1 So is 1 greater than the value of maxTail?  What is the value of maxTail?   maxTail is defined here: maxTail = maximum' xs Hmmm...that is starting to get confusing.  At this point, I draw a diagram: maximum' 1:2:4:[]  | 1 > maxTail  = 1        [     ]--------> maximum' xs  | otherwise maxTail The blank([   ]) represents the value of maxTail. From above, you know that xs is 2:4:[], giving you: maximum' 1:2:4:[]  | 1 > maxTail  = 1        [     ]--------> maximum' 2:4:[]  | otherwise maxTail Ok, so to figure out the value of maxTail, you have to figure out the value of: maximum' 2:4:[].   That function call matches the pattern in this definition: maximum' (x:xs)       | x > maxTail = x       | otherwise = maxTail       where maxTail = maximum' xs Lining up the function call with the function definition: >maximum' (x:xs)  maximum'  2:4:[] gives x = 2 and xs = 4:[].  Then the first condition("guard") in the function definition is examined: maximum' (x:xs)     | x > maxTail = x     | otherwise = maxTail     where maxTail = maximum' xs So is 2 greater than the value of maxTail?  What is the value of maxTail?  Uh oh, here we go again.  maxTail is defined here: maxTail = maximum' xs and this time xs = 4:[].  Time to update the diagram: maximum' 1:2:4:[]  | 1 > maxTail  = 1        [     ]----------> maximum' 2:4:[]  | otherwise maxTail       | 2 > maxTail   = 2                                                      [     ]---------> maximum' 4:[]                            | otherwise maxTail Now comes the fun part.  What is maximum' 4:[]? That function call matches one of the other definitions for maximum', this one: maximum' [x] = x That definition is the same as: maximum' x:[] = x Lining up the function call with the definition: maximum' x:[] = x maximum' 4:[] Looking at the pattern in the function definition, you should be able to see that x = 4, and therefore maximum' 4:[] = 4. Substituting 4 into right hand side of the current diagram: maximum' 1:2:4:[]  | 1 > maxTail  = 1        [     ]----------> maximum' 2:4:[]  | otherwise maxTail       | 2 > maxTail   = 2                                                      [     ]------------> 4                            | otherwise maxTail Ah ha!  Now we have a value for one of the blanks:   maximum' 1:2:4:[]  | 1 > maxTail  = 1        [     ]----------> maximum' 2:4:[]  | otherwise maxTail       | 2 > maxTail   = 2                                                      [  4  ]                            | otherwise maxTail Remember that a blank represents the value of maxTail above it. Now you can answer the question: is 2 > 4?  That is false, so you look at the second guard condition: | otherwise maxTail That just returns the value of maxTail, which is 4.  That means the value of maximum' 2:4:[] is 4.  Updating the diagram: maximum' 1:2:4:[]  | 1 > maxTail  = 1        [     ]----------> 4  | otherwise maxTail                                                       Moving the 4 into the blank gives:     maximum' 1:2:4:[]  | 1 > maxTail  = 1        [  4  ]  | otherwise maxTail         That allows you to answer the question is 1 > 4.  That is false, so you look at the second guard condition: | otherwise maxTail which just returns maxTail, or 4.  That means the value of maximum' 1:2:4:[] is 4. Ta da. Try doing something similar with the other function definitions to see if you can figure them out.