Я думаю, что я нашел ошибку в статье хака для Control.Applicative.
В качестве описания законов прикладного функтора говорится:
class Functor f => Applicative f whereФунктор с применением, обеспечивающий операции вставлять чистые выражения (
pure) и вычислять последовательности и комбинировать их результаты (<*>).Минимальное полное определение должно включать реализацию этих функций, удовлетворяющих следующим законам:
идентичность
pure id <*> v = vСостав
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)гомоморфизм
pure f <*> pure x = pure (f x)взаимообмен
u <*> pure y = pure ($ y) <*> u
(обратите внимание, что это ничего не говорит о fmap), и он утверждает, что эти законы определяют экземпляр Functor:
Как следствие этих законов, экземпляр
Functorдля f будет удовлетворятьfmap f x = pure f <*> x
Я подумал, что сначала это было явно неправильно. То есть, я догадался, что должен существовать конструктор типа t, удовлетворяющий следующим двум условиям:
t является экземпляром Applicative, выполняющим приведенные выше правила, иinstance (Functor t)
(т.е. существуют две различные функции fmap1, fmap2 :: (a->b) -> (t a->t b),
удовлетворяющих законам функтора).Если (и только в том случае, если) выше, то это утверждение должно быть переписано на
Экземпляр Functor для f должен удовлетворять
fmap f x = pure f <*> xКак следствие этих законов, это удовлетворяет законам
Functor.
что явно правильно, независимо от того, правильна ли моя догадка или нет.
Мой вопрос: моя догадка правильная? Существует ли t с требуемыми условиями?
Далее следует объяснение того, что я думал при попытке ответить на этот вопрос сам.
Если бы мы были просто математиками, не заинтересованными в реальном программировании Haskell, мы могли бы легко ответить на этот вопрос утвердительно. Фактически,
t = Identity
newtype Identity a = Identity {runIdentity :: a}
соответствует требованиям 1 и 2 выше (фактически, почти все будет сделано). Действительно, Identity тривиально является экземпляром Functor и Applicative, как определено в Data.Functor.Identity. (Это удовлетворяет fmap f = (pure f <*>).)
Чтобы определить другую "реализацию" instance (Functor f), возьмем для каждого типа a две функции
transf_a, tinv_a :: a -> a
такое, что
tinv_a . transf_a = id
(Это теоретически теоретически легко). Теперь определите
instance (Functor Identity) where
fmap (f :: a->b) = Identity . transf_b . f . tinv_a . runIdentity
Это удовлетворяет законам Functor и является другой реализацией от тривиального, если есть
x :: a
f :: a -> b
такое, что
f x /= transf_b $ f $ tinv_a x
Но совершенно не очевидно, можем ли мы сделать это в Haskell. Есть что-то вроде:
class (Isom a) where
transf, tinv :: a -> a
instance (Isom a) where
transf = id
tinv = id
specialized instance (Isom Bool) where
transf = not
tinv = not
возможно в Haskell?
Я забыл написать что-то очень важное. Я признаю Control.Applicative как часть базового пакета GHC, поэтому меня также интересует, изменяется ли ответ на мой вопрос с любыми языковыми расширениями GHC, такими как FlexibleInstances или OverlappingInstances, которые я пока не понимаю.
Любой тип в Haskell может иметь не более одного экземпляра Functor, поэтому ваше предположение неверно: ни для какого типа t (независимо от того, является ли он экземпляром Applicative) не может существовать две разные реализации instance (Functor t), Видеть: http://article.gmane.org/gmane.comp.lang.haskell.libraries/15384
Это свойство типа a -> a состоит только из двух его обитателей: id :: a -> a (определяется как id x = x) и bottom :: a -> a, определенных как bottom = error "Infinite loop.".
Если мы ограничимся только первым случаем как "разумным", мы приходим к важной математической теореме, которая заключается в том, что существует не более одной функции fmap типа forall a. forall b. (a -> b) -> f a -> f b, удовлетворяющей fmap id = id и fmap f . fmap g = fmap (f . g),
Если мы этого не сделаем, тогда вы правы, у нас есть один случай, когда fmap = undefined, а другой - fmap = (<*>) . pure. Но это немного дрянной.