Hi,
> let (first,rest) = break (const False) input
> in
> print (length (first ++ rest))
>
> When I compile this program using -O2 and use a large text file as
> input the code runs in constant space. If I understand correctly,
> the program runs in constant space because ghc uses an optimization
> similar to the one proposed by Wadler/Sparud.
Right. The optimization works by producing special thunks for tuple
selectors which the garbage collector can recognize and evaluate
during GC.
However the implementation in GHC is quite brittle. See
http://hackage.haskell.org/trac/ghc/ticket/2607
I suspect your program is another instance of this behaviour.
> If I define the following function which is based on break
>
> splitBy :: (a -> Bool) -> [a] -> [[a]]
> splitBy _ [] = []
> splitBy p xs =
> l : case ys of
> [] -> []
> _:zs -> splitBy' p zs
> where
> (l,ys) = break p xs
I haven't looked in detail; what follows is a guess of what
ghc may be doing. It could be verified by looking at the
generated core.
The where-binding desugars to something like
let q = break p xs
ys = case q of (_, ys) -> ys
l = case q of (l, _) -> l
in ...
ys can be inlined into splitBy, producing
l : case (case q of (l, ys) -> ys) of
[] -> []
_:zs -> splitBy' p zs
l : case q of (l, ys) -> case ys of
[] -> []
_:zs -> splitBy' p zs
and now the tuple selector is no longer recognizable.
Best regards,
Bertram
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
