Understanding recursion in Haskell.

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Understanding recursion in Haskell.

Caitlin-2

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 <[hidden email]> wrote:

From: Adrian Neumann <[hidden email]>
Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
To: [hidden email]
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
[hidden email]
http://www.haskell.org/mailman/listinfo/beginners



     
Reply | Threaded
Open this post in threaded view
|

Understanding recursion in Haskell.

Sean Lee-4
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,  <[hidden email]> 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 <[hidden email]> wrote:
>
> From: Adrian Neumann <[hidden email]>
> Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
> To: [hidden email]
> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> 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
Reply | Threaded
Open this post in threaded view
|

Understanding recursion in Haskell.

Thomas Davie
In reply to this post by Caitlin-2

On 18 Mar 2009, at 08:36, [hidden email] 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
Reply | Threaded
Open this post in threaded view
|

Understanding recursion in Haskell.

Zachary Turner-2
In reply to this post by Caitlin-2
A few others have given more complete walkthroughs / traces of the
executions, but just to add a little.  When it finally "clicked" with me and
recursion became easier to understand, it was when I stopped trying to think
about the entire execution chain.  For example, let's say I run a ticket
resale (scalping) shop and someone calls me and says "hey I need two tickets
for the show this saturday."  I tell the guy sure no problem, I'll call you
back in 2 hours.  But actually I don't have the tickets, so I call one of my
connections.   Unfortunately, he doesn't have the tickets either so this
process ends up repeating for a while.  When I talk to my connection on the
phone I don't think "ok he's going to call John, and John's probably going
to call William, and then William might call Frank, etc".  I just think
"he's either going to call me back and say yes or no, regardless of how he
arrives at that answer".  That's the key to recursion.

In the case of finding the maximum element of a list, just imagine breaking
the list into two pieces.  The first piece is the first item in the list,
and the second piece is everything else.  If everything else is empty, then
the first piece is trivially the maximum, it only has one element.
Otherwise, compare the first element to the max of everything else.  Take
whichever one is bigger.  The entire chain of stuff that happens as a result
of "the max of everything else", isn't important.  The important thing is
that IF you have the first element, and IF you have the max of everything
else, then the max of the whole list is the greater of those two items.



On Wed, Mar 18, 2009 at 2:36 AM, <[hidden email]> 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 <[hidden email]> wrote:
>
> From: Adrian Neumann <[hidden email]>
> Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
> To: [hidden email]
> 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
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20090318/e64dcf02/attachment-0001.htm
Reply | Threaded
Open this post in threaded view
|

Understanding recursion in Haskell.

Thomas Davie

On 18 Mar 2009, at 16:32, Zachary Turner wrote:

> A few others have given more complete walkthroughs / traces of the  
> executions, but just to add a little.  When it finally "clicked"  
> with me and recursion became easier to understand, it was when I  
> stopped trying to think about the entire execution chain.  For  
> example, let's say I run a ticket resale (scalping) shop and someone  
> calls me and says "hey I need two tickets for the show this  
> saturday."  I tell the guy sure no problem, I'll call you back in 2  
> hours.  But actually I don't have the tickets, so I call one of my  
> connections.   Unfortunately, he doesn't have the tickets either so  
> this process ends up repeating for a while.  When I talk to my  
> connection on the phone I don't think "ok he's going to call John,  
> and John's probably going to call William, and then William might  
> call Frank, etc".  I just think "he's either going to call me back  
> and say yes or no, regardless of how he arrives at that answer".  
> That's the key to recursion.

This, and the fact that Frank does not call you looking for tickets  
(i.e. we must always make some progress).

Bob
Reply | Threaded
Open this post in threaded view
|

Re: Understanding recursion in Haskell.

Will Ness-2
In reply to this post by Zachary Turner-2
Zachary Turner <divisortheory <at> gmail.com> writes:

>  The entire chain of stuff that happens as a result of "the max of everything
else", isn't important.? The important thing is that IF you have the first
element, and IF you have the max of everything else, then the max of the whole
list is the greater of those two items.?


IOW, to add a bit to your vivid description, a key to understanding recursion
is learning to let go. It's zen, really. :)

It's learning to rely on the veracity of sub-results and just to combine them
in a proper correctness-preserving fashion. It's about design by contract, and
keeping invariants.