Почему функции делают Vector экземпляром Functor, Monad, Applicative, Alternative, Foldable и Traversable slow?

В списке изменений для версии 0.8 vector указано следующее изменение с предупреждением:

Функтор, Монад, Аппликативный, Альтернативный, Складной и Траверсируемый экземпляры для вложенных векторов (ПРЕДУПРЕЖДЕНИЕ: они, как правило, медленны и только для полноты).

Может ли кто-нибудь объяснить, почему это так? Это просто нормальная стоимость специализации по типу или интереснее?

Обновление:. Рассматривая некоторые конкретные примеры, можно увидеть, например:

instance Foldable.Foldable Vector where
  {-# INLINE foldr #-}
  foldr = foldr

и аналогично для других складок. Означает ли это, что сложение в целом Vector замедляется? Если нет, что делает неспециализированную складку достаточно медленной, чтобы гарантировать предупреждение?

Ответ 1

Я отправил исходный набор этих экземпляров Роману полтора года назад и с тех пор поддерживал векторные экземпляры. (Мне пришлось удалить эти экземпляры из векторных экземпляров, как только они перешли на вектор, и теперь поддерживают его исключительно для действительно экзотических вещей). Его беспокойство заключалось в том, что если люди использовали эти экземпляры полиморфно, тогда ПРАВИЛА, которые заставляют Векторы сливаться, не могут срабатывать, если полиморфная функция не вставлена и мономорфна.

Они существуют, потому что не каждый бит кода на планете является специфичным для Vector, и даже тогда полезно иногда использовать общие имена.

Медленное здесь относительное. В худшем случае они выполняются, как и все остальные, сгибы, привязки и т.д., Но Роман берет каждое отдельное значение в виде бокса как личное оскорбление.:)

Ответ 2

Я просто быстро посмотрел на исходный код, и реализации не выглядят слишком медленными. Я утверждаю, что авторы добавили это предупреждение, потому что, когда вы пишете программу в монаде Vector, вы работаете с такой высокоуровневой точки зрения, что легко забыть, что каждый >>= есть, в факт, a concatMap, который, как правило, медленный.

Другое дело: Vector особенно быстрый для распакованных типов. Таким образом, пользователь может быть привлечен к использованию нотации монады (для удобства), в то время как он должен фактически использовать unboxed type (для скорости).