从 Data.Data.Data 了解 gfoldl 的类型签名

Question

Data defines as one of its core functions gfoldl:

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

里面的c和c (d -> b)有什么用？为什么它不只是一个普通的折叠，比如

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

Answer 1

想法是 Haskell 中的代数数据类型的值具有

形式

C x_1 x_2 ... x_n

其中 C 是构造函数，x_i 是参数。什么

gfoldl app con

就是把这样的值变成

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

从而将 a 变成 c a。假设 C 的类型是

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

那我们看看中间表达式的类型：

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

c 的参数化允许所有这些中间类型不同的。如果我们改用 gfoldl' 之类的简单折叠，那么所有这些中间类型必须相同。

gfoldl 的动机是成为一个使您可以表达 SYB 函数 gmapQ 和 gmapT（以及其他一些函数）的单一泛化。 gmapQ和gmapT的类型是：

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

虽然 gmapQ 将 a 折叠成 u 的统一列表，并且可以使用 gfoldl' 表示，这对于 gmapT.

是不可能的

但是，使用 gfoldl，我们可以使用 c = Identity 来获得像 gmapT 和 c = Const 得到像 gmapQ.

这样的东西

有关更多详细信息，您可能还想查看论文 Scrap your boilerplate Reloaded，其中显示 gfoldl 是一个普通的（尚未高阶）在该论文中称为 Spine 的数据类型的折叠。

使用恒等函子来获得转换和从单个底层表示更新行为有一些与从 "van Laarhoven" 镜头获得镜头操作的方式相似。

从 Data.Data.Data 了解 gfoldl 的类型签名

Understanding the type signature of gfoldl from Data.Data.Data

haskell

types

type-signature

scrap-your-boilerplate