Does span run in bounded space?

Previous Topic Next Topic
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

Does span run in bounded space?

Facundo Domínguez-3
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

Or is there a bug in ghci, and span is supposed to run in bounded
space after all?


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)
ghc-devs mailing list
[hidden email]