`seq` breaks the foldr/build-rule

[Janis Voigtlaender]

Hello,

while we are talking about strange semantic inequalities in the presence
of `seq` (supposed monads not satisfying the monad laws anymore...), I
just wanted to reiterate a point I made in a previous post, namely that
`seq` also makes the foldr/build-rule of shortcut deforestation [1]
wrong.

Consider the following (admittedly artificial) program:

 build:: (forall b . (a -> b -> b) -> b -> b) -> [a]
 build g = g (:) []

 original :: [Int] -> Int
 original l =  foldr const 0 (build g)
	where g c n = let h []     = n
                          h (x:xs) = let f=h xs 
                                     in  (c x f) `seq` (c 1 f)
                      in  h l

The foldr/build-rule says that for all g of appropriate type holds:

  foldr k z (build g) = g k z

i.e., the function "original" should be equivalent to the following:

 optimized :: [Int] -> Int
 optimized l = g const 0
	where g c n = let h []     = n
                          h (x:xs) = let f=h xs 
                                     in  (c x f) `seq` (c 1 f)
                      in  h l

But now we have a problem! In Hugs:

 Main> original [undefined]
 1
 (19 reductions, 35 cells)
 Main> optimized [undefined]
 
 Program error: {undefined}
 (10 reductions, 57 cells)

i.e. on the argument list [undefined] the "original" function yields a
nice result, while the "optimized" function fails at runtime.
This is not quite an optimization, right?

For list producers expressed with build in the Prelude this
incorrectness shouldn't be harmful (if they do not use `seq`). But if
one wants to write ones own list producers for shortcut deforestation,
or to use Olaf Chitil's type-inference based deforestation [2], one has
to be extremely careful with using `seq`.


[1] A. Gill, J. Launchbury and S.L. Peyton Jones. A Short Cut to
Deforestation. In Functional Programming Languages and Computer
Architecture, Copenhagen, Denmark, Proceedings, pages 223-232. ACM
Press, June 1993. 

[2] O. Chitil. Type Inference Builds a Short Cut to Deforestation. In
International Conference on Functional Programming, Paris, France,
Proceedings, volume 34 of ACM SIGPLAN Notices, pages 249-260, September
1999. 


--
Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt@tcs.inf.tu-dresden.de