Складной против Traversable

Question

Во время учебы Applicative глубже я пришел к Traversable, Хотя я уже знала Foldable от LYHGG я еще не видел первого, поэтому я начал читать вики на Haskell о Traversable.

Читая это, я понял, почему Foldable.fold параллельно Traversable.sequenceA а также Foldable.foldMap параллельно Traversable.traverse,

Я также видел, что каждый Traversable также Foldable и Functor, а также sequenceA а также traversal иметь реализацию по умолчанию в терминах друг друга:

traverse f = sequenceA . fmap f
sequenceA = traverse id

Итак, как я видел в LYHGG, что foldMap минимальное полное определение для Foldable Я думал, что это параллельно traverse, так fold (который параллелен sequenceA) было бы также минимальным полным определением (но это не так)... Foldable это не Functor лайк Traversable есть, поэтому мы не можем применить это:

foldMap f = fold . fmap f
fold = foldMap id -- this is ok

Почему не каждый Foldable Functor и что будет экземпляром Foldable это на самом деле не Functor?

Answer 1

Как говорит Dfeuer, Set хороший пример Foldable это не Functor,

Рассмотрим тип Set.map:

map :: Ord b => (a -> b) -> Set a -> Set b

Обратите внимание, что это почти fmap, но требует дополнительного Ord b ограничение. Поскольку у вас есть это ограничение, его нельзя сделать экземпляром Functor,

Обратите внимание, что Set не является функтором на Haskell, даже с этим ограничением. Учитывая умно настроенный Eq случаи, когда мы можем нарушить закон, fmap f . fmap g === fmap (f . g), Смотрите этот вопрос переполнения стека для дальнейшего обсуждения.

Как отмечено там, Set является (эндо) функтором в "подкатегории Hask"с упорядоченными типами в качестве наборов и с сохраняющими порядок отображениями в качестве морфизмов.

Так что даже если это не очевидно, тот факт, что мы не можем сделать Set Функтор на самом деле намекает на настоящую математическую проблему, а не только на ограничение нашего механизма типов.