Tricky typ podpis dla par pary odwrócone

Question

Powiedzmy mam następujący typ danych:

data D a b = D (a,b) (b,a) 

I chcę, aby zdefiniować następującą funkcję od niego:

apply f (D x y) = D (f x) (f y) 

Co to jest podpis typu z apply?

Oto kilka przykładów f które są w porządku:

f :: a -> a -- OK 
f :: (a, b) -> (b, a) -- OK 
f :: (a, b) -> ((a, c), (b, c)) -- OK 

We wszystkich powyższych przypadkach, możemy skończyć z ważnego typu D.

Ale to nie jest w porządku:

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

Ponieważ po wysłaniu takiej funkcji przez apply, musimy spróbować zbudować D (a,a) (b,b), która jest nieważna, chyba że a = b.

Nie mogę wydawać się podpis typu, aby wyrazić to wszystko? Ponadto, czy istnieje sposób, aby GHC powiedział mi, jakie powinny być te podpisy?

Wpisywane Holes Edycja:

Próbując odnaleźć typ za pomocą wpisywanych otwory, próbowałem następujące:

x = apply _ (D (1::Int,'a') ('b',2::Int)) 

I got:

Found hole ‘_’ with type: (Int, Int) -> (b, b) 
Where: ‘b’ is a rigid type variable bound by 
      the inferred type of x :: D b b 

co wydaje się mnie bycie nonsensem jako f :: (Int, Int) -> (b, b) najwyraźniej nie będzie tu działać.

Answer 1

Wiele typów pasuje do apply, ale wnioskowane ((t, t) -> (b, b)) -> D t t -> D b b jest najbardziej sensowne i użyteczne. Alternatywy będą wyższej rangi, więc niech to umożliwić, że przedłużenie język:

{-# LANGUAGE RankNTypes #-} 

Po pierwsze, możemy dokonać apply id pracy:

apply :: (forall a. a -> a) -> D a b -> D a b 
apply f (D x y) = D (f x) (f y) 

Jednak teraz id jest tylko funkcja z który działa apply (wszystkie funkcje łącznie typu forall a. a -> a są równe id).

Oto kolejny typ:

apply :: (forall a. a -> (c, c)) -> D a b -> D c c 
apply f (D x y) = D (f x) (f y) 

Ale to też jest w cenie. Teraz f -s mogą być tylko stałymi funkcjami, które ignorują poprzednie pola D. Tak więc apply (const (0, 0)) działa, ale nie mamy możliwości sprawdzenia argumentu f.

W przeciwieństwie do tego, wywnioskowany typ jest całkiem przydatny. Możemy wyrazić transformacje, które sprawdzają rzeczywiste dane zawarte w D.

W tym miejscu możemy zapytać: dlaczego GHC wywnioskuje, co zawiera? W końcu niektóre funkcje działają z typami alternatywnymi, ale nie działają z typem domyślnym. Czy czasem lepiej jest wnioskować typy o wyższej randze? Takie typy są często niezwykle przydatne, ale wnioskowanie o nich jest niewykonalne.

Wnioskowanie o typ dla typów rangi-2 jest dość skomplikowane i mało praktyczne, ponieważ nie można wywnioskować, że są to najbardziej ogólne typy. W przypadku wnioskowania rangowego 1 możemy wywnioskować typ bardziej ogólny niż wszystkie inne poprawne typy dla tego samego wyrażenia. Nie ma takiej gwarancji w przypadku typów rang 2. Wnioskowanie dla typów 3 i wyższych to tylko undecidable.

Z tych powodów GHC trzyma się rangi 1, więc nigdy nie podaje typów z forall -s wewnętrznych argumentów funkcji.

Answer 2

Biorąc rzeczy do skrajności ogólności, chcemy typ, który wygląda jak

apply :: tf -> D a b -> D c d 

gdzie tf reprezentuje typ f. W celu zastosowania f do (a,b) i uzyskać (c,d) musimy

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

w celu zastosowania f do (b,a) dostać (d,c) musimy

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

Gdybyśmy włączyć TypeFamilies (lub GADTs) mamy zdobądź magiczne ograniczenie, które musimy wyrazić:

{-# LANGUAGE TypeFamilies #-} 

apply :: (((a,b) -> (c,d)) ~ tf, 
      ((b,a) -> (d,c)) ~ tf) => 
     tf -> D a b -> D c d 

Podejrzewam, że jest to jeden z najbardziej ogólnych dostępnych typów. Niestety, jest dość dzika; sprawdzanie, czy dana aplikacja przejdzie sprawdzanie typu, nie zawsze jest takie łatwe. Należy również zauważyć, że ze względów Osobiście nie rozumiem, nie można wiarygodnie określić specjalizacje użyciu

apply' :: ... 
apply' = apply 

Zamiast tego, czasami musi korzystać

apply' f = apply f