Dlaczego używamy fałd do kodowania typów danych jako funkcji?

Question

Dlaczego używamy fałd do kodowania typów danych jako funkcji?

A dokładniej, dlaczego używamy foldr do kodowania list i iteracji do kodowania liczb?

Przepraszam za długi wstęp, ale naprawdę Nie wiem, jak nazwać rzeczy, o które chcę zapytać, więc muszę najpierw dać jakąś ekspozycję. To mocno czerpie z tego postu C. A. McCann , który po prostu nie zaspokaja mojej ciekawości, a ja również będę ręcznie wyginał problemy z rank-N-typami i nieskończonymi leniwymi rzeczami.

Jeden ze sposobów kodowania typów danych jako funkcji tworzy funkcję "pattern matching", która otrzymuje jeden argument dla każdego przypadku, każdy argument jest funkcją, która otrzymuje wartości odpowiadające temu konstruktorowi i wszystkie argumenty zwracające ten sam typ wyniku.

To wszystko działa zgodnie z oczekiwaniami dla typów nie rekurencyjnych

--encoding data Bool = true | False
type Bool r = r -> r -> r

true :: Bool r
true = \ct cf -> ct

false :: Bool r
false = \ct cf -> cf

--encoding data Either a b = Left a | Right b
type Either a b r = (a -> r) -> (b -> r) -> r

left :: a -> Either a b r
left x = \cl cr -> cl x

right :: b -> Either a b r
right y = \cl cr -> cr y

Jednak Ładna analogia z dopasowaniem wzorców rozpada się na typy rekurencyjne. Możemy pokusić się o coś w rodzaju

--encoding data Nat = Z | S Nat
type RecNat r = r -> (RecNat -> r) -> r
zero = \cz cs -> cz
succ n = \cz cs -> cs n

-- encoding data List a = Nil | Cons a (List a)
type RecListType a r = r -> (a -> RecListType -> r) -> r
nil = \cnil ccons -> cnil
cons x xs = \cnil ccons -> ccons x xs

Ale nie możemy napisać tego typu rekurencyjnego definicje w Haskell! Zwyczajowym rozwiązaniem jest wymuszenie wywołania zwrotnego sprawy cons / succ do zastosowania na wszystkich poziomach rekursji, a nie tylko na pierwszym (tj. pisanie fold/iterator). W tej wersji używamy typu return r gdzie typem rekurencyjnym będzie:

--encoding data Nat = Z | S Nat
type Nat r = r -> (r -> r) -> r
zero = \cz cf -> cz
succ n = \cz cf -> cf (n cz cf)

-- encoding data List a = Nil | Cons a (List a)
type recListType a r = r -> (a -> r -> r) -> r
nil = \z f -> z
cons x xs = \z f -> f x (xs z f)

Podczas gdy ta wersja działa, znacznie utrudnia definiowanie niektórych funkcji. Na przykład pisanie funkcji "ogona" dla list lub funkcji "poprzednika" dla liczb jest trywialne, jeśli można użyć dopasowania wzorców, ale staje się trudne, jeśli trzeba użyć fałdy zamiast.

Więc na moje prawdziwe pytania:

Jak możemy być pewni, że kodowanie za pomocą fałd jest tak potężne, jak hipotetyczne "kodowanie dopasowujące wzór"? czy istnieje sposób, aby przyjąć dowolną definicję funkcji poprzez dopasowanie wzorca i mechanicznie przekształcić ją na taką, używając tylko fałdów zamiast tego? (Jeśli tak, pomogłoby to również wprowadzić trudne definicje, takie jak tail lub foldl w kategoriach foldr jako mniej magiczne)
Dlaczego system typu Haskell nie pozwala na typy rekurencyjne potrzebne w kodowaniu" pattern matching"?. Czy istnieje powód zezwalania tylko na typy rekurencyjne w typach danych zdefiniowanych przez data? Czy dopasowanie wzorca jest jedynym sposobem na bezpośrednie wykorzystanie rekurencyjnych algebraicznych typów danych? Czy ma to związek z algorytmem wnioskowania typu?

14

haskell functional-programming algebraic-data-types church-encoding

Author: hugomg, 2012-11-27

Source

2 answers

Dany indukcyjny typ danych

data Nat = Succ Nat | Zero

Możemy rozważyć, w jaki sposób możemy dopasować te dane

case n of
  Succ n' -> f n'
  Zero    -> g

Powinno być oczywiste, że każda funkcja typu {[10] } może być zdefiniowana przez podanie odpowiednich f i g i że jedynym sposobem na utworzenie Nat (baring bottom) jest użycie jednego z dwóch konstruktorów.

Edit: pomyśl przez chwilę o f. Jeśli definiujemy funkcję foo :: Nat -> a podając odpowiednie f i g takie, że f wywołania rekurencyjne {[19] } niż możemy przedefiniować f jako f' n' (foo n') takie, że f' nie jest rekurencyjne. Jeśli Typ {[23] } to możemy zamiast tego napisać f' (foo n). Tak więc, bez utraty ogólności

foo n = h $ case n
                 Succ n' -> f (foo n)
                 Zero    -> g

To jest sformułowanie, które sprawia, że reszta mojego postu ma sens:

Tak więc, możemy myśleć o stwierdzeniu przypadku jako o zastosowaniu "słownika destruktora" [28]}

data NatDict a = NatDict {
   onSucc :: a -> a,
   onZero :: a
}

Teraz nasza sprawa z przeszłości może stać się

h $ case n of
      Succ n' -> onSucc (NatDict f g) n'
      Zero    -> onZero (NatDict f g)

Biorąc to możemy derive

newtype NatBB = NatBB {cataNat :: forall a. NatDict a -> a}

Możemy wtedy zdefiniować dwie funkcje

fromBB :: NatBB -> Nat
fromBB n = cataNat n (NatDict Succ Zero)

I

toBB :: Nat -> NatBB
toBB Zero = Nat $ \dict -> onZero dict
toBB (Succ n) = Nat $ \dict -> onSucc dict (cataNat (toBB n) dict)

Możemy udowodnić, że te dwie funkcje są świadkami izomorfizmu (aż do szybkiego i straconego rozumowania) i tym samym pokazać, że

newtype NatAsFold = NatByFold (forall a. (a -> a) -> a -> a)

(która jest taka sama jak NatBB) jest izomorficzna do Nat

Możemy użyć tej samej konstrukcji z innymi typami i udowodnić, że wynikowe typy funkcji są tym, czego chcemy, po prostu udowadniając, że typy bazowe są izomorficzne z algebraicznymi rozumowanie (i indukcja).

Jeśli chodzi o drugie pytanie, system typów Haskella opiera się na typach izo-rekurencyjnych, a nie równo-rekurencyjnych. Jest to prawdopodobnie dlatego, że teoria i wnioskowanie typów jest łatwiejsze do wypracowania z typami izo-rekurencyjnymi, a oni mają całą moc, którą po prostu narzucają trochę więcej pracy na Część programistów. Lubię twierdzić, że można uzyskać typy iso-rekurencyjne bez żadnych napowietrznych

newtype RecListType a r = RecListType (r -> (a -> RecListType -> r) -> r)

Ale widocznie GHCs optimizer dławił się tymi czasami :(.

6

Author: Philip JF,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-11-27 23:57:56

score 3 · Accepted Answer

Strona Wikipedii na Scott encoding ma kilka przydatnych spostrzeżeń. Krótka wersja jest taka, że chodzi Ci o kodowanie Kościoła, a twoje "hipotetyczne kodowanie dopasowania wzorców" to kodowanie Scotta. Oba są rozsądnymi sposobami robienia rzeczy, ale kodowanie Kościoła wymaga lżejszych maszyn do użycia (w szczególności nie wymaga typów rekurencyjnych).

Dowód, że oba są równoważne, wykorzystuje następującą ideę:

churchfold :: (a -> b -> b) -> b -> [a] -> b
churchfold _ z [] = z
churchfold f z (x:xs) = f x (churchfold f z xs)

scottfold :: (a -> [a] -> b) -> b -> [a] -> b
scottfold _ z [] = z
scottfold f _ (x:xs) = f x xs

scottFromChurch :: (a -> [a] -> b) -> b -> [a] -> b
scottFromChurch f z xs = fst (churchfold g (z, []) xs)
 where
  g x ~(_, xs) = (f x xs, x : xs)

Chodzi o to, że ponieważ churchfold (:) [] jest tożsamością na listach, możemy użyć fałdy kościelnej, która tworzy podany argument listy, jak również wynik, który ma wytworzyć. Następnie w łańcuchu x1 `f` (x2 `f` (... `f` xn) ... ) Zewnętrzny f otrzymuje parę (y, x2 : ... : xn : []) (dla niektórych {[5] } nie zależy nam), więc zwraca f x1 (x2 : ... : xn : []). Oczywiście, musi również zwrócić x1 : ... : xn : [], aby kolejne aplikacje f mogły również działać.

(w rzeczywistości jest to trochę podobne do dowodu matematycznej Zasady silnej (lub pełnej) indukcja , od "słabej" lub zwykłej zasady indukcji).

Przy okazji, twój typ Bool r jest trochę za duży dla prawdziwych booleanów kościelnych – np. (+) :: Bool Integer, ale (+) nie jest tak naprawdę booleanem kościelnym. Jeśli włączysz RankNTypes, możesz użyć bardziej precyzyjnego typu: type Bool = forall r. r -> r -> r. Obecnie jest zmuszony do polimorfizmu, więc zawiera tylko dwa (pomijając seq i dolny) mieszkańców - \t _ -> t i \_ f -> f. Podobne idee odnoszą się również do innych typów kościołów.