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

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



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

最佳答案

函数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从合成中分解出来，来解开组成obfuscate d函数的双连续计算。这个问题就是这样一个例子。

顶部代码块中的f是底部块中obfuscate的f d版本(更确切地说，top f x是底部obfuscate的f x d版本)。您可以通过注意到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，我们可以在右边保留)，因此我们可以将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!

关于haskell - 两个延续如何相互抵消？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56122022/