Zrozumienie podpis typu z gfoldl z Data.Data.Data

Question

Data definiuje jako jeden ze swoich podstawowych funkcji gfoldl:

gfoldl 
    :: (Data a) 
    => (forall d b. Data d => c (d -> b) -> d -> c b) 
    -> (forall g. g -> c g) 
    -> a 
    -> c a 

Jaki jest cel c i c (d -> b) w nim? Dlaczego nie jest to po prostu zwykły krotnie, coś

gfoldl' 
    :: (Data a) 
    => (forall d. Data d => r -> d -> r) 
    -> r 
    -> a 
    -> r 

Answer 1

Chodzi o to, że wartość algebraiczna typów danych w Haskell ma postać

C x_1 x_2 ... x_n 

gdzie C jest konstruktorem i x_i są argumenty. Co

gfoldl app con 

robi to, aby włączyć taką wartość w

con C `app` x_1 `app` x_2 ... `app` x_n 

tym samym przekształcając a w c a. Załóżmy rodzaj C jest

C :: T_1 -> T_2 -> ... -> T_n -> D 

następnie przyjrzyjmy typów wyrażeń pośrednimi:

con C         :: c (T_1 -> T_2 -> ... -> T_n -> D) 
con C `app` x_1       :: c (T_2 -> ... -> T_n -> D) 
con C `app` x_1 `app` x_2    :: c (... -> T_n -> D) 
con C `app` x_1 `app` x_2 ... `app` x_n :: c D 

Parametryzacja nad c pozwala wszystkie te typy pośrednie być inaczej. Gdybyśmy zamiast tego używali prostego spasowania, takiego jak gfoldl', wszystkie te typy pośrednie musiałyby być takie same.

Motywacją dla gfoldl ma być pojedynczy uogólnienie, które pozwala wyrazić funkcje SyB gmapQ i gmapT (i kilka innych). Rodzaje gmapQ i gmapT to:

gmapQ :: Data a => (forall d. Data d => d -> u) -> a -> [u] 
gmapT :: Data a => (forall b. Data b => b -> b) -> a -> a 

Podczas gmapQ zapada się w równomiernym a liście u S i może być wyrażona za pomocą gfoldl', to nie byłoby możliwe gmapT.

Jednak z gfoldl, możemy użyć c = Identity aby umożliwić nam dostać coś podobnego gmapT i c = Const dostać coś jak gmapQ.

Aby uzyskać więcej informacji, można również zajrzeć do papieru Scrap your boilerplate Reloaded którego wynika, że ​​gfoldl jest zwykłą (jeszcze wyższego rzędu) krotnie od typu danych, który nazywany jest Spine w tym dokumencie.

Wykorzystanie tożsamości i stałych funktorów w celu uzyskania zarówno przekształcenia, jak i zachowania aktualizacji z pojedynczego podstawowego przedstawienia ma pewne podobieństwo do sposobu uzyskania operacji soczewki z soczewek "van Laarhoven".