haskell - Stream Fusion 究竟是如何工作的？

Question

我能找到的关于 Stream Fusion 的唯一资源是介绍它的论文，这并不是最好的学习资源。流融合究竟是如何工作的？

更具体地说，因为这是 paper 的部分没有解释清楚:列表->流转换后生成的协同结构(即 maps f . maps g )本身是如何折叠的？

Answer 1

这是 maps 的定义来自 Duncan Coutt's thesis (第 1.4.2 节):

maps :: (a → b) → Stream a → Stream b
maps f (Stream next0 s0) = Stream next s0
    where
        next s = case next0 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (f x) s′

现在考虑表达式

maps f . maps g

编译器可以内联 (.)要得到

\x -> maps f (maps g x)

从 Stream的定义我们可以看出它只有一个构造函数:

data Stream a = ∃ s . Stream (s → Step a s) s

所以前面的结果等价于:

\(Stream next0 s) -> maps f (maps g (Stream next0 s))

内联 maps g ，这是安全的 maps是非递归的(这是流融合的关键见解):

\(Stream next0 s) -> maps f (Stream next1 s)
      where
          next1 s = case next0 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (g x) s′

内联 maps f :

\(Stream next0 s) -> Stream next2 s
      where
          next1 s = case next0 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (g x) s′
          next2 s = case next1 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (f x) s′

接下来我们可以内联 next1进入 next2并简化 case带有“case-of-case”的表达式 - 再次注意 next1是非递归的 - 并删除现在已死的 next1 :

\(Stream next0 s) -> Stream next2 s
      where
          next2 s = case next0 s of
            Done → Done
            Skip s′ → Skip s′
            Yield x s′ → Yield (f (g x)) s′

关键是这些步骤都是小的优化，它们在孤立的情况下是有意义的，不需要流融合本身的特殊编译器知识，或者 Stream。输入或 maps功能。