Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Understanding recursion in Haskell.
(the_polymo...@rocketmail.com)
2. Re: Understanding recursion in Haskell. (7stud)
3. Re: Understanding recursion in Haskell. (Sean Lee)
4. Re: Understanding recursion in Haskell. (Thomas Davie)
5. Re: Hudak state emulation discussion - can you give me some
idea? (Benjamin L.Russell)
6. How to display a time difference? (Colin Paul Adams)
----------------------------------------------------------------------
Message: 1
Date: Wed, 18 Mar 2009 00:36:57 -0700 (PDT)
From: the_polymo...@rocketmail.com
Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
To: beginners@haskell.org
Message-ID: <390551.23952...@web50807.mail.re2.yahoo.com>
Content-Type: text/plain; charset=iso-8859-1
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 <aneum...@inf.fu-berlin.de> wrote:
From: Adrian Neumann <aneum...@inf.fu-berlin.de>
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
------------------------------
Message: 2
Date: Wed, 18 Mar 2009 07:54:22 +0000 (UTC)
From: 7stud <bbxx789_0...@yahoo.com>
Subject: [Haskell-beginners] Re: Understanding recursion in Haskell.
To: beginners@haskell.org
Message-ID: <loom.20090318t073316-...@post.gmane.org>
Content-Type: text/plain; charset=us-ascii
Caitlin <The_Polymorph <at> 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.
------------------------------
Message: 3
Date: Wed, 18 Mar 2009 19:13:30 +1100
From: Sean Lee <sean....@gmail.com>
Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
To: beginners@haskell.org
Message-ID:
<856192540903180113r2fcddfebm1c8b370d6f056...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
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, <the_polymo...@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)
>
>
> Danke,
>
> Caitlin
>
>
> --- On Wed, 3/18/09, Adrian Neumann <aneum...@inf.fu-berlin.de> wrote:
>
> From: Adrian Neumann <aneum...@inf.fu-berlin.de>
> 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
------------------------------
Message: 4
Date: Wed, 18 Mar 2009 09:28:52 +0100
From: Thomas Davie <tom.da...@gmail.com>
Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
To: the_polymo...@rocketmail.com
Cc: beginners@haskell.org
Message-ID: <d1d5096a-4eda-4a9f-b81c-8f4ef147c...@gmail.com>
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
On 18 Mar 2009, at 08:36, the_polymo...@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
------------------------------
Message: 5
Date: Wed, 18 Mar 2009 18:59:40 +0900
From: Benjamin L.Russell <dekudekup...@yahoo.com>
Subject: [Haskell-beginners] Re: Hudak state emulation discussion -
can you give me some idea?
To: beginners@haskell.org
Message-ID: <m6h1s459radd4h3tfggnbg5o1r76cmn...@4ax.com>
Content-Type: text/plain; charset=us-ascii
On Wed, 18 Mar 2009 13:02:34 +0530, Girish Bhat
<girishbhat6...@gmail.com> wrote:
>>[...]
>>
>> Hope this helps....
>>
>Thanks! It does. I think what threw me was that while there is enough
>redundancy in what he states for someone more clever than me, he would
>have explicitly stated before hand that he was defining the operators
>[:=], [+'], ['if] etc.:)
But he did; specifically, on pages 405 (the previous page) to 406 of
the volume, Hudak writes as follows:
>For expository purposes we would like to
>make the state as implicit as possible, and
>thus we express the result as a composition
>of higher-order functions. To facilitate this
>and to make the result look as much like
>the original program as possible, we define
>the following higher-order infix operators
>and functions(22):
So he did in fact explicitly state beforehand that he was defining
those operators.
-- Benjamin L. Russell
--
Benjamin L. Russell / DekuDekuplex at Yahoo dot com
http://dekudekuplex.wordpress.com/
Translator/Interpreter / Mobile: +011 81 80-3603-6725
"Furuike ya, kawazu tobikomu mizu no oto."
-- Matsuo Basho^
------------------------------
Message: 6
Date: Wed, 18 Mar 2009 10:06:30 +0000
From: Colin Paul Adams <co...@colina.demon.co.uk>
Subject: [Haskell-beginners] How to display a time difference?
To: beginners@haskell.org
Message-ID: <m37i2ntaah....@colina.demon.co.uk>
Content-Type: text/plain; charset=us-ascii
The code of the following routine is intended to indicate how long it
takes for the computer to make a move. However the time is printed (as
very close to zero) long before the move is made.
I must be missing something about sequencing actions in the IO monad.
play_move :: IORef Game_state -> IO ()
play_move game_state_ior = do
(_, state, _) <- readIORef game_state_ior
putStr "Playing AI: "
start_time <- getCurrentTime
let move = recommended_move state
modifyIORef game_state_ior (update_interactive_from_move move)
end_time <- getCurrentTime
putStrLn $ show $ (diffUTCTime end_time start_time)
--
Colin Adams
Preston Lancashire
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 19
****************************************
