Разрешение типа `f = f (<*>) pure`

Question

Недавно я заметил, что юмористически liftA можно записать как

liftA (<*>) pure

Я подумал, что это аккуратно, и как шутка, я подумал, что сделаю новое «определение» liftA основываясь на этом свойстве:

f = f (<*>) pure

Теперь я ожидал, что это будет что-то типа того же типа, что и liftA, который просто никогда не останавливается.Однако он не компилируется.

• Occurs check: cannot construct the infinite type:
    t ~ (f (a -> b) -> f a -> f b) -> (a1 -> f1 a1) -> t
• In the expression: f (<*>) pure
  In an equation for ‘f’: f = f (<*>) pure
• Relevant bindings include
    f :: (f (a -> b) -> f a -> f b) -> (a1 -> f1 a1) -> t
      (bound at liftA.hs:2:1)

Это кажется разумным, я вижу, как у компилятора есть проблема.Однако все становится немного странным, потому что, когда я добавляю аннотацию:

f :: Applicative f => (a -> b) -> f a -> f b
f = f (<*>) pure

Она неожиданно компилируется.

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

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

Answer 1

Путаница вызвана классами типов Haskell и тем фактом, что функции from-fixed-type являются экземпляром Applicative (он же монада читателя).Это станет более понятным, если вы напишите это со специализированной версией:

type Reader a b = a -> b

fmapFn :: (a -> b) -> Reader c a -> Reader c b
fmapFn = fmap
    -- ≡ liftA
    -- ≡ (.)

fmap' :: Applicative f => (a -> b) -> f a -> f b
fmap' = fmapFn (<*>) pure
      ≡ (<*>) . pure
      ≡ \φ -> (<*>) (pure φ)
      ≡ \φ fa -> pure φ <*> fa

И на этом этапе требуется применимый закон

fmap f x = pure f <*> x

, поэтому

 fmap' ≡ \φ fa -> fmap φ fa
       ≡ fmap

1012 * Дух *.Но дело в том, что в определении fmap' = fmap' (<*>) pure (<*>) и pure принадлежат функтору, для которого вы хотите, чтобы это в конечном итоге работало, но fmap' вы , используя на самом деле всегдапринадлежит функтору функции.Это нормально в Haskell: определение в конце концов является полиморфным, так что если верхний уровень знает, как это сделать для всех функторов, то вы, безусловно, можете также использовать его для функтора функции.(Оставляя в стороне вопрос о нетерминации из-за циклической зависимости ...) Однако, поскольку вы определяете его в виде fmap' = ..., , ограничение мономорфизма включается: если вы пишете fmap' = fmap' (<*>) pure без подписи на верхнем уровне, компилятор пытается найти конкретный тип, для которого это должно работать, в частности один конкретный функтор.Но какой бы конкретный тип вы ни выбрали, тогда он будет отличаться от fmapFn, который вы пытаетесь использовать сами.Таким образом, это определение компилируется только с явной сигнатурой, которая заставляет его быть полиморфным (или, альтернативно, с флагом -XNoMonomorphismRestriction, который заставляет компилятор выбирать полиморфный тип без явной инструкции) .

^{РЕДАКТИРОВАТЬ} Удивительно, но оказывается, что не ограничение мономорфизма, которое пытается сделать тип менее полиморфным, чем необходимо.Чтобы выяснить, что это такое, давайте попробуем найти более простой пример с той же проблемой.Первая попытка:

fromFloat :: RealFrac a => Float -> a
toFloat :: RealFrac a => a -> Float
fromFloat = realToFrac
toFloat   = realToFrac

s = fromFloat . s . toFloat

(я выбрал Float, потому что это не тип default, который компилятор может выбрать сам.)
Получается, что это компилируется просто отлично, но вместо большинстваобщий тип

s' :: (RealFrac a, RealFrac b) => a -> b
s' = fromFloat . s' . toFloat

он просто выбирает более простой

s :: Float -> Float

... независимо от того, включено ли ограничение мономорфизма. Почему? Не знаю;Я нашел бы этот интересный вопрос, чтобы задать.

Answer 2

Это потому, что f, используемая в теле определения f, имеет тип, отличный от определения.Это называется полиморфной рекурсией, и Haskell допускает это только если вы предоставляете сигнатуру типа.Причина, по которой требуется подпись типа, заключается в том, что вывод типа для полиморфной рекурсии в общем случае неразрешим.