Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: How to display a time difference? (Colin Paul Adams)
2. Re: How to display a time difference? (Daniel Fischer)
3. Re: How to display a time difference? (Colin Paul Adams)
4. Re: folds again -- myCycle (Will Ness)
5. Re: folds again -- myCycle (Will Ness)
6. Re: Re: folds again -- myCycle (Daniel Fischer)
7. Re: Hudak state emulation discussion - can you give me some
idea? (Will Ness)
8. Re: folds again -- myCycle (Will Ness)
9. Re: Understanding recursion in Haskell. (Zachary Turner)
----------------------------------------------------------------------
Message: 1
Date: Wed, 18 Mar 2009 10:58:46 +0000
From: Colin Paul Adams <[email protected]>
Subject: Re: [Haskell-beginners] How to display a time difference?
To: Sean Lee <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>>>>> "Sean" == Sean Lee <[email protected]> writes:
Sean> You get some random values? or no change at all on the
Sean> state?
I'm not sure if the state has changed at all or not. Certainly it has
not changed correctly - the move does not get made.
As for Daniel's suggestion, I can't compile it because it says I need
an instance of NFData for Move.Move. I'm not sure what that involves.
Anyway, I don't think that evaluating move is necessarily the
solution. I need to force the entire evaluation of modifyIORef.
--
Colin Adams
Preston Lancashire
------------------------------
Message: 2
Date: Wed, 18 Mar 2009 12:00:56 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] How to display a time difference?
To: Sean Lee <[email protected]>, Colin Paul Adams
<[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Mittwoch, 18. März 2009 11:54 schrieb Sean Lee:
> You get some random values? or no change at all on the state?
>
> On Wed, Mar 18, 2009 at 9:45 PM, Colin Paul Adams
>
> <[email protected]> wrote:
> >>>>>> "Sean" == Sean Lee <[email protected]> writes:
> >
> > Sean> Hi Colin The following code probably would do what I wanted
> > Sean> to do.
> >
> > Sean> play_move :: IORef Game_state -> IO () play_move
> > Sean> game_state_ior = do (_, state, _) <- readIORef
> > Sean> game_state_ior putStr "Playing AI: " start_time <-
> > Sean> getCurrentTime let move = recommended_move state end_time <-
> > Sean> move `seq` (modifyIORef game_state_ior $!
> > Sean> update_interactive_from_move move) `seq` getCurrentTime
that should probably have been
move `seq` (modifyIORef game_state_ior $! ... ) >> getCurrentTime
value `seq` ioAction1 `seq` ioAction2
doesn't execute ioAction1.
> > Sean> putStrLn $ show $ (diffUTCTime end_time start_time)
> >
> > Sean> Due to the non-strictness of Haskell, the evaluation of the
> > Sean> expressions between start_time and end_time is deferred
> > Sean> until there is a need. By using `seq` and ($!), the
> > Sean> strictness can be forced.
> >
> > It certainly causes a time delay, and a non-zero time is printed, but
> > the state doesn't get modified correctly now.
> >
> > ??
> >
> > I will ponder Daniel's suggestion.
> > --
> > Colin Adams
> > Preston Lancashire
------------------------------
Message: 3
Date: Wed, 18 Mar 2009 11:07:28 +0000
From: Colin Paul Adams <[email protected]>
Subject: Re: [Haskell-beginners] How to display a time difference?
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
>>>>> "Daniel" == Daniel Fischer <[email protected]> writes:
Daniel> that should probably have been
Daniel> move `seq` (modifyIORef game_state_ior $! ... ) >>
Daniel> getCurrentTime
Daniel> value `seq` ioAction1 `seq` ioAction2
Daniel> doesn't execute ioAction1.
That did the trick!
Thanks everyone.
--
Colin Adams
Preston Lancashire
------------------------------
Message: 4
Date: Wed, 18 Mar 2009 11:19:29 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
>
> On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com> wrote:
> > which is then just rewritable as:
> >
> > myCycle xs = ys where ys = foldr (:) ys xs
> >
> > or (arriving at the same result)
> >
> > myCycle xs = foldr (:) (myCycle xs) xs
>
> Note that, because 'ys' only has to be calculated once, GHC makes the
> most efficient code for the former one. In the latter 'myCycle xs' has
> to be calculated each time 'xs' runs empty.
>
Actually my point was, that
" I find that "where" rewrites are easier to comprehend for me,
more often than not. :) "
" myCycle xs = ys where ys = foldr (:) ys xs "
which should be exactly as the one with the let.
------------------------------
Message: 5
Date: Wed, 18 Mar 2009 11:23:57 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
7stud <bbxx789_05ss <at> yahoo.com> writes:
>
> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> >
> >variant 2:
> >foldr rightAdd [] ones
> > ~> foldr rightAdd [] (1:ones)
> > ~> rightAdd 1 (foldr rightAdd [] ones)
> > ~> (foldr rightAdd [] ones) ++ xs
> >
> >and variant 2 [amounts] to:
> >myCycle2 xs = let ys = ys ++ xs in ys
> >
> >Ah, well. I again underestimated how much experience one
> >needs to see it immediately, sorry once more.
>
> >The right hand side of myCycle2's definition (if we specialise
> >xs to, say, [1,2,3])
>
> Ok, I see now. Using this definition:
>
> >myCycle2 xs = let ys = ys ++ xs in ys
>
> Then calling:
>
> myCycle2 [1, 2, 3]
>
> You get:
>
> let ys = ys ++ [1, 2, 3]
>
> But what is the value of ys on the right hand side?
> ...
> and then you need to substitute the value for ys
> again on the right hand side, and so on ad infinitum.
Exactly! That's what's called LEFT recursion: the 'ys' in the re-write
expression is ON THE LEFT SIDE of the expression, and so is immediately needed,
before the lazyness of list-access has a chance to kick in. Note that the
definition itself doesn't cause any infinite looping, only the actual list
access will do that.
I would recommend first to think about Haskell code in terms of rewritable
equivalence equations. Forget the supposed efficiency conserns, at first. Just
think of definitions as of equations you can use to rewrite your expressions,
in whichever order best suits you and assume the compiler will find the same
way of simplifying your expression; and realize that simplification is
triggered by _pattern_ _matching_ on _access_.
That is, until a value is needed at the top level, the definition is just a
definition, dormant and ready to be used, nothing more - regardless whether
it's implemented via thunks or not.
In our case, having
head (x:xs) = x
The access in (head ys) gets traslated in
head ys = head (ys ++ [1,2,3]) = head ((ys ++ [1,2,3]) ++ [1,2,3])
but for the other defintion
let zs = [1, 2, 3] ++ zs
it's
head zs = head([1, 2, 3] ++ zs) = head( (1:[2,3]) ++ zs)
= head( 1:([2,3]++zs) ) = 1
according to the defintion of (++),
(x:xs)++ys = x:(xs++ys)
Were we to use the foldr definition, it'll get rewritten just the same, using
the foldr definition (as long as it's not the left-recursive defintion):
foldr f z (a:as) = a `f` foldr f z as
let ws = foldr (:) [1,2,3] ws
head ws = head (foldr (:) [1,2,3] ws)
= head (foldr (:) [1,2,3] (foldr (:) [1,2,3] ws))
because 'ws' is getting matched against (a:as) pattern in foldr definition, so
is immediately needed, causing INFINITE looping. BUT
let qs = foldr (:) qs [1,2,3]
head qs = head( foldr (:) qs [1,2,3] ) = head( 1:foldr (:) qs [2,3]) = 1
So remember just these two rules:
1) the defintion is just a re-write equation, and
2) a value is forced by being pattern matched
- and you'll be fine.
------------------------------
Message: 6
Date: Wed, 18 Mar 2009 12:45:38 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Re: folds again -- myCycle
To: Will Ness <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Am Mittwoch, 18. März 2009 12:19 schrieb Will Ness:
> Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
> > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com>
wrote:
> > > which is then just rewritable as:
> > >
> > > myCycle xs = ys where ys = foldr (:) ys xs
> > >
> > > or (arriving at the same result)
> > >
> > > myCycle xs = foldr (:) (myCycle xs) xs
> >
> > Note that, because 'ys' only has to be calculated once, GHC makes the
> > most efficient code for the former one. In the latter 'myCycle xs' has
> > to be calculated each time 'xs' runs empty.
>
> Actually my point was, that
>
> " I find that "where" rewrites are easier to comprehend for me,
> more often than not. :) "
Of course a matter of personal preference, but I tend to prefer where clauses,
too, in general. However, my preferred layout is
some code
where
local declarations
I deeply loathe not having the where on a separate line :-/
>
> " myCycle xs = ys where ys = foldr (:) ys xs "
>
> which should be exactly as the one with the let.
>
AFAIK,
myCycle1 [] = []
myCycle1 xs = let ys = foldr (:) ys xs in ys
and
myCycle2 [] = []
myCycle2 xs = ys
where
ys = foldr (:) ys xs
are compiled to exactly the same code. In GHC, I think the first thing that
happens to myCycle2 is that it's rewritten to myCycle1.
What matters if whether you give a name to the result to get it shared or not.
------------------------------
Message: 7
Date: Wed, 18 Mar 2009 14:45:27 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: Hudak state emulation discussion -
can you give me some idea?
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Benjamin L. Russell <DekuDekuplex <at> Yahoo.com> writes:
>
> On Wed, 18 Mar 2009 13:02:34 +0530, Girish Bhat
> <girishbhat6620 <at> gmail.com> wrote:
>
> >>[...]
> >>
> >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
>
> So he did in fact explicitly state beforehand that he was defining
> those operators.
>
What he didn't do, is specify the precedences associativities of these
operators.
It seems that for the definitions to make sense, together with the code that
follows them in the article, the fixity declarations ought to be as e.g.
infixl 8 +'
infix 8 <'
infix 7 :=
infixl 6 ; -- infixr is good too
(p; q) s = q (p s) -- (;) = CB -- flip (.)
(x:=f) s = x s (f s) -- (:=) = S
goto f s = f s -- id = I
(f+'g) s = f s + g s
(f<'g) s = f s < g s
if' p c s = if (p s) then (c s) else s
x' (a,b) = a
i' (a,b) = b
so that ( x:=f ; i:=g ; x:=h )
would parse as ( ( (x:=f) ; (i:=g) ) ; (x:=h) ) , so that
( x:=f ; i:=g ; x:=h ) s = (x:=h) . (i:=g) . (x:=f) $ s
The types involved would be as follows. 's' denotes state; (_:=_) denote state
transformers of type (s -> s) (for them to be composable). 'x' and 'f' in
(x:=f) are
f :: s -> v -- value producer (including x' and i')
x :: s v -> s -- state updater (with the new value)
so that the combination (x:=f) s = x s (f s) has 'f' produce a new value
and 'x' update its supplied state with it:
(x:=f) s = s' where v = f s; s' = x s v
The whole combination as presented in the article actually defines a new
function to perform all these activities, and would be defined as
prog = x := const 1 ; i := const 0 ; loop
where loop = x := f ; i := i' +' const 1 ;
if' (i' <' const 10) (goto loop)
and used as
prog initState where initState = (0,0)
or something like that. Which is all very reminiscent of monad, a "programmable
semicolon".
Cheers,
------------------------------
Message: 8
Date: Wed, 18 Mar 2009 15:14:03 +0000 (UTC)
From: Will Ness <[email protected]>
Subject: [Haskell-beginners] Re: folds again -- myCycle
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
> Am Mittwoch, 18. März 2009 12:19 schrieb Will Ness:
> > Bas van Dijk <v.dijk.bas <at> gmail.com> writes:
> > > On Sun, Mar 15, 2009 at 7:35 PM, Will Ness <will_n48 <at> yahoo.com>
> wrote:
> > > >
> > > > myCycle xs = ys where ys = foldr (:) ys xs
> Of course a matter of personal preference, but I tend to prefer where
> clauses, too, in general. However, my preferred layout is
>
> some code
> where
> local declarations
>
> I deeply loathe not having the where on a separate line :-/
Will try not to offend in the future. :)
> AFAIK,
>
> [let and where versions of myCycle] are compiled to exactly the same code.
since there are no guards there with shared variables, I guess.
> What matters is whether you give a name to the result to get it shared or not.
I was hoping GHC is smarter than that in finding shared expressions. Is it
what's called deforestation?
Also, one can imagine this rewrite to be arrived at automagically by a compiler:
sum $ take m $ cycle [1..k]
| n > 0 = x*n+y
where
(n,r) = quotRem m k
x = sum [1..k]
y = sum [1..r]
Any human is certainly capable of seen this almost immediately, presented with
the big k's and huge m's. It's automagical. :)
Cheers,
------------------------------
Message: 9
Date: Wed, 18 Mar 2009 10:32:03 -0500
From: Zachary Turner <[email protected]>
Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
To: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
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, <[email protected]> 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 <[email protected]> wrote:
>
> From: Adrian Neumann <[email protected]>
> Subject: Re: [Haskell-beginners] Understanding recursion in Haskell.
> To: [email protected]
> 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
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> 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.htm
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 21
****************************************
