Reduce list on the fly in Haskell

Question

Assume I have a function `f` which accepts some input and produce a number. Within the function `f`, a list is created according the input, which is then reduced (e.g. using `foldl' g`) to produce the final output number. Because the intermediate list is to be reduced after all, is it possible to apply the reduce function `g` without expressing the intermediate list. The goal here is to limit memory used for storing (or expressing, if 'storing' a less accurate word) the list. To illustrate it, this function `foldPairProduct` takes `O(N1 * N2)` space for the intermediate list (the space consumed maybe more complicated due to expression and lazy evaluation, but I assume it is proportional or worse). Here `N1, N2` are the size of the two input lists. ``` foldPairProduct :: (Num a, Ord a) => (a -> a -> a) -> [a] -> [a] -> a foldPairProduct f xs ys = foldl1 f [ x*y | x <- xs, y <- ys] ``` An alternative implementation to the logic is foldPairProduct', which takes `O(2 * 2)` space. ``` fold…

Accepted Answer

``` foldPairProduct :: (Num a, Ord a) => (a -> a -> a) -> [a] -> [a] -> a foldPairProduct f xs ys = foldl1 f [ x*y | x <- xs, y <- ys] ``` can be a good memory citizen. The second argument, `ys` is used repeatedly, so that will have to be in memory entirely during the computation, but the intermediate list is lazily produced as it is consumed, so that contributes only a constant amount of memory, giving an overall `O(length ys)` space complexity. Of course there have to be `length xs * length ys` list cells produces and consumed, so the overall allocations are `O(length xs * length ys)` [assuming each `a` value uses bounded space]. The number of bytes copied during GC (and thus the time needed for GC) can be drastically reduced by providing a larger allocation area, with `+RTS -A1M`, the number drops from ``` 3,717,333,376 bytes copied during GC ``` for the default setting to ``` 20,445,728 bytes copied during GC ``` and the time from `GC time 4.88s` to `GC time 0.07s` for `xs == ys = [1 .. 10000] :: [Int]` and `f = (+)`. But that depends on the strictness analyser doing its job - which it does fine if the type it's used at is e.g. `Int` and known during compilation, and the combining function is known to be strict. If the code is not specialised or if the combining function is not known to be strict, the fold will produce a thunk of `O(length xs * length ys)` size. That problem can be alleviated by using the stricter `foldl1'`. ``` foldPairProduct' :: Num a => (Maybe a -> Maybe a -> Maybe a) -> [a] -> [a] -> Maybe a foldPairProduct' _ _ [] = Nothing foldPairProduct' _ [] _ = Nothing foldPairProduct' f (x:xs) (y:ys) = foldl1 f [Just $ x*y, foldPairProduct' f [x] ys, foldPairProduct' f xs [y], foldPairProduct' f xs ys] ``` runs head-on into the problem of insufficient strictness, the value wrapped by a `Just` constructor can't be made strict by the compiler here, since it might not be needed for the overall result, so the fold often produces an `O(length xs * length ys)` size thunk under the `Just` - of course, for some `f`, like `const`, it will behave well as is. For that to be a good memory citizen if all values are used, you must use a sufficiently strict combining function `f`, forcing also the value under `Just` in the result (if it's a `Just`); using `foldl1'` also helps. With that, it can have `O(length ys + length xs)` space complexity (the lists `xs` and `ys` are used more than once, so are reused). ``` foldCrossProduct :: Num a => (a -> a -> a) -> [[a]] -> a foldCrossProduct f xss = foldl1 f (crossProduct xss) crossProduct :: Num a => [[a]] -> [a] crossProduct [] = [] crossProduct (xs:[]) = xs crossProduct (xs:xss) = [x * y | x <- xs, y <- crossProduct xss] ``` Although GHC does little CSE (common subexpression elimination), the list `crossProduct xss` will (probably) be shared here between the different `x`s, so that produces `O(N2*...*Nk)` space complexity. If the order of elements in the list doesn't matter, reordering to ``` crossProduct (xs:xss) = [x * y | y <- crossProduct xss, x <- xs] ``` helps. Then `crossProduct xss` need not be in memory at once, so can be incrementally produced and consumed, only `xs` must be remembered because it's used multiple times. For the recursive invocations, the first of the remaining lists has to be shared, so that would produce an overall `O(N1+...+Nk-1)` space complexity.

Reduce list on the fly in Haskell

Solution

Problem

Related problems