haskell - 两个延续如何相互抵消？

Question

我正在阅读 Some Tricks for List Manipulation ，它包含以下内容:

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

What we can see here is that we have two continuations stacked on top of each other. When this happens, they can often “cancel out”, like so:

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在几个步骤中。这意味着您可以经常使用此转换来解开构成 obfuscate 的双连续计算。 d 通过因式分解obfuscate 一起发挥作用出组合物。这个问题就是这种解开的一个例子。
f在顶部代码块中是 obfuscate f 的 d 版本在底部 block 中(更准确地说，顶部 f x 是底部 obfuscate 的 f x d 版本)。您可以通过注意顶部 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 ，我们可以将其留在右侧)，我们可以分解 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!