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

Question

Data将其核心功能之一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的东西。

要了解更多细节，您可能还需要查看论文把你的样板重装起来，它表明gfoldl是一种数据类型的普通(但更高的)折叠，该数据类型在该论文中称为Spine。

使用恒等函子从单个基本表示中获得变换和更新行为与从"van Laarhoven“透镜获得透镜操作有一些相似之处。