Поднятие функции высшего порядка в Хаскеле - PullRequest
18 голосов
/ 11 февраля 2012

Я пытаюсь построить функцию типа:

liftSumthing :: ((a -> m b) -> m b) -> (a -> t m b) -> t m b

где t - монадный трансформатор. В частности, я заинтересован в этом:

liftSumthingIO :: MonadIO m => ((a -> IO b) -> IO b) -> (a -> m b) -> m b

Я возился с волшебными библиотеками Хаскелла, но безрезультатно. Как я могу получить это правильно, а может, где-то есть готовое решение, которого я не нашел?

1 Ответ

24 голосов
/ 12 февраля 2012

Это нельзя сделать в общем случае для всех экземпляров MonadIO из-за типа IO в отрицательной позиции.Есть некоторые библиотеки на hackage, которые делают это для определенных случаев ( monad-control , monad-peel ), но были некоторые споры по поводу того, насколько они семантически здоровы, особенно в отношениикак они обрабатывают исключения и подобные странные IO y вещи.

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

Интуиция, лежащая в основе подтипов, заключается в том, что "a - это подтип b (который я напишу a <= b), когда можно использовать aгде-нибудь b ожидалось вместо этого ".Выбор подтипа прост во многих случаях;для продуктов (a1, a2) <= (b1, b2) всякий раз, например, a1 <= b1 и a2 <= b2, что является очень простым правилом.Но есть несколько хитрых случаев;например, когда мы должны решить, что a1 -> a2 <= b1 -> b2?

Ну, у нас есть функция f :: a1 -> a2 и контекст, ожидающий функцию типа b1 -> b2.Таким образом, контекст будет использовать возвращаемое значение f, как если бы оно было b2, поэтому мы должны требовать, чтобы a2 <= b2.Хитрость в том, что контекст будет снабжать f b1, хотя f будет использовать его, как если бы это был a1.Следовательно, мы должны потребовать b1 <= a1 - что оглядывается назад от того, что вы можете догадаться!Мы говорим, что a2 и b2 являются "ковариантными" или встречаются в "положительной позиции", а a1 и b1 являются "контрвариантными" или встречаются в "отрицательной позиции".

(Отбросим: почему «положительный» и «отрицательный»? Он мотивирован умножением. Рассмотрим два типа:

f1 :: ((a1 -> b1) -> c1) -> (d1 -> e1)
f2 :: ((a2 -> b2) -> c2) -> (d2 -> e2)

Когда тип f1 должен быть подтипом f2 's type? Я констатирую эти факты (упражнение: проверьте это, используя приведенное выше правило):

  • У нас должно быть e1 <= e2.
  • У нас должно быть d2 <= d1.
  • У нас должно быть c2 <= c1.
  • У нас должно быть b1 <= b2.
  • У нас должно быть a2 <= a1.

e1 находится вположительная позиция в d1 -> e1, которая в свою очередь находится в положительной позиции в типе f1, более того, e1 находится в положительной позиции в типе f1 в целом (поскольку она ковариантна, согласнофакт выше). Его позиция во всем термине является произведением его позиции в каждом подтерме: положительный * положительный = положительный. Точно так же d1 находится в отрицательной позиции in d1 -> e1, который находится в положительной позиции во всем типе.отрицательный * положительный = отрицательный, а переменные d действительно противоречивы.b1 находится в положительной позиции в типе a1 -> b1, который находится в отрицательной позиции в (a1 -> b1) -> c1, который находится в отрицательной позиции во всем типе.положительный * отрицательный * отрицательный = положительный, и он ковариантен.Вы поняли.)

Теперь давайте взглянем на класс MonadIO:

class Monad m => MonadIO m where
    liftIO :: IO a -> m a

Мы можем рассматривать это как явное объявление подтипа: мы даем способсделать IO a подтипом m a для некоторого бетона m.Сразу же мы знаем, что можем принять любое значение с конструкторами IO в положительных позициях и превратить их в m с.Но это все: у нас нет способа превратить отрицательные IO конструкторы в m s - для этого нам нужен более интересный класс.

...