两个延续如何相互抵消？

Question

我正在阅读有关列表操作的一些技巧，其中包含以下内容：

zipRev xs ys = foldr f id xs snd (ys,[])
  where
    f x k c = k (\((y:ys),r) -> c (ys,(x,y):r)) 

我们在这里可以看到，我们有两个连续的叠放在一起。发生这种情况时，他们通常可以“取消”，如下所示：

zipRev xs ys = snd (foldr f (ys,[]) xs)
  where
    f x (y:ys,r) = (ys,(x,y):r)

我不明白您如何“取消”堆叠的延续以从顶部的代码块到达底部的代码块。您寻找进行这种转换的方式是什么，为什么会起作用？

Answer 1

函数f :: a -> b可以“伪装”双延续作为一个函数内f' :: ((a -> r1) -> r2) -> ((b -> r1) -> r2)。

obfuscate :: (a -> b) -> ((a -> r1) -> r2) -> (b -> r1) -> r2
obfuscate f k2 k1 = k2 (k1 . f)

obfuscate具有很好的属性，可以保留函数的组成和身份：您可以通过几个步骤证明这obfuscate f . obfuscate g === obfuscate (f . g)一点obfuscate id === id。这意味着您可以经常使用此变换来解开构成obfuscated函数的双连续计算，方法obfuscate是将合成中的因子分解出来。这个问题就是这样一个例子。

的f在顶部的代码块是obfuscate的d版本f在底块（更确切地说，顶部f x是obfuscate底部的d版本f x）。您可以通过注意到top如何f将外部延续应用到转换其输入的函数，然后将整个事物应用到内部延续来看到这一点，就像在主体中一样obfuscate。

这样我们就可以解开纠结zipRev：

zipRev xs ys = foldr f id xs snd (ys,[])
  where
    f x = obfuscate (\(y:ys,r) -> (ys,(x,y):r))

由于foldr此处的作用是obfuscate彼此构成一堆d函数（并将其全部应用到id，我们可以在右边保留），因此我们可以将d函数分解为obfuscate整个折叠的外部：

zipRev xs ys = obfuscate (\accum -> foldr f accum xs) id snd (ys,[])
  where
    f x (y:ys,r) = (ys,(x,y):r)

现在应用的定义obfuscate并简化：

zipRev xs ys = obfuscate (\accum -> foldr f accum xs) id snd (ys,[]) 
zipRev xs ys = id (snd . (\accum -> foldr f accum xs)) (ys,[])
zipRev xs ys = snd (foldr f (ys,[]) xs)

QED！

Answer 2

给定功能

g :: a? -> a?

我们可以将其提升为延续函数，切换顺序：

lift g = (\c a? -> c (g a?))
    :: (a? -> t) -> a? -> t

这个转换是一个逆函数，也就是说，它通过切换顺序与功能组合交互：

g? :: a? -> a?
g? :: a? -> a?

lift g? . lift g?
== (\c? a? -> c? (g? a?)) . (\c? a? -> c? (g? a?))
== \c? a? -> (\a? -> c? (g? a?)) (g? a?)
== \c? a? -> c? (g? (g? a?)) 
== lift (g? . g?)
    :: (a? -> t) -> a? -> t

lift id
== (\c a? -> c a?)
== id
    :: (a? -> t) -> a? -> t

我们可以以与堆叠连续体上的函数相同的方式再次提升被提升的函数，但顺序要切换回去：

lift (lift g)
== (\k c -> k ((\c a? -> c (g a?)) c))
== (\k c -> k (\a? -> c (g a?)))
    :: ((a? -> t) -> u) -> (a? -> t) -> u

堆叠两个逆变函子可以得到一个（协变）函子：

lift (lift g?) . lift (lift g?)
== lift (lift g? . lift g?)
== lift (lift (g? . g?))
    :: ((a? -> t) -> u) -> (a? -> t) -> u

lift (lift id)
== lift id
== id
    :: ((a? -> t) -> u) -> (a? -> t) -> u

这正是您的示例中使用逆转的转换g = \(y:ys, r) -> (ys, (x, y):r)。这g是一个内同态（a? = a?），它foldr是将一堆带有各种的拷贝组成在一起x。我们正在做的是用功能组合的双重提升来代替双重提升的功能，这只是对函子定律的归纳应用：

f :: x -> a? -> a?
c :: (a? -> t) -> u
xs :: [x]

foldr (\x -> lift (lift (f x))) c xs
== lift (lift (\a? -> foldr f a? xs)) c
    :: (a? -> t) -> u