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

Answer 1

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.