Czy istnieje sposób realizacji funkcji typu ((a -> b) -> b) -> Albo ab?

Propozycje (P -> Q) -> Qi P \/ Qsą równoważne.

Czy istnieje sposób, aby być świadkiem tej równoważności w Haskell:

from :: Either a b -> ((a -> b) -> b)
from x = case x of
         Left a -> \f -> f a
         Right b -> \f -> b

to :: ((a -> b) -> b) -> Either a b
to = ???

takie, że

from . to = idi to . from = id?

Propozycje (P -> Q) -> Qi P \/ Qsą równoważne.

Dotyczy to logiki klasycznej, ale nie logiki konstruktywnej.

W logice konstruktywnej nie mamy prawa wykluczonego środka , tzn. Nie możemy rozpocząć myślenia od „albo P jest prawdą, albo P nie jest prawdą”.

Klasycznie rozumujemy:

• jeśli P jest prawdziwe (tzn. mamy ( x :: P)), to zwróć Left x.
• jeśli P jest fałszem, to w Haskell mówimy, że mielibyśmy nx :: P -> Voidfunkcję. Następnie absurd . nx :: P -> Q(możemy szczyt wszelkiego rodzaju, bierzemy Q) i wywołać dane f :: (P -> Q) -> Q)z absurd . nxaby uzyskać wartość typu Q.

Problem polegający na tym, że nie ma ogólnej funkcji typu:

lem :: forall p. Either p (p -> Void)

Dla niektórych konkretnych typów istnieją, np. Są Boolzamieszkane, więc możemy pisać

lemBool :: Either Bool (Bool -> Void)
lemBool = Left True -- arbitrary choice

ale ogólnie nie możemy.

Nie, to niemożliwe. Rozważ szczególny przypadek, w którym Q = Void.

Either P Qjest wtedy Either P Void, co jest izomorficzne P.

iso :: P -> Either P Void
iso = Left

iso_inv :: Either P Void -> P
iso_inv (Left p)  = p
iso_inv (Right q) = absurd q

Stąd, gdybyśmy mieli pojęcie funkcji

impossible :: ((P -> Void) -> Void) -> Either P Void

moglibyśmy również mieć termin

impossible2 :: ((P -> Void) -> Void) -> P
impossible2 = iso_inv . impossible

Według korespondencji Curry-Howarda byłaby to tautologia w intuicyjnej logice:

((P -> False) -> False) -> P

Ale powyższe to eliminacja podwójnej negacji, o której wiadomo, że jest niemożliwa do udowodnienia w logice intuicyjnej - stąd sprzeczność. (Fakt, że możemy to udowodnić w logice klasycznej, nie ma znaczenia).

(Uwaga końcowa: zakłada się, że nasz program Haskell zakończy się. Oczywiście, używając nieskończonej rekurencji undefinedi podobnych sposobów, aby faktycznie uniknąć wyniku, możemy zamieszkać w Haskell dowolnego typu).

Nie, nie jest to możliwe, ale jest nieco subtelne. Problem polega na tym, że zmienne typu ai bsą powszechnie ilościowo.

to :: ((a -> b) -> b) -> Either a b
to f = ...

ai bsą powszechnie obliczane ilościowo. Dzwoniący wybiera, jakiego rodzaju są, więc nie można po prostu utworzyć wartości żadnego z tych typów. Oznacza to, że nie można po prostu utworzyć wartości typu Either a b, ignorując argument f. Ale używanie fjest również niemożliwe. Bez wiedzy o typach ai typach bnie można utworzyć wartości typu, którą a -> bnależy przekazać f. Po prostu nie ma wystarczającej ilości informacji, gdy typy są powszechnie kwantyfikowane.

Jeśli chodzi o to, dlaczego izomorfizm nie działa w Haskell - czy jesteś pewien, że te twierdzenia są równoważne w konstruktywnej intuicyjnej logice? Haskell nie implementuje klasycznej logiki dedukcyjnej.

Jak zauważyli inni, jest to niemożliwe, ponieważ nie mamy prawa wykluczonego środka. Pozwól, że przejdę przez to nieco bardziej wyraźnie. Załóżmy, że mamy

bogus :: ((a -> b) -> b) -> Either a b

i ustawiamy b ~ Void. Potem dostaniemy

-- chi calls this `impossible2`.
double_neg_elim :: ((a -> Void) -> Void) -> a
bouble_neg_elim f = case bogus f of
             Left a -> a
             Right v -> absurd v

Teraz udowodnijmy podwójną negację prawa wykluczonego środka w odniesieniu do konkretnego zdania .

nnlem :: forall a. (Either a (a -> Void) -> Void) -> Void
nnlem f = not_not_a not_a
  where
    not_a :: a -> Void
    not_a = f . Left

    not_not_a :: (a -> Void) -> Void
    not_not_a = f . Right

Więc teraz

lem :: Either a (a -> Void)
lem = double_neg_elim nnlem

lemnajwyraźniej nie może istnieć, ponieważ amoże zakodować twierdzenie, że każda konfiguracja maszyny Turinga, którą wybiorę, zostanie zatrzymana.

Sprawdźmy, czy lemto wystarczy:

bogus :: forall a b. ((a -> b) -> b) -> Either a b
bogus f = case lem @a of
  Left a -> Left a
  Right na -> Right $ f (absurd . na)

Nie mam pojęcia, czy jest to poprawne logicznie, czy co oznacza dla twojej równoważności, ale tak, możliwe jest napisanie takiej funkcji w Haskell.

Aby zbudować Either a b, potrzebujemy albo wartości, aalbo bwartości. Nie mamy żadnego sposobu na skonstruowanie awartości, ale mamy funkcję, która zwraca funkcję b, którą moglibyśmy wywołać. Aby to zrobić, musimy podać funkcję, która konwertuje an ana a b, ale biorąc pod uwagę, że typy nie są znane, moglibyśmy w najlepszym wypadku stworzyć funkcję, która zwraca stałą b. Aby uzyskać tę bwartość, nie możemy jej skonstruować w żaden inny sposób niż wcześniej, więc staje się to okrągłym rozumowaniem - i możemy to rozwiązać, po prostu tworząc punkt stały :

to :: ((a -> b) -> b) -> Either a b
to f = let x = f (\_ -> x) in Right x