[Haskell-cafe] Re: sort and lazyness (?)

[Bayley, Alistair]

> 	reverse creates the output list by pulling items from 
> the head of the
> 	input list, and prefixing them to the output list.
> 
> 
> Tail recursively! That is a very important point. Let's have 
> a closer look at an explicitly recursive version.
> 
> reverse xs = go [] xs
>   where
>   go out [] = out
>   go out (x:xs) = go (x:out) xs
> 
> Now let's do a rewrite chain:
> 
> reverse (enumFromTo 1 4)
> go [] (enumFromTo 1 4)
> go [] (1:enumFromTo 2 4)
> go (1:[]) (enumFromTo 2 4)
> go (1:[]) (2:enumFromTo 3 4)
> go (2:1:[]) (enumFromTo 3 4)
> go (2:1:[]) (3:enumFromTo 4 4)
> go (3:2:1:[]) (enumFromTo 4 4)
> go (3:2:1:[]) (4:enumFromTo 5 4)
> go (4:3:2:1:[]) (enumFromTo 5 4)
> go (4:3:2:1:[]) []
> 4:3:2:1:[]
> 
> (For sanity I skipped the number evaluation steps, but 
> enumFromTo would have been forcing them to check for the end, 
> so it ends up the same)
>  
> We needed to construct the entire reversed list before we 
> could see the first cons cell. 
> 
> There is a very strange implementation of reverse whose spine 
> is as lazy as the input spine (but forcing the first element 
> will still force the whole input spine).  But it is quite 
> odd, and certainly is not arrived at by the compiler 
> automatically from the definition in the Prelude.
> 
> I verified with -O2.  length . reverse is not constant space 
> in GHC.  And there really is no reasonable way it could be 
> (save for specific RULES pragmata).
> 
> Luke


One could also well imagine a list fusion optimisation that says:

  length . reverse == length

I have no idea if this is applied (or even correct).


I compared (with ghc 6.8, --make -O2 -prof -auto-all):

main = print (length x)
x :: [Int]
x = [1..1000000]

	total alloc =  40,002,288 bytes  (excludes profiling overheads)


main = print (length (reverse x))
x :: [Int]
x = [1..1000000]

	total alloc =  52,002,296 bytes  (excludes profiling overheads)

So the reverse has some overhead (25%). Is that what you'd expect if it
was entirely constructed?


Another comparison:

main = print (length x)
x :: [Int]
x = take 1000000 (repeat 1)

	total alloc =  24,002,256 bytes  (excludes profiling overheads)

main = print (length (reverse x))
x :: [Int]
x = take 1000000 (repeat 1)

	total alloc =  36,002,264 bytes  (excludes profiling overheads)


I'm not sure what this says, exactly (50% overhead?).

Alistair
*****************************************************************
Confidentiality Note: The information contained in this message,
and any attachments, may contain confidential and/or privileged
material. It is intended solely for the person(s) or entity to
which it is addressed. Any review, retransmission, dissemination,
or taking of any action in reliance upon this information by
persons or entities other than the intended recipient(s) is
prohibited. If you received this in error, please contact the
sender and delete the material from any computer.
*****************************************************************