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. Stack space overflow: using strict accumulator still fails
(Hugo Ferreira)
2. Re: Stack space overflow: using strict accumulator still
fails (Daniel Fischer)
3. Re: Stack space overflow: using strict accumulator still
fails (Hugo Ferreira)
4. Re: Stack space overflow: using strict accumulator still
fails (Hugo Ferreira)
5. Re: Stack space overflow: using strict accumulator still
fails (Hugo Ferreira)
6. Re: Stack space overflow: using strict accumulator still
fails (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Thu, 27 Oct 2011 11:45:11 +0100
From: Hugo Ferreira <[email protected]>
Subject: [Haskell-beginners] Stack space overflow: using strict
accumulator still fails
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-15; format=flowed
Hello,
Have a stack overflow but cannot see why (read up on [1],
may be missing something trivial). Once again using the
http://nlpwp.org/ book code. If I call the following function,
it blows its top:
scoreRule :: TransformationRule -> Z.Zipper (Tag, Tag) -> Int
scoreRule r z = nCorrect - nIncorrect
where (nCorrect, nIncorrect) = scoreRule_ r z
scoreRule_ :: TransformationRule -> Z.Zipper (Tag, Tag) -> (Int, Int)
scoreRule_ r = Z.foldlz' (scoreElem r) (0, 0)
where scoreElem r s@(nCorrect, nIncorrect) z =
case ruleApplication r z of
Just tag -> if tag == correct then
(nCorrect + 1, nIncorrect)
else
(nCorrect, nIncorrect + 1)
Nothing -> s
where (correct, _) = Z.cursor z
however I see that the eager version of foldlz is being used.
I also though that maybe ruleApplication my not be executing
immediately. But I cannot see why (added definition below for
reference).
Can anyone point out why this is not strict?
TIA,
Hugo F.
[1] http://www.haskell.org/haskellwiki/Stack_overflow
ruleApplication :: TransformationRule -> Z.Zipper (Tag, Tag) -> Maybe Tag
ruleApplication (NextTagRule (Replacement old new) next) z = do
(_, proposed) <- Z.safeCursor z
(_, nextProposed) <- rightCursor z
if proposed == old && nextProposed == next then Just new else Nothing
ruleApplication (PrevTagRule (Replacement old new) prev) z = do
(_, proposed) <- Z.safeCursor z
(_, prevProposed) <- leftCursor z
if proposed == old && prevProposed == prev then Just new else Nothing
ruleApplication (SurroundTagRule (Replacement old new) prev next) z = do
(_, proposed) <- Z.safeCursor z
(_, nextProposed) <- rightCursor z
(_, prevProposed) <- leftCursor z
if proposed == old && prevProposed == prev &&
nextProposed == next then Just new else Nothing
------------------------------
Message: 2
Date: Thu, 27 Oct 2011 13:41:58 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Stack space overflow: using strict
accumulator still fails
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
On Thursday 27 October 2011, 12:45:11, Hugo Ferreira wrote:
> Hello,
>
> Have a stack overflow but cannot see why (read up on [1],
> may be missing something trivial). Once again using the
> http://nlpwp.org/ book code. If I call the following function,
> it blows its top:
>
> scoreRule :: TransformationRule -> Z.Zipper (Tag, Tag) -> Int
> scoreRule r z = nCorrect - nIncorrect
> where (nCorrect, nIncorrect) = scoreRule_ r z
>
> scoreRule_ :: TransformationRule -> Z.Zipper (Tag, Tag) -> (Int, Int)
> scoreRule_ r = Z.foldlz' (scoreElem r) (0, 0)
> where scoreElem r s@(nCorrect, nIncorrect) z =
> case ruleApplication r z of
> Just tag -> if tag == correct then
> (nCorrect + 1, nIncorrect)
> else
> (nCorrect, nIncorrect + 1)
> Nothing -> s
> where (correct, _) = Z.cursor z
>
> however I see that the eager version of foldlz is being used.
> I also though that maybe ruleApplication my not be executing
> immediately. But I cannot see why (added definition below for
> reference).
>
> Can anyone point out why this is not strict?
The additions (increments) are never forced before the final subtraction,
so from scoreRule_ you will probably get a pair of thunks
(((...(0+1)+1...)+1), ((...(0+1)+1...)+1)),
since the forcing in the fold can only use seq, to force *the outermost
constructor* of the intermediate results, in this case, the outermost
constructor is the pair constructor - (,) - and the components are left
unforced.
To force the increments without (big) delay, you can
- use a custom strict pair type instead of ordinary pairs
data P = P !Int !Int -- {-# UNPACK #-} the fields for extra goodness
so that forcing the outermost constructor automatically forces the
components.
- make the scoreElem function strict in the components of the accumulator
s, with ghc {-# LANGUAGE BangPatterns #-},
scoreElem r !s@(!nCorrect, !nIncorrect) z = ...
that way you will never get bigger thungks than (n+1) in the components
- force the updated count as it is constructed,
if tag == correct
then let newCorrect = nCorrect+1
in newCorrect `seq` (newCorrect, nIncorrect)
else let newIncorrect = ...
The important thing to be aware of is that seq only forces the outermost
level of a value. If the value is a structure with more levels, it doesn't
prevent the building of huge thunks in the inner levels at all.
You then have to take care of that yourself, by using a datatype with the
desired strictness or, in the case of folds and similar, providing a
comination function with the desired strictness.
HTH,
Daniel
------------------------------
Message: 3
Date: Thu, 27 Oct 2011 13:06:47 +0100
From: Hugo Ferreira <[email protected]>
Subject: Re: [Haskell-beginners] Stack space overflow: using strict
accumulator still fails
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Daniel,
Appreciate the comprehensive and clear explanation.
I see it has something to do with seq and weak head
normal form explanation in [1].
I will stick to the last solution.
Thanks,
Hugo F
On 10/27/2011 12:41 PM, Daniel Fischer wrote:
> On Thursday 27 October 2011, 12:45:11, Hugo Ferreira wrote:
>> Hello,
>>
>> Have a stack overflow but cannot see why (read up on [1],
>> may be missing something trivial). Once again using the
>> http://nlpwp.org/ book code. If I call the following function,
>> it blows its top:
>>
>> scoreRule :: TransformationRule -> Z.Zipper (Tag, Tag) -> Int
>> scoreRule r z = nCorrect - nIncorrect
>> where (nCorrect, nIncorrect) = scoreRule_ r z
>>
>> scoreRule_ :: TransformationRule -> Z.Zipper (Tag, Tag) -> (Int, Int)
>> scoreRule_ r = Z.foldlz' (scoreElem r) (0, 0)
>> where scoreElem r s@(nCorrect, nIncorrect) z =
>> case ruleApplication r z of
>> Just tag -> if tag == correct then
>> (nCorrect + 1, nIncorrect)
>> else
>> (nCorrect, nIncorrect + 1)
>> Nothing -> s
>> where (correct, _) = Z.cursor z
>>
>> however I see that the eager version of foldlz is being used.
>> I also though that maybe ruleApplication my not be executing
>> immediately. But I cannot see why (added definition below for
>> reference).
>>
>> Can anyone point out why this is not strict?
>
> The additions (increments) are never forced before the final subtraction,
> so from scoreRule_ you will probably get a pair of thunks
> (((...(0+1)+1...)+1), ((...(0+1)+1...)+1)),
> since the forcing in the fold can only use seq, to force *the outermost
> constructor* of the intermediate results, in this case, the outermost
> constructor is the pair constructor - (,) - and the components are left
> unforced.
>
> To force the increments without (big) delay, you can
> - use a custom strict pair type instead of ordinary pairs
>
> data P = P !Int !Int -- {-# UNPACK #-} the fields for extra goodness
>
> so that forcing the outermost constructor automatically forces the
> components.
>
> - make the scoreElem function strict in the components of the accumulator
> s, with ghc {-# LANGUAGE BangPatterns #-},
>
> scoreElem r !s@(!nCorrect, !nIncorrect) z = ...
>
> that way you will never get bigger thungks than (n+1) in the components
>
> - force the updated count as it is constructed,
>
> if tag == correct
> then let newCorrect = nCorrect+1
> in newCorrect `seq` (newCorrect, nIncorrect)
> else let newIncorrect = ...
>
>
> The important thing to be aware of is that seq only forces the outermost
> level of a value. If the value is a structure with more levels, it doesn't
> prevent the building of huge thunks in the inner levels at all.
> You then have to take care of that yourself, by using a datatype with the
> desired strictness or, in the case of folds and similar, providing a
> comination function with the desired strictness.
>
> HTH,
> Daniel
>
------------------------------
Message: 4
Date: Thu, 27 Oct 2011 14:22:26 +0100
From: Hugo Ferreira <[email protected]>
Subject: Re: [Haskell-beginners] Stack space overflow: using strict
accumulator still fails
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Hello,
After trying the suggestions, I still cannot execute
the code. I have tried:
scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
where scoreElem r !s@(!nCorrect, !nIncorrect) z =
case ruleApplication r z of
Just tag -> if tag == correct then
(nCorrect+1, nIncorrect)
else (nCorrect, nIncorrect + 1)
Nothing -> s
where (correct, _) = Z.cursor z
and
scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
nIncorrect)
where (correct, _) = Z.cursor z
nCorrect = nCorrect + 1
nIncorrect = nIncorrect + 1
where scoreElem r s@(nCorrect, nIncorrect) z =
case ruleApplication r z of
Just tag -> if tag == correct then
let nCorrect = nCorrect + 1 in
nCorrect `seq` nIncorrect `seq`
(nCorrect, nIncorrect)
else let nIncorrect = nIncorrect + 1 in
nCorrect `seq` nIncorrect `seq`
(nCorrect, nIncorrect)
Nothing -> s
where (correct, _) = Z.cursor z
In an attempt to figure out the problem I also tried:
scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
where scoreElem r !s@(!nCorrect, !nIncorrect) z = (nCorrect,
nIncorrect)
where (correct, _) = Z.cursor z
nCorrect = nCorrect + 1
nIncorrect = nIncorrect + 1
Strangely enough GHC complains that correct, nCorrect and nIncorrect
are not used. Why is this so for nCorrect and nIncorrect? Why won't the
above also execute in a strict manner?
Does anyone have any ideas why I still get stack-overflow?
TIA,
Hugo F.
On 10/27/2011 12:41 PM, Daniel Fischer wrote:
> On Thursday 27 October 2011, 12:45:11, Hugo Ferreira wrote:
>> Hello,
>>
>> Have a stack overflow but cannot see why (read up on [1],
>> may be missing something trivial). Once again using the
>> http://nlpwp.org/ book code. If I call the following function,
>> it blows its top:
>>
>> scoreRule :: TransformationRule -> Z.Zipper (Tag, Tag) -> Int
>> scoreRule r z = nCorrect - nIncorrect
>> where (nCorrect, nIncorrect) = scoreRule_ r z
>>
>> scoreRule_ :: TransformationRule -> Z.Zipper (Tag, Tag) -> (Int, Int)
>> scoreRule_ r = Z.foldlz' (scoreElem r) (0, 0)
>> where scoreElem r s@(nCorrect, nIncorrect) z =
>> case ruleApplication r z of
>> Just tag -> if tag == correct then
>> (nCorrect + 1, nIncorrect)
>> else
>> (nCorrect, nIncorrect + 1)
>> Nothing -> s
>> where (correct, _) = Z.cursor z
>>
>> however I see that the eager version of foldlz is being used.
>> I also though that maybe ruleApplication my not be executing
>> immediately. But I cannot see why (added definition below for
>> reference).
>>
>> Can anyone point out why this is not strict?
>
> The additions (increments) are never forced before the final subtraction,
> so from scoreRule_ you will probably get a pair of thunks
> (((...(0+1)+1...)+1), ((...(0+1)+1...)+1)),
> since the forcing in the fold can only use seq, to force *the outermost
> constructor* of the intermediate results, in this case, the outermost
> constructor is the pair constructor - (,) - and the components are left
> unforced.
>
> To force the increments without (big) delay, you can
> - use a custom strict pair type instead of ordinary pairs
>
> data P = P !Int !Int -- {-# UNPACK #-} the fields for extra goodness
>
> so that forcing the outermost constructor automatically forces the
> components.
>
> - make the scoreElem function strict in the components of the accumulator
> s, with ghc {-# LANGUAGE BangPatterns #-},
>
> scoreElem r !s@(!nCorrect, !nIncorrect) z = ...
>
> that way you will never get bigger thungks than (n+1) in the components
>
> - force the updated count as it is constructed,
>
> if tag == correct
> then let newCorrect = nCorrect+1
> in newCorrect `seq` (newCorrect, nIncorrect)
> else let newIncorrect = ...
>
>
> The important thing to be aware of is that seq only forces the outermost
> level of a value. If the value is a structure with more levels, it doesn't
> prevent the building of huge thunks in the inner levels at all.
> You then have to take care of that yourself, by using a datatype with the
> desired strictness or, in the case of folds and similar, providing a
> comination function with the desired strictness.
>
> HTH,
> Daniel
>
------------------------------
Message: 5
Date: Thu, 27 Oct 2011 14:44:34 +0100
From: Hugo Ferreira <[email protected]>
Subject: Re: [Haskell-beginners] Stack space overflow: using strict
accumulator still fails
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
My apologies, the 2nd function should be:
scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
where scoreElem r s@(nCorrect, nIncorrect) z =
case ruleApplication r z of
Just tag -> if tag == correct then
let nCorrect = nCorrect + 1 in
nCorrect `seq` nIncorrect `seq`
(nCorrect, nIncorrect)
else let nIncorrect = nIncorrect + 1 in
nCorrect `seq` nIncorrect `seq`
(nCorrect, nIncorrect)
Nothing -> s
where (correct, _) = Z.cursor z
R,
Hugo F.
On 10/27/2011 02:22 PM, Hugo Ferreira wrote:
> Hello,
>
> After trying the suggestions, I still cannot execute
> the code. I have tried:
>
> scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
> where scoreElem r !s@(!nCorrect, !nIncorrect) z =
> case ruleApplication r z of
> Just tag -> if tag == correct then
> (nCorrect+1, nIncorrect)
> else (nCorrect, nIncorrect + 1)
> Nothing -> s
> where (correct, _) = Z.cursor z
>
> and
>
> scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
> nIncorrect)
> where (correct, _) = Z.cursor z
> nCorrect = nCorrect + 1
> nIncorrect = nIncorrect + 1
> where scoreElem r s@(nCorrect, nIncorrect) z =
> case ruleApplication r z of
> Just tag -> if tag == correct then
> let nCorrect = nCorrect + 1 in
> nCorrect `seq` nIncorrect `seq` (nCorrect, nIncorrect)
> else let nIncorrect = nIncorrect + 1 in
> nCorrect `seq` nIncorrect `seq` (nCorrect, nIncorrect)
> Nothing -> s
> where (correct, _) = Z.cursor z
>
>
> In an attempt to figure out the problem I also tried:
>
> scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
> where scoreElem r !s@(!nCorrect, !nIncorrect) z = (nCorrect, nIncorrect)
> where (correct, _) = Z.cursor z
> nCorrect = nCorrect + 1
> nIncorrect = nIncorrect + 1
>
> Strangely enough GHC complains that correct, nCorrect and nIncorrect
> are not used. Why is this so for nCorrect and nIncorrect? Why won't the
> above also execute in a strict manner?
>
> Does anyone have any ideas why I still get stack-overflow?
>
> TIA,
> Hugo F.
>
>
>
> On 10/27/2011 12:41 PM, Daniel Fischer wrote:
>> On Thursday 27 October 2011, 12:45:11, Hugo Ferreira wrote:
>>> Hello,
>>>
>>> Have a stack overflow but cannot see why (read up on [1],
>>> may be missing something trivial). Once again using the
>>> http://nlpwp.org/ book code. If I call the following function,
>>> it blows its top:
>>>
>>> scoreRule :: TransformationRule -> Z.Zipper (Tag, Tag) -> Int
>>> scoreRule r z = nCorrect - nIncorrect
>>> where (nCorrect, nIncorrect) = scoreRule_ r z
>>>
>>> scoreRule_ :: TransformationRule -> Z.Zipper (Tag, Tag) -> (Int, Int)
>>> scoreRule_ r = Z.foldlz' (scoreElem r) (0, 0)
>>> where scoreElem r s@(nCorrect, nIncorrect) z =
>>> case ruleApplication r z of
>>> Just tag -> if tag == correct then
>>> (nCorrect + 1, nIncorrect)
>>> else
>>> (nCorrect, nIncorrect + 1)
>>> Nothing -> s
>>> where (correct, _) = Z.cursor z
>>>
>>> however I see that the eager version of foldlz is being used.
>>> I also though that maybe ruleApplication my not be executing
>>> immediately. But I cannot see why (added definition below for
>>> reference).
>>>
>>> Can anyone point out why this is not strict?
>>
>> The additions (increments) are never forced before the final subtraction,
>> so from scoreRule_ you will probably get a pair of thunks
>> (((...(0+1)+1...)+1), ((...(0+1)+1...)+1)),
>> since the forcing in the fold can only use seq, to force *the outermost
>> constructor* of the intermediate results, in this case, the outermost
>> constructor is the pair constructor - (,) - and the components are left
>> unforced.
>>
>> To force the increments without (big) delay, you can
>> - use a custom strict pair type instead of ordinary pairs
>>
>> data P = P !Int !Int -- {-# UNPACK #-} the fields for extra goodness
>>
>> so that forcing the outermost constructor automatically forces the
>> components.
>>
>> - make the scoreElem function strict in the components of the accumulator
>> s, with ghc {-# LANGUAGE BangPatterns #-},
>>
>> scoreElem r !s@(!nCorrect, !nIncorrect) z = ...
>>
>> that way you will never get bigger thungks than (n+1) in the components
>>
>> - force the updated count as it is constructed,
>>
>> if tag == correct
>> then let newCorrect = nCorrect+1
>> in newCorrect `seq` (newCorrect, nIncorrect)
>> else let newIncorrect = ...
>>
>>
>> The important thing to be aware of is that seq only forces the outermost
>> level of a value. If the value is a structure with more levels, it
>> doesn't
>> prevent the building of huge thunks in the inner levels at all.
>> You then have to take care of that yourself, by using a datatype with the
>> desired strictness or, in the case of folds and similar, providing a
>> comination function with the desired strictness.
>>
>> HTH,
>> Daniel
>>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 6
Date: Thu, 27 Oct 2011 16:26:10 +0200
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Stack space overflow: using strict
accumulator still fails
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
On Thursday 27 October 2011, 15:44:34, Hugo Ferreira wrote:
> My apologies, the 2nd function should be:
>
> scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
> where scoreElem r s@(nCorrect, nIncorrect) z =
> case ruleApplication r z of
> Just tag -> if tag == correct then
> let nCorrect = nCorrect + 1 in
This is a cyclic definition. The nCorrect on the right hand side is not the
nCorrect from the function parameter but the nCorrect from the left hand
side of the definition, so you have a nonterminating value here.
You need to introduce a new name,
let newCorrect = nCorrect + 1
in newCorrect `seq` (newCorrect, nIncorrect)
(since nIncorrect isn't changed, we don't need to use seq on that).
> nCorrect `seq` nIncorrect `seq`
> (nCorrect, nIncorrect)
> else let nIncorrect = nIncorrect + 1 in
Same problem here.
> nCorrect `seq` nIncorrect `seq`
> (nCorrect, nIncorrect)
> Nothing -> s
> where (correct, _) = Z.cursor z
>
> R,
> Hugo F.
>
> On 10/27/2011 02:22 PM, Hugo Ferreira wrote:
> > Hello,
> >
> > After trying the suggestions, I still cannot execute
> > the code. I have tried:
> >
> > scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
> > where scoreElem r !s@(!nCorrect, !nIncorrect) z =
> > case ruleApplication r z of
> > Just tag -> if tag == correct then
> > (nCorrect+1, nIncorrect)
> > else (nCorrect, nIncorrect + 1)
> > Nothing -> s
> > where (correct, _) = Z.cursor z
That should run, what's the problem here?
Perhaps the bangs should be placed s@(!(InCorrect, !nIncorrect)), I'm not
sure how ghc treats bang patterns exactly atm.
> >
> > and
> >
> > scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
> > nIncorrect)
> > where (correct, _) = Z.cursor z
> > nCorrect = nCorrect + 1
> > nIncorrect = nIncorrect + 1
Again cyclic definitions.
> > where scoreElem r s@(nCorrect, nIncorrect) z =
> > case ruleApplication r z of
> > Just tag -> if tag == correct then
> > let nCorrect = nCorrect + 1 in
> > nCorrect `seq` nIncorrect `seq` (nCorrect, nIncorrect)
> > else let nIncorrect = nIncorrect + 1 in
> > nCorrect `seq` nIncorrect `seq` (nCorrect, nIncorrect)
> > Nothing -> s
> > where (correct, _) = Z.cursor z
Here too.
> >
> >
> > In an attempt to figure out the problem I also tried:
> >
> > scoreRule_ r zs = Z.foldlz' (scoreElem r) (0, 0) zs
> > where scoreElem r !s@(!nCorrect, !nIncorrect) z = (nCorrect,
> > nIncorrect) where (correct, _) = Z.cursor z
> > nCorrect = nCorrect + 1
> > nIncorrect = nIncorrect + 1
> >
> > Strangely enough GHC complains that correct, nCorrect and nIncorrect
> > are not used.
With -Wall or -fwarn-name-shadowing it should also complain about the
shadowing of nCorrect and nIncorrect.
> > Why is this so for nCorrect and nIncorrect? Why won't
> > the above also execute in a strict manner?
> >
> > Does anyone have any ideas why I still get stack-overflow?
> >
> > TIA,
> > Hugo F.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 40, Issue 42
*****************************************
