Comprendere la firma tipo di gfoldl da Data.Data.Data

Question

Data definisce come una delle sue funzioni fondamentali gfoldl:

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

Qual è lo scopo di c e c (d -> b) in esso? Perché non è solo una piega normale, qualcosa di simile a

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

Answer 1

L'idea è che un valore di un tipo di dati algebrica in Haskell ha la forma

C x_1 x_2 ... x_n 

dove C è un costruttore e il x_i sono gli argomenti. Nei

gfoldl app con 

fa è trasformare tale valore in

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

trasformando così un a in c a. Supponiamo che il tipo di C è

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

poi guardiamo i tipi di espressioni intermedie:

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 

La parametrizzazione su c consente a tutti questi tipi di media importanza diverso. Se invece utilizzassimo una piega semplice come gfoldl', allora tutti i tipi intermedi dovrebbero essere uguali.

La motivazione per gfoldl è quello di essere una sola generalizzazione che ti permette di esprimere le funzioni SYB gmapQ e gmapT (e pochi altri). I tipi di gmapQ e gmapT sono:

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

Mentre gmapQ crolla un a in un elenco uniforme u s e potrebbe espressi ricorrendo gfoldl', ciò non sarebbe possibile per gmapT.

Tuttavia, con gfoldl, possiamo usare c = Identity per permetterci di ottenere qualcosa come gmapT, e c = Const per ottenere qualcosa di simile gmapQ.

Per maggiori dettagli, si può anche voler guardare la carta Scrap your boilerplate Reloaded che dimostra che gfoldl è un normale (ancora di ordine superiore) piegare di un tipo di dati che si chiama Spine in quella carta.

L'uso della identità e funtori costanti per ottenere sia di trasformazione e comportamento aggiornamento da una singola rappresentazione sottostante ha una certa somiglianza con come ottenere le operazioni di lenti da lenti "van Laarhoven".