[Haskell-cafe] RE: simple function: stack overflow in hugs vsnonein ghc

[john lask]

nope.

it is true that in the case of an infinite list it exibits the "desired" 
behaviour but ...

return (replicate 1000000 'a') >>= \x->print $ spant (const True) x

ERROR - Garbage collection fails to reclaim sufficient space

i.e. as the function unfold, the thunk representing the second term builds 
up on the heap. (not sure why it works for an infinite list, hugs must drop 
the reference to the tail ?)

to obtain a function that will properly operate in constant space, for every 
unfolding of the first term we need to enforce evaluation of the second 
term.

>From: "Claus Reinke" <claus.reinke at talk21.com>
>To: "john lask" <jvlask at hotmail.com>
>CC: <haskell-cafe at haskell.org>
>Subject: Re: [Haskell-cafe] RE: simple function: stack overflow in hugs 
>vsnonein ghc
>Date: Mon, 24 Sep 2007 16:20:42 +0100
>
>>afraid not
>>
>>the given example is too strict, the requirement is to generate the 
>>matched portion lazilly, and return the tail (unconsumed portion).
>
>ah yes, without optimisations, Prelude.span builds up stack,
>while the continuation-based alternative i mentioned is too
>strict for some uses.
>
>>In principle the function should be capable of being written to run in 
>>constant space which the given example dose not.
>
>
>>>>return (repeat 'a') >>= \ x -> print $ span (const True) x
>
>how about the old spec, then?
>
>    span p l = (takeWhile p l,dropWhile p l)
>
>since takeWhile takes forever, here, it isn't even inefficient!-)
>
>claus
>
>>>>with hugs you will get a stack error, in ghc it executes in constant 
>>>>space, i.e. indefinitely. In essenece the above example does exactly the 
>>>>same as my ealier code.
>>>
>>>this thread might be relevant:
>>>
>>>http://www.haskell.org/pipermail/hugs-bugs/2007-June/001815.html
>>>http://www.haskell.org/pipermail/hugs-bugs/2007-June/001816.html
>>>http://www.haskell.org/pipermail/hugs-bugs/2007-June/001817.html
>
>

_________________________________________________________________
Get more out of your e-mail. Update to Windows Live Hotmail today! 
http://ninemsn.com.au/share/redir/adTrack.asp?mode=click&clientID=778&referral=HotmailTagline&URL=http://g.msn.com/8HMBEN/14811??PS=