Re: [Haskell-beginners] Understanding recursion in Haskell.

This function drops the first n elements from xs.

If n <= 0 || null xs then xs

if n is less than or equal to 0, we are done dropping the elements that we intended to drop. If xs is null, the list is empty and we have no more elements to drop. So, either way, we can just return xs and stop the recursion.

else myDrop (n - 1) (tail xs)

Otherwise, we drop the first element from xs and pass that to myDrop. Of course, when we call myDrop, we give n-1 instead of n because we dropped the first element from xs. I think it will be easier if we take an example. Let's say we want to evaluate myDrop 3 [1,2,3,4,5], expecting the output to be [4,5]. 3 is greater than 0 and [1,2,3,4,5] is not empty. So, it evaluates to myDrop (3 - 1) (tail [1,2,3,4,5]) 2 is greater than 0 and [2,3,4,5] is not empty So, it evaluates to myDrop (2 - 1) (tail [2,3,4,5]) 1 is greater than 0 and [3,4,5] is not empty So, it evaluates to myDrop (1 -1) (tail [3,4,5]) 0 is now equal to 0, so it evaluates to [4,5]. Sean On Wed, Mar 18, 2009 at 6:36 PM, 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)

Danke,

Caitlin

--- On Wed, 3/18/09, Adrian Neumann wrote:

From: Adrian Neumann Subject: Re: [Haskell-beginners] Understanding recursion in Haskell. To: beginners@haskell.org Date: Wednesday, March 18, 2009, 12:05 AM

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

-----Inline Attachment Follows-----

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Sean Lee PhD Student Programming Language and Systems Research Group School of Computer Science and Engineering University of New South Wales