Есть ли что-то, что мы теряем с MonoFoldable?

Question

MonoFoldable в моно-перемещаемом пакете, кажется, в состоянии реализовать все обычные складные контейнеры и многое другое, например, такие вещи, как Bytestring и однородные кортежи могут быть сделаны MonoFoldable но нет Foldable, Мой вопрос, мы что-нибудь теряем от MonoFoldable что у нас нет в FoldableКроме того, что требуются некоторые расширенные функции GHC, что делает его немного более сложным для авторов экземпляров и, возможно, получение более ужасных сообщений об ошибках?

Например, есть ли код, который при использовании Foldable компилируется но с MonoFoldable типы не выведены например? Или что-нибудь еще, что делает клиент (не код, пишущий экземпляр) значительно проще с Foldable чем MonoFoldable?

Answer 1

Самая большая вещь, которую вы теряете - это полиморфная рекурсия. Посмотрите на списки Окасаки:

data Cat q a = Empty | Cat a (q (Cat q a))

Мы можем написать

instance Foldable q => Foldable (Cat q) where
   foldMap _ Empty = mempty
   foldMap f (Cat a q) = f a <> foldMap (foldMap f) q

Но если мы попытаемся использовать только MonoFoldable, застряли. Необходимое ограничение экземпляра на q, forall x . (MonoFoldable (q x), Element (q x) ~ x), не может быть выражено каким-либо обычным способом. Вероятно, можно обойти это с Data.Constraint.Forall, но это становится довольно уродливым.

---

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

osum :: (MonoFoldable c, Num (Element c)) => c -> Element c

кажется мне хуже

sum :: (Foldable f, Num n) => f n -> n

Исправить несложно: изменить определение MonoFoldable в

class (a ~ Element c) => MonoFoldable' a c where ...

что бы дать вам

osum' :: (MonoFoldable' n c, Num n) => c -> n

В качестве альтернативы, лом Element в целом, и использовать

class MonoFoldable'' a c | c -> a

который дает аналогично упрощенную подпись.

К сожалению, Майкл Снойман не согласен со мной по этому вопросу. Я могу написать свой собственный пакет-обёртку, чтобы раскрыть свой предпочтительный API.

Answer 2

Вы теряете параметричность.

Тип (Foldable f) => f a -> [a] предоставляет значительно отличающиеся гарантии, чем (MonoFoldable c) => c -> [Element c],

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