流设置为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下“拉出”应用f的唯一方法。现在，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成为Traversable缺少什么结构元素