Can I exploit lazy evaluation to reference future values without space leaks?

Question

I'm looking to try to run a moderately expensive function on a large list of inputs, using part of the output of that function as one of its inputs. The code runs as expected, unfortunately it consumes a large amount of memory in the process (just under 22GiB on the heap, just over 1GiB maximum residency). Here is a simplified example of what I mean:

{-# LANGUAGE OverloadedStrings #-}

import Data.List (foldl')
import qualified Data.Text as T
import qualified Data.Text.Lazy as TL
import qualified Data.Text.Lazy.IO as TL
import qualified Data.Text.Lazy.Builder as TB

main :: IO ()
main = TL.putStr $ TB.toLazyText showInts

showInts :: TB.Builder
showInts = foldMap fst shownLines
  where
    shownLines = map (showInt maxwidth) [0..10^7]
    maxwidth = foldl' (\n -> max n . snd) 0 shownLines

showInt :: Int -> Int -> (TB.Builder, Int)
showInt maxwidth n = (builder, len)
  where
    builder = TB.fromText "This number: "
      <> TB.fromText (T.replicate (maxwidth - len) " ") <> thisText
      <> TB.singleton '\n'
    (thisText, len) = expensiveShow n

expensiveShow :: Int -> (TB.Builder, Int)
expensiveShow n = (TB.fromText text, T.length text)
  where text = T.pack (show n)

Note that in the where clause of showInts, showInt takes maxwidth as an argument, where maxwidth itself depends on the output of running showInt maxwidth on the whole list.

If, on the other hand, I do the naïve thing and replace the definition of maxwidth with foldl' max 0 $ map (snd . expensiveShow) [0..10^7], then maximum residency falls to just 44KiB. I would hope that performance like this would be achievable without workarounds like precomputing expensiveShow and then zipping it with the list [0..10^7].

I tried consuming the list strictly (using the foldl package), but this did not improve the situation.

I'm trying to have my cake and eat it too: exploiting laziness, while also making things strict enough that we don't build up a mountain of thunks. Is this possible to do? Or is there a better technique for accomplishing this?

This feels similar to [*Catamorphism that allows looking at part of the final result*](https://stackoverflow.com/q/56121207/2751851). The consensus in that case was that laziness tricks couldn't save us from linear memory consumption. — duplode, Mar 10 '21 at 18:11

score 5 · Accepted Answer · answered Mar 10 '21 at 13:46

You can't do it like this.

The problem is that your showInts has to traverse the list twice, first to find the longest number, second to print the numbers with the necessary format. That means the list has to be held in memory between the first and second passes. This isn't a problem with unevaluated thunks; it is simply that the whole list, completely evaluated, is being traversed twice.

The only solution is to generate the same list twice. In this case it is trivial; just have two [0..10^7] values, one for the maximum length and the second to format them. I suspect in your real application you are reading them from a file or something, in which case you need to read the file twice.

Can I exploit lazy evaluation to reference future values without space leaks?

1 Answers1