gmane.comp.lang.haskell.cafe

Stack Overflow, tail recursion and CPS

Hi all,

I get a stack overflow when I want to insert a huge, lazy list into a Map.

I have changed the insertion algo to use foldl to make it tail-recursive  
but still get a stack overflow as the "insert" remains lazy.

Could CPS be a solution in these cases?

Günther

headers

Neil Mitchell | 14 Jan 18:32

Re: Stack Overflow, tail recursion and CPS

Hi

> I have changed the insertion algo to use foldl to make it tail-recursive but
> still get a stack overflow as the "insert" remains lazy.

Try foldl' and insertWith' - that should work.

Thanks

Neil

headers

Günther Schmidt | 14 Jan 19:19

Re: Stack Overflow, tail recursion and CPS

Hello Neil,

thanks, that did indeed work.

I guess I shot myself in the foot a bit here ...

Cause my real problem isn't actually with Map but with IxSet (from HAppS)  
which to my knowledge does not have some sort of strict insert function.  
Me trying to be really clever just used Map as a random example here  
quietly hoping to get confirmation for "Yes, CPS is the anwer to force  
evaluation here, keep digging in that direction boy", or a straight CPS  
solution which I then would just translate to my problem.

Um ...

Didn't work, you were to clever, thanks a bunch Neil :)

Günther

Am 14.01.2009, 18:32 Uhr, schrieb Neil Mitchell <ndmitchell <at> gmail.com>:

> Hi
>
>> I have changed the insertion algo to use foldl to make it  
>> tail-recursive but
>> still get a stack overflow as the "insert" remains lazy.
>
> Try foldl' and insertWith' - that should work.
>
> Thanks

(Continue reading)

headers

Jonathan Cast | 14 Jan 19:37

Re: Stack Overflow, tail recursion and CPS

On Wed, 2009-01-14 at 19:19 +0100, Günther Schmidt wrote:
> Hello Neil,
> 
> thanks, that did indeed work.
> 
> I guess I shot myself in the foot a bit here ...
> 
> Cause my real problem isn't actually with Map but with IxSet (from HAppS)  
> which to my knowledge does not have some sort of strict insert function.

Does it by any chance have a Control.Parallel.Strategies.NFData
instance?  If it should happen to, then replacing (I didn't look up the
type of insert!)

    foldl insert empty xn

with

    foldl' ((result.result) (`using` rnf) insert) empty xn

(where result is the Semantic Editor Combinator[1]

    result e f = e . f)

would give you as much strictness as possible.

Which might not be an improvement.

jcc

(Continue reading)