Wie zeige ich, dass ein Haskell-Typ von einer einzigen Funktion bewohnt wird?

Question

In this answer zeigt Gabriel Gonzalez, wie man zeigt, dass id der einzige Einwohner von forall a. a -> a ist. Um dies zu tun (in der formalsten Iteration des Beweises), zeigt er, dass der Typ isomorph zu () unter Verwendung der Yoneda lemma ist, und da () nur einen Wert enthält, so muss der Typ id sein. Zusammengefasst ist sein Beweis wie folgt aus:

Yoneda sagt:

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

Wenn a =() und f = Identity wird daraus:

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

Und da trivialer () -> b ~ b, die LHS ist im Grunde die Art von id.

Das fühlt sich an wie ein "magischer Trick", der gut funktioniert für id. Ich versuche, dasselbe für eine komplexere Funktion zu tun:

aber ich habe keine Ahnung, wo ich anfangen soll. Ich weiß, dass es von \f g x = g (f x) x bewohnt wird, und wenn Sie hässliche ⊥/undefined Zeug ignorieren, bin ich ziemlich sicher, dass es keine anderen Funktionen dieses Typs gibt.

Ich glaube nicht, Gabriels Trick wird sofort gelten hier, egal wie ich die Typen auswählen. Gibt es andere Ansätze (die genauso formal sind), mit denen ich den Isomorphismus zwischen diesem Typ und () zeigen kann?

Answer 1

Sie können sequent calculus anwenden.

Kurz Beispiel mit Typ a -> a, könnten wir bauen Begriff wie: \x -> (\y -> y) x, aber das normalisiert noch \x -> x die id ist. Im sequentiellen Kalkül verbietet das System, "reduzierbare" Beweise zu konstruieren.

Ihre Art ist (b -> a) -> (a -> b -> c) -> b -> c, informell:

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

Und es gibt nicht viele Möglichkeiten, um fortzufahren:

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 

Also am Ende, so scheint, dass g (f x) x ist der einzige Bewohner dieses Typs .

---

Yoneda Lemma Ansatz, müssen tatsächlich haben forall x vorsichtig sein!

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

Let Konzentrat am Ende:

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

Das isomorph (a, b) ist, so ganze Art reduziert sich auf

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

Nehmen f = Compose (Reader b) (,b)

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

Und das ist einzigartig, indem sie HP a = (a,a) Funktors:

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

---

EDIT der erste Ansatz ein bisschen mehr von Hand wellig fühlt, fühlt sich aber irgendwie direkterer: die eingeschränkte Menge von Regeln gegeben, wie der Beweis kann konstruiert werden, wie viele Beweise können wir konstruieren?