Does span run in bounded space?
Facundo DomÃnguez
facundo.dominguez at tweag.io
Wed Sep 13 11:58:05 UTC 2017
Dear devs,
I used to think that span is a function which doesn't run in bounded
space. But ghc defied this understanding. The program copied below
runs in bounded space with "ghc-8.2.1 -O0 main.hs; ./main" but it does
not if run with "runghc-8.2.1 -O0 main.hs".
Does someone have any insights on what's the optimization that is
making a difference in the memory footprint of these two methods of
running?
Or is there a bug in ghci, and span is supposed to run in bounded
space after all?
Thanks,
Facundo
import Prelude hiding (span)
import Data.List (foldl')
main = case span (>0) (replicate 100000000 1) of
(xs, ys) -> do
print (foldl' (+) 0 xs)
print (foldl' (+) 0 ys)
span :: (a -> Bool) -> [a] -> ([a],[a])
span _ xs@[] = (xs, xs)
span p xs@(x:xs')
| p x = let (ys, zs) = span p xs' in (x : ys, zs)
| otherwise = ([],xs)
More information about the ghc-devs
mailing list