performance - 为什么不能应用遍历数组？ (或者是吗？)

Question

在思考如何最好地映射时，即traverse , 一个 a -> Maybe a -Kleisli 通过 unboxed vector ，我寻找了一个现有的实现。显然 U.Vector不是 Traversable , 但是 it does supply a mapM ，对于 Maybe当然工作得很好。

但问题是:Monad真的需要约束吗？好吧，事实证明，即使 boxed vectors cheat for the Traversable instance :他们真的只是遍历一个列表，他们从/转换为:

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

mono-traversable does the same thing also for unboxed vectors ;在这里，这在性能方面似乎更加可怕。

现在，如果 vector 我不会感到惊讶实际上能够将许多这些被黑客入侵的遍历融合成一种更有效的形式，但是 - 似乎仍然存在一个基本问题，阻止我们立即在数组上实现遍历。这种无能有什么“深层原因”吗？

Answer 1

看完vector的相关出处并试图制作 mapM与 Applicative 合作我觉得原因Data.Vector.Unboxed.Vector没有 traverse :: (Applicative f, Unbox a, Unbox b) -> (a -> f b) -> Vector a -> f (Vector b)功能和Data.Vector.Vector没有原生 traverse是融合代码。违规者如下Stream类型:

-- 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里面。仿函数，如果您只有 m 的应用程序，则无法使用它.

另请参阅 vector 上的此问题GitHub 仓库: Weaken constraint on mapM .

免责声明:我真的不知道融合是如何工作的。不知道怎么 vector作品。