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: can't build haskell-crypto (Daniel Fischer)
2. Tail recursion problem (Sebastian Arndt)
3. Re: Tail recursion problem (Daniel Fischer)
4. Re: can't build haskell-crypto (Mark Wright)
----------------------------------------------------------------------
Message: 1
Date: Sun, 20 Feb 2011 13:17:49 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] can't build haskell-crypto
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Saturday 19 February 2011 21:09:54, Chris Bolton wrote:
> http://paste.pocoo.org/show/341187/
>
> any ideas?
At some point in time (with QuickCheck-2.1.2), the Arbitrary instances for
Word8 and Word64 were included in Test.QuickCheck.Arbitrary. Probably
around the same time, they were removed from QuickTest.hs in the Crypto
package (because one can't have multiple instances for the same type).
Seems your QuickCheck is too old for the current Crypto.
You can install an older Crypto or a newer QuickCheck.
Getting the latest QuickCheck is probably the better way.
Cheers,
Daniel
------------------------------
Message: 2
Date: Sun, 20 Feb 2011 16:42:28 +0100
From: Sebastian Arndt <[email protected]>
Subject: [Haskell-beginners] Tail recursion problem
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-15"; Format="flowed"
Hi everyone,
i'm trying to understand tail recursion, but im stuck when it comes to
tail recursion with tuples. Look at the following source code:
module Main(main) where
main = do
putStrLn "tail recursion"
print $ countOdd2 [0..10000000]
{- Tail recursion doesnt work -}
countOdd :: [Int] -> (Int, Int)
countOdd lst = countOdd' lst (0,0)
countOdd' :: [Int] -> (Int, Int) -> (Int, Int)
countOdd' (x:xs) last = if odd x then
countOdd' xs $! (fst last, snd last
+ 1)
else
countOdd' xs $! (fst last + 1, snd
last)
countOdd' [] last = last
{- Working tail recursion -}
countOdd2 :: [Int] -> Int
countOdd2 lst = countOdd2' lst 0
countOdd2' :: [Int] -> Int -> Int
countOdd2' (x:xs) last = if odd x then
countOdd2' xs $! last + 1
else
countOdd2' xs last
countOdd2' [] last = last
The tail recursion in the function *countOdd2 *works fine. But it seems
not to work in *countOdd *because i get a*Stack space overflow *error.
Can anyone rewrite *countOdd *so that it works without a Stack space
overflow?
Thank you.
Cheers
Sebastian Arndt
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20110220/50c74ac3/attachment-0001.htm>
------------------------------
Message: 3
Date: Sun, 20 Feb 2011 17:20:33 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Tail recursion problem
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Sunday 20 February 2011 16:42:28, Sebastian Arndt wrote:
> Hi everyone,
>
> i'm trying to understand tail recursion, but im stuck when it comes to
> tail recursion with tuples. Look at the following source code:
>
> module Main(main) where
>
> main = do
> putStrLn "tail recursion"
> print $ countOdd2 [0..10000000]
>
> {- Tail recursion doesnt work -}
>
> countOdd :: [Int] -> (Int, Int)
> countOdd lst = countOdd' lst (0,0)
>
> countOdd' :: [Int] -> (Int, Int) -> (Int, Int)
> countOdd' (x:xs) last = if odd x then
> countOdd' xs $! (fst last, snd last
> + 1)
The ($!) doesn't evaluate anything here that isn't evaluated anyway.
x `seq' y
evaluates x to 'weak head normal form' when y must be evaluated.
Evaluating to WHNF means evaluating to the outermost constructor (or
lambda), in this case it means the pair
(fst last, snd last +1)
is evaluated only so far to determine that the outermost constructor is (,)
- which means the components remain completely unevaluated and your
function constructs a result of the form
(((...(0 + 1)...+ 1) + 1), ((...(0 + 1)...+ 1) + 1))
which obviously is't what you really want. What you want is the evaluation
of the pair's components, a simple and portable way would be
countOdd' (x:xs) (evenCount, oddCount) =
evenCount `seq` oddCount `seq` if odd x then ...
or, to avoid unnecessary seq'ing,
countOdd' (x:xs) (evenCount, oddCount)
| odd x = let oc = oddCount + 1 in oc `seq` countOdd' xs
(evenCount,oc)
| otherwise = let ec = evenCount + 1 in ec `seq` countOdd' xs
(ec,oddCount)
When using GHC, it's more convenient to write it using bang-patterns:
countOdd' (x:xs) (!ec, !oc)
| odd x = countOdd' xs (ec, oc+1)
| otherwise = countOdd' xs (ec+1,oc)
> else
> countOdd' xs $! (fst last + 1, snd
> last)
> countOdd' [] last = last
>
> {- Working tail recursion -}
>
> countOdd2 :: [Int] -> Int
> countOdd2 lst = countOdd2' lst 0
>
> countOdd2' :: [Int] -> Int -> Int
> countOdd2' (x:xs) last = if odd x then
> countOdd2' xs $! last + 1
> else
> countOdd2' xs last
> countOdd2' [] last = last
>
> The tail recursion in the function *countOdd2 *works fine.
You're evaluating an Int here to WHNF. For Ints, evaluation to WHNF is
complete evaluation.
> But it seems
> not to work in *countOdd *because i get a*Stack space overflow *error.
> Can anyone rewrite *countOdd *so that it works without a Stack space
> overflow?
>
> Thank you.
>
> Cheers
> Sebastian Arndt
------------------------------
Message: 4
Date: Sun, 20 Feb 2011 20:41:14 +1100
From: Mark Wright <[email protected]>
Subject: Re: [Haskell-beginners] can't build haskell-crypto
To: Chris Bolton <[email protected]>, [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Hi Chris,
I'm sort of guessing that maybe you are trying to build
a old version of Crypto against a QuickCheck vesion 2.4
or later. There are incompatible API changes in
Quickcheck 2.4.
The latest Crypto:
http://hackage.haskell.org/package/Crypto-4.2.3
builds with Quickcheck 2.4.0.1
Regards, Mark
On Sat, 19 Feb 2011 12:09:54 -0800, Chris Bolton <[email protected]> wrote:
> http://paste.pocoo.org/show/341187/
>
> any ideas?
Non-text part: text/html
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 32, Issue 37
*****************************************
