Does span run in bounded space?

13 Sep 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)

Does span run in bounded space?

Facundo Domínguez