Как показать, что тип Haskell заселен одной и только одной функцией?

В этом ответе Габриэль Гонсалес показывает, как показать, что id является единственным жителем forall a. a -> a. Для этого (в самой формальной итерации доказательства) он показывает, что тип изоморфен (), используя лемму Yoneda, и поскольку () имеет в нем только одно значение, то должен быть тип id. Подводя итог, его доказательство таково:

Йонеда говорит:

Functor f => (forall b . (a -> b) -> f b) ~ f a

Если a = () и f = Identity, это становится:

(forall b. (() -> b) -> b) ~ ()

И поскольку тривиально () -> b ~ b, LHS является в основном типом id.

Это похоже на "волшебный трюк", который хорошо работает для id. Я пытаюсь сделать то же самое для более сложного типа функции:

(b -> a) -> (a -> b -> c) -> b -> c

но я не знаю, с чего начать. Я знаю, что он заселен \f g x = g (f x) x, и если вы игнорируете уродливые вещи ⊥/undefined, я уверен, что других функций этого типа нет.

Я не думаю, что трюк Габриэля немедленно применим здесь, каким бы способом я ни выбрал типы. Существуют ли другие подходы (одинаково формальные!), С которыми я могу показать изоморфизм между этим типом и ()?

Ответы

Ответ 1

Вы можете применить секвенциальное исчисление.

Короткий пример, с типом a -> a, мы могли бы построить выражение типа: \x -> (\y -> y) x, но оно все еще нормализуется до \x -> x, которое равно id. В последовательном исчислении система запрещает строить "сокращаемые" доказательства.

Ваш тип (b -> a) -> (a -> b -> c) -> b -> c, неофициально:

f: b -> a
g: a -> b -> c
x: b
--------------
Goal: c

И не так много способов:

apply g

f: b -> a
g: a -> b -> c
x: b
---------------
Subgoal0: a
Subgoal1: b


apply f

f: b -> a
g: a -> b -> c
x: b
---------------
Subgoal0': b
Subgoal1: b


-- For both
apply x

Итак, в конце концов, кажется, что g (f x) x является единственным жителем этого типа.

Подход к лебеде Йонеда должен быть осторожным, чтобы иметь forall x!

 (b -> a) -> (a -> b -> c) -> b -> c
 forall b a. (b -> a) -> b -> forall c. (a -> b -> c) -> c

Давайте сконцентрироваться на конце:

 (a -> b -> c) -> c ~ ((a,b) -> c) -> c

Это изоморфно (a, b), поэтому весь тип сводится к

(b -> a) -> b -> (a, b)

Возьмем f = Compose (Reader b) (,b)

(b -> a) -> f a ~ f b ~ b -> (b,b)

И это уникально, если принять HP a = (a,a) функтор:

b -> (b,b) ~ (() -> b) -> HP b ~ HP () ~ ()

РЕДАКТИРОВАТЬ первый подход чувствует себя немного более волноводным, но чувствует себя как-то более прямым: учитывая ограниченный набор правил, как можно построить доказательство, сколько доказательств мы можем построить?