Is scanl' safe for foldr/build fusion?
David Feuer
david.feuer at gmail.com
Wed Jul 23 20:17:53 UTC 2014
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>
More information about the Libraries
mailing list