Почему это невозможно для аппликативно-траверсных массивов? (Или это?)

Рассматривая, как наилучшим образом отображать карту, т.е. traverse, a -> Maybe a -Kleisli над unboxed vector, я искал существующую реализацию. Очевидно, 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 действительно смог сплавить многие из этих взломанных обходов в гораздо более эффективную форму, но все же - кажется, есть фундаментальная проблема, мешающая нам реализовать обход на массив сразу. Есть ли какая-то "глубокая причина" для этой неспособности?

Ответы

Ответ 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: Ослабление ограничения на mapM.

Отказ от ответственности: я не знаю, как работает фьюжн. Я не знаю, как работает vector.