haskell - Stream 成为可遍历的实例

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 ，但为了简单起见，让我们使用旧的、非单子(monad)的。
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' = ...

<*>是“拉出”应用程序 f 的唯一方法来自 Stream .现在，step'应该

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

我们有一个

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

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

拥有 Traversable实例对我的任何努力都不是至关重要的，从性能的角度来看，它甚至可能不是可取的。但是我不明白为什么Stream 让我很困扰。不会是 Traversable .缺少什么结构元素来制作Stream一个 Traversable ?

Answer 1

这是可遍历的，但不是以一种非常有趣的方式。因为它允许 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) ())

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

你不想要pure s根本上，因为您正在构建一个新的 Stream，它具有一种新的内部状态，与您使用的 Stream 无关。而且您已经有办法使用 s您在范围内的值(value):调用 step用它!

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