Stream Fusion的工作原理是什么？

Question

我可以找到Stream Fusion的唯一资源是介绍它的论文,这些资源并不是最好的学习资源.流融合究竟是如何工作的？

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

Answer 1

这里的定义maps从邓肯Coutt的论文(第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与"案例的情况"的表述-再次注意,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函数.