deniok: (Рыжий)
[personal profile] 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).

Date: 2015-03-30 10:01 am (UTC)
From: [identity profile] sassa-nf.livejournal.com
так на самом деле тут нужно что-то такое:
instance (Traversable t) => Foldable t where
  foldMap = foldMapDefault

Date: 2015-03-30 10:37 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Для этого потребуются FlexibleInstances и UndecidableInstances для объявления и еще и OverlappingInstances, если у нас встретятся прямые реализации представителей Foldable.

Date: 2015-03-30 10:44 am (UTC)
From: [identity profile] sassa-nf.livejournal.com
ну да, но каковы последствия от включения этих фич? что-то перестанет работать?

Date: 2015-03-30 10:58 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Почему-то отсутствует, хотя согласен со здравостью идеи.

Date: 2015-03-30 12:41 pm (UTC)
From: [identity profile] 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) ...

Бамц.

Date: 2015-03-30 10:44 am (UTC)
From: [identity profile] lelf.livejournal.com
Мне лень сейчас искать, но этот proposal давно есть

Date: 2015-03-30 10:51 am (UTC)
From: [identity profile] deni-ok.livejournal.com
Было бы странно, если бы не. Просто сейчас это несколько актуализировалось.

Date: 2015-03-30 11:54 am (UTC)
From: [identity profile] migmit.livejournal.com
Замечательно изложено, почему Monad не должен быть наследником Applicative.

Date: 2015-03-30 12:41 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Что ж ты раньше молчал!

Date: 2015-03-30 12:46 pm (UTC)
From: [identity profile] migmit.livejournal.com
Ну дык хипстота так мечтала, чтобы оно случилось. Должны же мечты сбываться.

Date: 2015-03-30 12:57 pm (UTC)
From: [identity profile] deni-ok.livejournal.com
Кому же, как не тебе, индоктринировать хипстоту правильным образом!

Profile

deniok: (Default)
deniok

April 2017

S M T W T F S
      1
23 45678
9101112131415
16171819202122
23242526272829
30      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 27th, 2017 02:31 am
Powered by Dreamwidth Studios