Is scanl' safe for foldr/build fusion?

[David Feuer]

In a comment on trac #9345, nomeata proposed the implementation of
Data.List.inits below. He indicates that the performance is very good, and
wrote it in this fashion so it could fuse. My concern is that since seq is
used in the argument to build, we need to make sure that fusion on the left
will be safe. If I did the calculations right, this specifically requires
that for all f, cons, nil, and bs, and all a≠_|_, the following "correct"
expression

e1 = a `cons`
     foldr cons nil $
       foldr (\b g x -> (let b' = f x b in b' `seq` (b' : g b')))
          (\b -> b `seq` [])
          bs
          a

gives the same result as the fused expression

e2 = a `cons`
     foldr (\b g x -> (let b' = f x b in b' `seq` (b' `cons` g b')))
           (\b -> b `seq` nil)
           bs
           a

I haven't been able to figure out how to prove this or give a
counterexample, so far, but I have very little experience with such.

myScanl' :: (b -> a -> b) -> b -> [a] -> [b]
myScanl' f a bs = build $ \c n ->
     a `seq` a `c`
     foldr (\b g x -> (let b' = f x b in b' `seq` (b' `c` g b')))
           (\b -> b `seq` n)
           bs
           a

 initsQ2 :: [a] -> [[a]]
 initsQ2 = map toListQ . myScanl' snocQ emptyQ
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140723/b39172e6/attachment.html>