时间戳

首页 > 解决方案 > Stream 成为可遍历的实例

haskell - Stream 成为可遍历的实例

问题描述

该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很自然地是Functorand的一个实例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)），而在这里我需要完全相反的，可以<*>这么说。

拥有一个Traversable实例对我的任何努力都不是至关重要的，从性能的角度来看，它甚至可能不是可取的。但让我感到困扰的是，我并没有真正理解为什么Stream不会Traversable。Stream制作a缺少什么结构元素Traversable？

标签： haskellstreamapplicativetraversable

解决方案

这是可遍历的，但不是以一种非常有趣的方式。因为它也允许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你在范围内的价值：step用它来调用！

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

推荐阅读