Haskell recursive function without stack overflow

Question

I have a recursive function which index a textile and if I use it for huge textfiles, i'll get a stack space overflow. I thought because I put the recursive part in the let part I could avoid this stack space overflow, but I'm still getting it. What would be the best way to avoid a stack space overflow with this function?

--lines to Map

parseLinesToWordEntryMap :: Int -> [String] -> M.Map Word [TextLocation] -> (M.Map Word [TextLocation])
parseLinesToWordEntryMap lineNumber [] wordEntryMap  = wordEntryMap
parseLinesToWordEntryMap lineNumber (x:xs) wordEntryMap =
    let
         lineNumber' = lineNumber-1
         wordEntryMapRec = parseLinesToWordEntryMap lineNumber' xs wordEntryMap
    in
         parseLineToWordEntryMap lineNumber x wordEntryMapRec

It would help to know the definition of parseLineToWordEntryMap — applicative
– applicative, Commented Jul 9, 2012 at 14:42

Daniel Fischer · Accepted Answer · 2012-07-09 13:54:30Z

7

What you have is essentially a right fold,

parseLinesToWordEntryMap lineNumber xs wordEntryMap
    = foldr update wordEntryMap (zip [lineNumber, lineNumber - 1 .. ] xs)
      where
        update (num,x) wordMap = parseLineToWordEntryMap num x wordMap

thus if parseLineToWordEntryMap is strict in its Map argument (fairly typical for Map arguments), nothing can be done before the end of the list is reached, and then the result is built going back to the beginning of the list.

If at all possible, you should consume the input the other way round, with a left fold, and make sure that the folded function has the right strictness, so that no large thunks are built.

For more specific suggestions, we'd need to see more of the code.

edited Jul 9, 2012 at 13:54

answered Jul 9, 2012 at 13:48

Daniel Fischer

184k19 gold badges319 silver badges436 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

LeonS Over a year ago

parseLineToWordEntryMap is function of this: Int -> String -> M.Map Word [TextLocation] -> M.Map Word [TextLocation] I'm currently investigating foldl but don't know how to use it for my function, do you have an idea?

Daniel Fischer Over a year ago

I'd need to know what the function does, how it's implemented. I suspect it just adds the line number to the [TextLocation] associated to the String (and inserts the String into the Map if not yet present). Then it's quite easy to transform it to a left fold. But I'd rather not speculate more without seeing what about.

applicative Over a year ago

Starting from Daniel Fischer's version, you would substitute foldl' (strict version in Data.List) for foldr, which would require flipping the arguments in the definition of update. Then his other advice about strictness would need to be studied. Edit: I am adding a little speculation, now that I see he commented at the same time.

LeonS Over a year ago

@Daniel your speculation is right, I sent you a message via BitBucket

Daniel Fischer Over a year ago

@LeonS Indeed, a left fold is what's needed here. I'm rewriting now.

|

Collectives™ on Stack Overflow

Haskell recursive function without stack overflow

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related