Почему экземпляры соответствуют только их головам?

Question

Начну с конкретной проблемы (ребята из Stackru, как это). Скажем, вы определяете простой тип

data T a = T a

Этот тип Functor, Applicative и Monad, Игнорируя автоматическое получение, чтобы получить эти экземпляры, вы должны написать каждый из них, даже если Monad подразумевает Applicative, что подразумевает Functor, Более того, я мог бы определить такой класс

class Wrapper f where
    wrap   :: a -> f a
    unwrap :: f a -> a

Это довольно сильное условие, и оно определенно подразумевает Monad, но я не могу написать

instance Wrapper f => Monad f where
    return = wrap
    fa >>= f = f $ unwrap fa

потому что это по какой-то причине означает, что "все Monad (каждый f), только если это Wrapperвместо того, чтобы Wrapper это Monad".

Точно так же вы не можете определить Monad a => Applicative a а также Applicative a => Functor a экземпляров.

Еще одна вещь, которую вы не можете сделать (которая, вероятно, связана, я действительно не знаю), - это чтобы один класс был суперклассом другого и предоставлял реализацию подкласса по умолчанию. Конечно, это здорово, что class Applicative a => Monad a, но это гораздо менее здорово, что я все еще должен определить Applicative экземпляр, прежде чем я могу определить Monad один.

Это не напыщенная речь. Я много писал, потому что иначе это бы быстро пометили как "слишком широкое" или "неясное". Вопрос сводится к названию. Я знаю (по крайней мере, я почти уверен), что для этого есть некоторая теоретическая причина, поэтому мне интересно, какие именно здесь преимущества.

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

Дополнение: я подозреваю, что одним из ответов может быть что-то вроде "Что если мой тип Wrapper, но я не хочу использовать Monad экземпляр, что это подразумевает?". На этот вопрос я спрашиваю, почему компилятор не может просто выбрать самый конкретный? Если есть instance Monad MyType, конечно, это более конкретно, чем instance Wrapper a => Monad a,

Answer 1

Здесь собрано много вопросов. Но давайте возьмем их по одному.

Первый: почему компилятор не смотрит на контексты экземпляров при выборе того, какой экземпляр использовать? Это необходимо для эффективного поиска экземпляров. Если вам требуется, чтобы компилятор рассматривал только экземпляры, заголовки экземпляров которых удовлетворены, вы, по сути, в конечном итоге потребовали, чтобы ваш компилятор выполнил поиск с обратным отслеживанием среди всех возможных экземпляров, после чего вы реализовали 90% Prolog. Если, с другой стороны, вы принимаете позицию (как это делает Haskell), что вы смотрите только на заголовки экземпляров при выборе экземпляра для использования, а затем просто применяете контекст экземпляра, обратного отслеживания нет: в каждый момент времени есть только один выбор, который вы можете сделать.

Далее: почему вы не можете сделать один класс суперклассом другого и обеспечить реализацию подкласса по умолчанию? Для этого ограничения нет фундаментальной причины, поэтому GHC предлагает эту функцию в качестве расширения. Вы могли бы написать что-то вроде этого:

{-# LANGUAGE DefaultSignatures #-}
class Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

    default pure :: Monad f => a -> f a
    default (<*>) :: Monad f => f (a -> b) -> f a -> f b
    pure = return
    (<*>) = ap

Затем, как только вы предоставили instance Monad M where ...Вы могли бы просто написать instance Applicative M без where пункт и имейте это просто работа. Я действительно не знаю, почему это не было сделано в стандартной библиотеке.

И последнее: почему компилятор не может разрешить много экземпляров и просто выбрать наиболее конкретный? Ответ на этот вопрос является своего рода сочетанием двух предыдущих: есть очень веские фундаментальные причины, по которым это не работает, но GHC, тем не менее, предлагает расширение, которое делает это. Основная причина, по которой это не работает, состоит в том, что наиболее конкретный экземпляр для данного значения не может быть известен до времени выполнения. Ответ GHC на это - для полиморфных значений выбрать наиболее конкретную, совместимую с полным доступным полиморфизмом. Если позже эта вещь станет мономорфизированной, ну, для вас это слишком плохо. Результатом этого является то, что некоторые функции могут работать с некоторыми данными с одним экземпляром, а другие могут работать с теми же данными с другим экземпляром; это может привести к очень тонким ошибкам. Если после всего этого обсуждения вы по-прежнему считаете это хорошей идеей и отказываетесь учиться на чужих ошибках, вы можете включить IncoherentInstances,

Я думаю, что это охватывает все вопросы.

Answer 2

Согласованность и раздельная компиляция.

Если у нас есть два экземпляра, головы которых совпадают, но имеют разные ограничения, скажем:

-- File: Foo.hs

instance Monad m => Applicative m
instance            Applicative Foo

Тогда либо это действительный код, производящий Applicative экземпляр для Fooили это ошибка, создающая два разных Applicative случаи для Foo, Какой это зависит от того, существует ли экземпляр монады дляFoo, Это проблема, потому что трудно гарантировать, что знания о Monad Foo Hold сделает это компилятору, когда он компилирует этот модуль.

Другой модуль (скажем, Bar.hs) может произвести Monad экземпляр для Foo, Если Foo.hs не импортирует этот модуль (даже косвенно), тогда как знать компилятору? Хуже того, мы можем изменить, является ли это ошибкой или допустимым определением, изменив, добавим ли мы позже Bar.hs в финальной программе или нет!

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

Единственный способ избежать этого - никогда не заставлять GHC принимать решения на основе негативной информации. Вы не можете выбрать экземпляр на основании отсутствия другого экземпляра.

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

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

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