Продолжение представления стиля представления типов

Предположим, что у нас есть монада, определяемая return, (>>=) и набором законов. Существует тип данных

newtype C m a = C { unC ∷ forall r. (a → m r) → m r }

также известный как Codensity. C m a ≅ m a, учитывая, что m является Monad, т.е. мы можем написать две функции to ∷ Monad m ⇒ m a → C m a и from ∷ Monad m ⇒ C m a → m a

to ∷ Monad m ⇒ m a → C m a
to t = C $ \f → t >>= f

from ∷ Monad m ⇒ C m a → m a
from = ($ return) . unC

и покажите, что to ∘ from ≡ id и from ∘ to ≡ id с помощью эквациональных рассуждений, например:

from . to =                                  -- by definition of `(.)'
  \x → from (to x) =                         -- by definition of `to'
  \x → from (C $ \f → x >>= f) =             -- by definition of `from'
  \x → ($ return) (unC (C $ \f → x >>= f)) = -- unC . C ≡ id
  \x → ($ return) (\f → x >>= f) =           -- β-reduce
  \x → x >>= return =                        -- right identity law
  \x → x =                                   -- by definition of `id'
  id

Пока все хорошо. Мои вопросы

  • Учитывая тип и совокупность законов, как мы построим соответствующее изоморфное представление CPS?
  • Является ли это представление уникальным (я бы предположил, нет)?
  • Если это не уникально, всегда есть самый "простой" (в числе → например:)) один?

Ответы

Ответ 1

Нет такой кодировки Unique

Как вы задали вопрос, ответ, очевидно, "нет" 

a = forall r. (a -> r) -> r
a = forall s. ((forall r. (a -> r) -> r) -> s) -> s

относительно какой кодировки является наименьшей... ну, базовый тип почти наверняка!

Codensity может быть не тем, что вы хотите

Чем больше, хотя Codensity увлекательна, я не считаю, что он изоморфен базовому типу. from . to = id - это простое направление.

to . from
  = \x -> to (from x)
  = \x -> C $ \f -> (from x) >>= f
  = \x -> C $ \f -> (unC x return) >>= f
  = \(C g) -> C $ \f -> (g return) >>= f

но потом вы застряли. То же самое происходит, когда вы пытаетесь доказать a = forall r. (a -> r) -> r, но вы получаете "теорему бесплатно" (возможно, это можно сделать без этого, но свободная теорема упрощает). Я не знаю соответствующего аргумента для Codensity, и то, что большинство документов, которые я прочитал, является скорее тем, что он сохраняет >>= и return, то есть, если вы только создаете свой C m a, используя монадические операции и то, что вы называете to тогда вызов to . from является тождественным.

Если мы достаточно стараемся, мы можем даже придумать встречный пример изоморфизма

evil :: C Maybe Int
evil = C $ \h -> case h 1 of
                      Nothing -> h 2
                      Just x  -> Nothing


 to . from $ evil
  = (\(C g) -> C $ \f -> (g return) >>= f) evil
  = C $ \f -> ((\h -> case h 1 of
                      Nothing -> h 2
                      Just x  -> Nothing) return) >>= f
  = C $ \f -> Nothing >>= f

так они одинаковы?

test 1 = Nothing
test n = Just n

unC evil test
  = Just 2
unC (C $ \f -> Nothing >>= f) test
  = Nothing >>= test
  = Nothing

Возможно, я ошиблась в этом деле. Я действительно не проверял его, но достаточно сказать, что сейчас я не думаю, что C m a = m a

Другой вид CPS

Все данные могут быть закодированы как нетипизированные лямбда-функции, свойство, обнаруженное Церковью около 70 лет назад. Часто мы говорим о структурах данных "Церковного кодирования", хотя Олег предположил, что вместо этого, по крайней мере, в типизированной обстановке, мы должны поговорить о кодировании "Boehm-Beraducci". Независимо от того, что вы называете, идея

(a,b) = forall r. (a -> b -> r) -> r
Either a b = forall r. (a -> r) -> (b -> r) -> r

по крайней мере до быстрых и слабых рассуждений. Должно быть очевидно, что эта кодировка обеспечивает способ кодирования любого ADT как типа System F. Это также показывает способ реализации функциональных языков: рассматривать все как замыкания под капотом, а сопоставление образцов просто реализуется как функциональное приложение.

Фактически, система F даже имеет способ кодирования экзистенциальных типов как универсальных типов

exists a. f a = forall r. (forall a'. f a' -> r) -> r

который оказывается очень важным тождеством. Помимо всего прочего, это помогает нам задуматься о связи между типом вывода для более высоких типов рангов и для экзистенциальных типов. Поскольку вывод типа разрешимо до типов ранга 2, вывод типа также разрешима в системе с универсалями 1 и экзистенциальными единицами. Поскольку экзистенциальная квантификация является основой для модулей, это важный материал.