current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 1 down vote favorite

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
share|improve this question
    
It would help to know the definition of parseLineToWordEntryMap –  applicative Jul 9 '12 at 14:42

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
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? –  LeonS Jul 9 '12 at 14:38
    
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. –  Daniel Fischer Jul 9 '12 at 14:45
    
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. –  applicative Jul 9 '12 at 14:45
    
@Daniel your speculation is right, I sent you a message via BitBucket –  LeonS Jul 9 '12 at 14:52
    
@LeonS Indeed, a left fold is what's needed here. I'm rewriting now. –  Daniel Fischer Jul 9 '12 at 15:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.