Rodzaj sprawdzeniu z RankNTypes w Haskell

Question

Próbuję zrozumieć RankNTypes w Haskell i znalazłem ten przykład: (. Jeśli moje zrozumienie jest prawidłowe, jest to równoznaczne z check :: forall b c d. Eq b => (forall a. [a] -> b) -> [c] -> [d] -> Bool)

check :: Eq b => (forall a. [a] -> b) -> [c] -> [d] -> Bool 
check f l1 l2 = f l1 == f l2 

Ok, jak na razie dobrze. Teraz, gdy wyraźne forall a jest usuwany, GHC produkuje następujące błędy:

Could not deduce (c ~ a) 
from the context (Eq b) 
[…] 
Could not deduce (d ~ a) 
from the context (Eq b) 
[…] 

Wyjmując zagnieżdżona forall, podpis typu staje

check :: forall a b c d. Eq b => ([a] -> b) -> [c] -> [d] -> Bool 

Łatwo jest zrozumieć, dlaczego to się nie powiedzie wpisać sprawdzanie od l1 i l2 powinny mieć typ [a], abyśmy mogli przekazać je do f, ale dlaczego nie jest tak w przypadku określania typu f jako (forall a. [a] ->b)? Czy fakt, że a jest związany tylko wewnątrz parens pełną odpowiedź? To znaczy. sprawdzania typu zaakceptuje

[c] -> b ~ (forall a. [a] -> b) 
[d] -> b ~ (forall a. [a] -> b) 

(Edycja: Fixed. Dzięki, Boyd!)

od funkcji typu (forall a. a -> b) może potrwać żadnej listy?

Answer 1

Kiedy f = \xs -> ... jest napisana z wyraźnym Rank2 kwantyfikacji forall a. [a] -> b można zobaczyć to jako nową funkcję

f = Λa -> \xs -> ... 

gdzie Λ jest specjalnym lambda, która zajmuje typu argumentu celu określenia, które specyficzny rodzaj a to będzie użyj w ciele funkcji. Ten typ argumentu jest stosowany za każdym razem, gdy wywoływana jest funkcja, podobnie jak stosowane są normalne powiązania lambda dla każdego połączenia. W ten sposób GHC wewnętrznie obsługuje forall.

W Jawnie forall „wersji d, f mogą być stosowane do różnych typów argumentów za każdym razem jest tak zwany a można rozwiązać na inny typ za każdym razem, gdy do c i raz na d.

W wersji bez wewnętrznej forall, aplikacja tego typu dla a dzieje się tylko raz, gdy jest wywoływana check.Dlatego za każdym razem, gdy jest wywoływana f, musi używać tego samego a. Oczywiście to się nie udaje, ponieważ f jest wywoływane na listach różnych typów.

Answer 2

Można przepisać uniwersalne kwantyfikacje w polu przeciwstawnym z kwantyfikacją egzystencjalną w polach kowariancyjnych (nie prawnie w Haskell, ale w zasadzie).

check' :: exists c' d'. forall b c d. Eq b 
      => ([c'] -> b) -> ([d'] -> b) -> [c] -> [d] -> Bool 

To dosyć oczywiste, że to działa: na c ~ C, d ~ D wybrać c' ~ C i d' ~ D jak dobrze, to funkcja jest po prostu

check'' :: forall b . Eq b => ([C] -> b) -> ([D] -> b) -> [C] -> [D] -> Bool 

Nie wiem, czy to odpowiedzi, pytanie, ale jest to jeden ze sposobów aby przyjrzeć się typom rang 2.

Answer 3

Łatwo zrozumieć, dlaczego to nie powiedzie się sprawdzanie typu, ponieważ l1 i l2 powinny mieć typ [a], abyśmy przekazali je do f, ale dlaczego nie jest tak w przypadku określania typu f jako (dla wszystkich . [a] -> b)?

ponieważ typ (forall a. [a] -> B) mogą być ujednolicone z [C] -> B i (oddzielnie) [D] -> B. Jednak typu [A] -> B nie można ujednolicić z [C] -> B ani [D] -> B.

Czy fakt, że a jest tylko związany w parens pełną odpowiedź?

Zasadniczo. Musisz wybrać konkretny typ dla każdej zmiennej typu, gdy jesteś "wewnątrz" całościowego zasięgu, ale poza tym możesz korzystać z funkcji wiele razy i wybierać inny określony typ za każdym razem.

tj. sprawdzanie typu będzie akceptować

[c] ~ (forall a. a -> b) 
[d] ~ (forall a. a -> b) 

, ponieważ funkcja typu (forall a. a -> b) może przyjmować dowolną listę?

Ostrożnie. Wygląda na to, że straciłeś jakieś "[]" znaki. Poza tym nie jesteś w stanie poprawnie zunifikować. Kontrolujący typ będzie akceptować zarówno:

[C] -> B ~ (forall a. [a] -> B) 
[D] -> B ~ (forall a. [a] -> B) 

To nie zaakceptuje albo: "(. Forall a a -> b) dlaczego nie _tylko_ pracę z` `"

[C] -> B ~ [A] -> B 
[D] -> B ~ [A] -> B