Personal tools

Talk:Correctness of short cut fusion

From HaskellWiki

Revision as of 03:22, 15 August 2014 by Dfeuer (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

If unfoldr would use a lazy pattern match:

unfoldr :: (b -> Maybe (a,b)) -> b -> [a]
unfoldr p e = case p e of Nothing     -> []
                          Just ~(x,e') -> x:unfoldr p e'

the left hand side of the example without seq will be the same as the right hand side:

destroy g (unfoldr p e) = g step (unfoldr p e)
                        = case step (unfoldr p e) of Just z -> 0
                        = case step (case p e of Nothing     -> []
                                                 Just ~(x,e') -> x:unfoldr p e') of Just z -> 0
                        = case step (case Just undefined of Nothing     -> []
                                                            Just ~(x,e') -> x:unfoldr p e') of Just z -> 0
                        = case step (undefined:unfoldr p undefined) of Just z -> 0
                        = case Just (undefined,unfoldr p undefined) of Just z -> 0
                        = 0

--Twanvl 12:18, 13 February 2007 (UTC)

Details about what uses of seq are dangerous

If I understand things properly, the essential problem with
seq
in
foldr/build
is that it allows the builder function
g :: forall b . (a -> b -> b) -> b -> b
g cons nil = ...
to do something with values of type
b
other than pass them to
cons
, namely to
seq
against them. If
g
doesn't force anything whose type includes
b
, it should, I believe, be safe to fuse. For example,
unfoldr
written using
build
should, I believe, be safe to fuse because the function it is given isn't passed the polymorphic cons and nil arguments—the list generation is left up to the known-
seq
-free machinery of
unfoldr
. --Dfeuer (talk) 03:22, 15 August 2014 (UTC)