Traversable is Foldable, а мы-то тут при чем?

[deniok]

Размышляю тут вторые сутки над вопросом, что делает контекст Foldable в определении класса типов Traversable

class (Functor t, Foldable t) => Traversable t where
  ...

Технически он не нужен: никакая функциональность Foldable не используется ни при выражении законов Traversable, ни для реализации по умолчанию его методов.

Контекст Functor, кстати, не вызывает вопросов в техническом отношении: он нужен и для формулировки законов (Naturality и Composition для sequenceA и Composition для traverse) и для реализации по умолчанию

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
traverse f = sequenceA . fmap f

Соображения, которыми руководствовались разработчики класса типов Traversable, включая контекст Foldable, заключаются в довольно разумном соображении: любой Traversable является Foldable в том смысле, что имея traverse можно гарантированно и универсально реализовать Foldable с помощью нехитрой машинерии:

foldMap :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMap f = getConst . traverse (Const . f)

(эта функция присутствует в Data.Traversable под именем foldMapDefault).

Тем не менее решение о "наследовании" Traversable от Foldable имеет свою цену. Теперь, объявляя некоторый тип MyType представителем Traversable, я должен сначала сделать его представителем Foldable. Даже если я совсем не собираюсь пользоваться Foldable-интерфейсом, я должен написать затычку

instance Foldable MyType where
    foldMap = foldMapDefault

Это не очень большая цена, но представим, что через пару лет ресерчеры обнаружат, что есть замечательный класс типов SomethingInterestingAndTrendyable и что с помощью traverse можно реализовать его единственную ключевую функцию somethingInterestingAndTrendyImpl. То есть Traversable является (is a :)
SomethingInterestingAndTrendyable и поэтому нужно сделать

class (Functor t, Foldable t, SomethingInterestingAndTrendyable t) => Traversable t where
  ...

а для "удобства" добавить somethingInterestingAndTrendyImplDefault. Не думаю, что мы будем этим очень довольны, хотя технически в каждый наш инстанс Traversable потребуется добавить лишь

instance SomethingInterestingAndTrendyable MyType where
    somethingInterestingAndTrendyImpl = somethingInterestingAndTrendyImplDefault

Но раз уж мы двинулись по этому пути "проявленных наследований" (а мы таки двинулись, см. Monad и Applicative), почему бы не переложить эту деятельность на компилятор? Вроде есть напрашивающееся решение: разрешить в Хаскелле в классах-наследниках задавать методы по умолчанию для классов-родителей. То есть вместо внешней по отношению к классу foldMapDefault и ей подобных разрешить писать

class (Functor t, Foldable t, SomethingInterestingAndTrendyable t) => Traversable t where
    -- default impls for Traversable methods
    traverse = ...
    -- default impls for parents methods
    fmap f = getId . traverse (Id . f)
    foldMap f = getConst . traverse (Const . f)
    somethingInterestingAndTrendyImpl = ...

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

Discuss.

UPD. В комментах сказали, что proposal такой имеется. Нашел, https://wiki.haskell.org/Class_system_extension_proposal, почитал. Мрак. C++ как мы его знаем, практически все прелести разрешения коллизий при множественном наследовании реализации. Нам такого не надо. Вывод: наследование - зло, его надо избегать, долой контекст Foldable из Traversable (и, как мне тут подсказывают, Applicative из Monad).

Comments

[sassa-nf.livejournal.com]

так на самом деле тут нужно что-то такое:

instance (Traversable t) => Foldable t where
  foldMap = foldMapDefault

[deni-ok.livejournal.com]

Для этого потребуются FlexibleInstances и UndecidableInstances для объявления и еще и OverlappingInstances, если у нас встретятся прямые реализации представителей Foldable.

[sassa-nf.livejournal.com]

ну да, но каковы последствия от включения этих фич? что-то перестанет работать?

[deni-ok.livejournal.com]

Почему-то отсутствует, хотя согласен со здравостью идеи.

[deni-ok.livejournal.com]

Ну, кстати, вот пример, когда это плохо:

instance (Traversable t) => Foldable t where
  foldMap = Data.Traversable.foldMapDefault

instance (OtherFoldableChild t) => Foldable t where
  foldMap = Data.OtherFoldableChild.foldMapDefaultOther

f :: (Traversable t, OtherFoldableChild t) => t a -> ...
f xs = ... (foldr (+) 0 xs) ...

Бамц.

[lelf.livejournal.com]

Мне лень сейчас искать, но этот proposal давно есть

[deni-ok.livejournal.com]

Было бы странно, если бы не. Просто сейчас это несколько актуализировалось.

[deni-ok.livejournal.com]

Нашел: https://wiki.haskell.org/Class_system_extension_proposal

[migmit.livejournal.com]

Замечательно изложено, почему Monad не должен быть наследником Applicative.

[deni-ok.livejournal.com]

Что ж ты раньше молчал!

[migmit.livejournal.com]

Ну дык хипстота так мечтала, чтобы оно случилось. Должны же мечты сбываться.

[deni-ok.livejournal.com]

Кому же, как не тебе, индоктринировать хипстоту правильным образом!