为什么Applicative-traverse数组不可能？(或者是吗？)

Question

一边琢磨如何最好地映射,即traverse,一个a -> Maybe a-Kleisli在一个未装箱载体,我找了一个现有的实现.显然U.Vector不是Traversable,但它确实提供了一个mapM,Maybe当然工作得很好.

但问题是:Monad真的需要约束吗？好吧,事实证明,甚至盒装向量为Traversable实例作弊:它们实际上只是遍历一个列表,它们从/转换为:

instance Traversable.Traversable Vector where
  {-# INLINE traverse #-}
  traverse f xs = Data.Vector.fromList Applicative.<$> Traversable.traverse f (toList xs)

mono-traversable 对于未装箱的载体也会做同样的事情 ; 在这里,这似乎更加令人毛骨悚然.

现在,如果vector实际上能够将这些被攻击的遍历融合成更有效的形式,我不会感到惊讶,但仍然 - 似乎存在一个根本问题,阻止我们立即在阵列上实现遍历.这种无能是否存在"深层原因"？

Answer 1

在阅读了相关来源vector并尝试使用mapM之后，我认为没有函数并且没有本机的Applicative原因是融合代码。犯罪者属于以下类型：Data.Vector.Unboxed.Vectortraverse :: (Applicative f, Unbox a, Unbox b) -> (a -> f b) -> Vector a -> f (Vector b)Data.Vector.VectortraverseStream

-- Data/Vector/Fusion/Stream/Monadic.hs  Line: 137

-- | Result of taking a single step in a stream
data Step s a where
  Yield :: a -> s -> Step s a
  Skip  :: s -> Step s a
  Done  :: Step s a

-- | Monadic streams
data Stream m a = forall s. Stream (s -> m (Step s a)) s

这是内部使用来实现的mapM。这m将与您最初调用 时的相同Data.Vector.Unboxed.mapM。但由于该流的主干位于m函子内部，因此如果您只有 for 的应用程序，则无法使用它m。

另请参阅vectorGitHub 存储库上的此问题：Weaken constraint on mapM。

免责声明：我真的不知道融合是如何运作的。我不知道如何vector运作。