Difference between revisions of "Talk:Correctness of short cut fusion"
(Comments on unfoldr/destroy fusion without seq) |
(→Details about what uses of seq are dangerous: new section) |
||
Line 18: | Line 18: | ||
</haskell> |
</haskell> |
||
--[[User:Twanvl|Twanvl]] 12:18, 13 February 2007 (UTC) |
--[[User:Twanvl|Twanvl]] 12:18, 13 February 2007 (UTC) |
||
+ | |||
+ | == Details about what uses of seq are dangerous == |
||
+ | |||
+ | If I understand things properly, the essential problem with <hask>seq</hask> in <hask>foldr/build</hask> is that it allows the builder function |
||
+ | <haskell> |
||
+ | g :: forall b . (a -> b -> b) -> b -> b |
||
+ | g cons nil = ... |
||
+ | </haskell> |
||
+ | to do something with values of type <hask>b</hask> other than pass them to <hask>cons</hask>, namely to <hask>seq</hask> against them. If <hask>g</hask> doesn't force anything whose type includes <hask>b</hask>, it should, I believe, be safe to fuse. For example, <hask>unfoldr</hask> written using <hask>build</hask> 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-<hask>seq</hask>-free machinery of <hask>unfoldr</hask>. --[[User:Dfeuer|Dfeuer]] ([[User talk:Dfeuer|talk]]) 03:22, 15 August 2014 (UTC) |
Latest revision as of 03:22, 15 August 2014
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)