Stream 是 traversable 的一个实例

Question

vector-0.1 包有一个非常有效的 Stream 实现（Data.Vector.Stream）：

data Step s a = Yield a s
              | Skip    s
              | Done

-- | The type of fusible streams
data Stream a = forall s. Stream (s -> Step s a) s Size

vector 的更高版本将其扩展为单子版本 Data.Vector.Fusion.Stream.Monadic，但为了简单起见，让我们使用旧的非单子版本。

Stream 很自然地是 Functor 和 Foldable:

的一个实例

instance Foldable Stream where
    foldMap f s = foldl' (\a b -> a <> (f b)) mempty s

作为一个流，它也应该是Traversable的一个实例，不是吗？至少乍一看，它看起来很简单。我们需要

sequenceA :: Applicative f => Stream (f a) -> f (Stream a)

一开始是

sequenceA (Stream step s) = Stream <$> step' <*> (pure s) where
    step' = ...

<*> 是从 Stream 下 'pull out' 应用 f 的唯一途径。现在，step' 应该是

step' :: f (s -> Step s a)

而且我们有

step :: s -> Step s (f a)

我只知道 f 是一个 Applicative（和 Functor）。但是 <*> 'pulls in' f (<*> :: f(a->b)->(f a->f b)) 而这里我需要的是完全相反的，一个 co-<*> 可以这么说。

拥有一个 Traversable 实例在我的任何努力中都不是至关重要的，从性能的角度来看，它甚至可能是不可取的。但令我烦恼的是，我并不真正理解为什么 Stream 不会是 Traversable。使 Stream 成为 Traversable 缺少什么结构元素？

Answer 1

这是 Traversable，但不是很有趣的方式。因为它允许 fromList 以及 toList，所以我们有

sequenceA = fmap fromList . sequenceA . toList

你真的不能做更有趣的事情了：你有一个 Stream (f a) 并希望产生 f (Stream a)。由于您的 Stream 与列表同构，要使 f 中的效果达到外层，您必须遍历流中的每个项目，合并每个项目的效果，最后重建一个流，以模仿嵌入在其中的对象应用结构，按照你看到它们的顺序。

如果愿意，您可以使用 Stream 模块中的其他函数自己重新实现它，但它的作用基本相同。特别是，它同样懒惰。一种方法是：

sequenceA (Stream step init) = case step init of
  Yield x s -> cons <$> x <*> sequenceA (Stream step s)
  Skip s -> sequenceA $ Stream step s
  Done -> pure (Stream (const Done) ())

如您所见，与您的尝试最大的不同是您应该 fmapping 到 Yield 案例中找到的 x 值 - 这是合并其效果的唯一方法，因为正如您所指出的那样无法从 f a 中提取值，只能将其他值推入一个值。令人高兴的是，这毕竟是你想要做的！在到达结构中有趣的部分之前，您无法对任何内容进行 fmap，这意味着首先调用 step s 以掌握其效果。

您根本不需要 pure s，因为您正在构建一个新的 Stream，它具有一种新的内部状态，与您消费的 Stream 无关。而且您已经有办法利用范围内的 s 值：用它调用 step！

一旦您已经编写了几个使用 Stream 的函数（这是我通过手动实现 Foldable 和 Functor 发现的），这种方法就相当自然了。使用 Stream 的唯一可能方法是在 step s 上进行大小写匹配，如果你以此开始，你就避开了让你分心的红鲱鱼。

Stream 是 traversable 的一个实例

Stream to be an instance of traversable

haskell

stream

applicative

traversable