[Haskell-beginners] Understanding recursion in Haskell.
Adrian Neumann
aneumann at inf.fu-berlin.de
Wed Mar 18 03:05:09 EDT 2009
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
More information about the Beginners
mailing list