两个延续如何相互抵消？
How can two continuations cancel each other out?
我正在通读 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)
我不明白您如何 "cancel out" 堆叠延续以从顶部代码块到达底部代码块。您寻找什么模式来进行这种转换，为什么它有效？
函数 f :: a -> b 可以 "disguised" 在双重延续中作为函数 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。这意味着您可以经常使用此转换来解开 double-continuation 计算，这些计算将 obfuscated 函数组合在一起，方法是将 obfuscate 从组合中分解出来。这个问题就是这种理清的一个例子。
顶部代码块中的 f 是底部代码块中 f 的 obfuscated 版本（更准确地说，顶部 f x 是 obfuscated 版本底部 f x)。您可以通过注意 top f 如何将外部延续应用于转换其输入的函数，然后将整个事物应用于内部延续，就像在 obfuscate.[=35 的主体中一样=]
所以我们可以开始理清zipRev:
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x = obfuscate (\(y:ys,r) -> (ys,(x,y):r))
因为这里foldr的作用是把一堆obfuscated个函数相互组合起来（然后全部应用到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！
给定一个函数
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合成一堆它的副本。我们正在做的是用函数组合的 double-lift 替换 double-lifted 函数的组合，这只是函子定律的归纳应用：
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
让我们试着从初级的角度来理解这段代码。它到底有什么作用，有人想知道吗？
zipRev xs ys = foldr f id xs snd (ys,[])
where
-- f x k c = k (\(y:ys, r) -> c (ys, (x,y):r))
f x k c = k (g x c)
-- = (k . g x) c -- so,
-- f x k = k . g x
g x c (y:ys, r) = c (ys, (x,y):r)
这里我们使用了lambda lifting to recover the g combinator。
那么因为 f x k = k . g x 是 k 到 x 的左边 ，输入列表被翻译成一个反向链作品，
foldr f id [x1, x2, x3, ..., xn] where f x k = k . g x
===>>
(((...(id . g xn) . ... . g x3) . g x2) . g x1)
因此，它只是做了左折叠会做的事情，
zipRev [] ys = []
zipRev [x1, x2, x3, ..., xn] ys
= (id . g xn . ... . g x3 . g x2 . g x1) snd (ys, [])
= g xn (g xn1 ( ... ( g x3 ( g x2 ( g x1 snd)))...)) (ys, [])
where ----c--------------------------------------------
g x c (y:ys, r) = c (ys, (x,y):r)
所以我们去了 xs 列表的最深处，然后我们回来在路上消费 ys 列表 left-to-right（即 top-down）回到 xs 列表中的 right-to-left（即 bottom-up）。这直接编码为带有严格缩减器的右折叠，因此流程确实是 xs 上的 right-to-left。链中的 bottom-most 操作 (snd) 最后完成，因此在新代码中它成为最顶层（仍然最后完成）：
zipRev xs ys = snd (foldr h (ys,[]) xs)
where
h x (y:ys, r) = (ys, (x,y):r)
g x c在原代码中作为延续，用c作为second-tier延续；但实际上一直都是从右边开始的常规弃牌。
所以它确实将反向的第一个列表与第二个列表压缩在一起。这也不安全；它遗漏了一个子句：
g x c ([], r) = c ([], r) -- or just `r`
g x c (y:ys, r) = c (ys, (x,y):r)
(update:) duplode（和 Joseph Sible）的答案以更适合任务的方式对 lambda 进行了一些不同的提升。它是这样的：
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x k c = k (\((y:ys), r) -> c (ys, (x,y):r))
= k (c . (\((y:ys), r) -> (ys, (x,y):r)) )
= k (c . g x)
g x = (\((y:ys), r) -> (ys, (x,y):r))
{- f x k c = k ((. g x) c) = (k . (. g x)) c = (. (. g x)) k c
f x = (. (. g x)) -}
那么
foldr f id [ x1, x2, ... , xn ] snd (ys,[]) =
= ( (. (. g x1)) $ (. (. g x2)) $ ... $ (. (. g xn)) id ) snd (ys,[]) -- 1,2...n
= ( id . (. g xn) . ... . (. g x2) . (. g x1) ) snd (ys,[]) -- n...2,1
= ( snd . g x1 . g x2 . ... . g xn ) (ys,[]) -- 1,2...n!
= snd $ g x1 $ g x2 $ ... $ g xn (ys,[])
= snd $ foldr g (ys,[]) [x1, x2, ..., xn ]
简单。 :) 翻转两次根本就不是翻转。
让我们从一些外观调整开始：
-- Note that `g x` is an endomorphism.
g :: a -> ([b], [(a,b)]) -> ([b], [(a,b)])
g x ((y:ys),r) = (ys,(x,y):r)
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x k = \c -> k (c . g x)
f 将延续 (c . g x) 提供给另一个函数 (k, "double continuation", ).
虽然我们可能合理地期望随着折叠的进行重复使用 f 将以某种方式组成由列表元素组成的 g x 自同态，但自同态的组成顺序可能不是很明显，所以我们最好通过几个步骤来确定：
-- x0 is the first element, x1 the second, etc.
f x0 k0
\c -> k0 (c . g x0)
\c -> (f x1 k1) (c . g x0) -- k0 is the result of a fold step.
\c -> (\d -> k1 (d . g x1)) (c . g x0) -- Renaming a variable for clarity.
\c -> k1 (c . g x0 . g x1)
-- etc .
-- xa is the *last* element, xb the next-to-last, etc.
-- ka is the initial value passed to foldr.
\c -> (f xa ka) (c . g x0 . g x1 . . . g xb)
\c -> (\d -> ka (d . g xa)) (c . g x0 . g x1 . . . g xb)
\c -> ka (c . g x0 . g x1 . . . g xb . g xa)
ka，传递给 foldr 的初始值是 id，这使事情变得相当简单：
foldr f id xs = \c -> c . g x0 . g x1 . . . g xa
由于我们对传递给 foldr f id xs 的 c 参数所做的一切都是 post-composing 它与自同态，我们不妨将其排除在外：
zipRev xs ys = (snd . foldr h id xs) (ys,[])
where
h x e = g x . e
请注意我们是如何从 c . g x 发展到 g x . e 的。这可以说是原始实施中 CPS 欺骗的附带影响。
最后一步是注意 h x e = g x . e 如何与我们对 implement foldr in terms of foldMap for the Endo monoid 所做的完全对应。或者，更明确地说：
foldEndo g i xs = foldr g i xs -- The goal is obtaining an Endo-like definition.
foldEndo _ i [] = i
foldEndo g i (x : xs) = g x (foldEndo g i xs)
foldEndo g i xs = go xs i
where
go [] = \j -> j
go (x : xs) = \j -> g x (foldEndo g j xs)
foldEndo g i xs = go xs i
where
go [] = \j -> j
go (x : xs) = \j -> g x (go xs j)
foldEndo g i xs = go xs i
where
go [] = id
go (x : xs) = g x . go xs
foldEndo g i xs = go xs i
where
h x e = g x . e
go [] = id
go (x : xs) = h x (go xs)
foldEndo g i xs = go xs i
where
h x e = g x . e
go xs = foldr h id xs
foldEndo g i xs = foldr h id xs i
where
h x e = g x . e
这最终让我们找到了我们要找的东西：
zipRev xs ys = snd (foldr g (ys,[]) xs)
让我明白了。这是我在阅读它时的一些见解，以及一些 step-by-step 转换。
见解
- 延续不直接抵消。它们最终只能被取消（beta-reducing），因为有可能将它们排除在外。
- 您正在寻找的进行此转换的模式是
\k c -> k (c . f)（或者如果您喜欢不可读的 pointfree，(. (. f))）对于任何 f（请注意 f 不是 lambda 的参数）。
- 作为
，continuation-passing风格的函数可以认为是函子，而obfuscate是他们对fmap的定义。
- 从
foldr 中提取这样的函数的技巧适用于任何可能是有效的函数 fmap。
从第一个代码块到第二个代码块的完整转换
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x k c = k (\((y:ys),r) -> c (ys,(x,y):r))
从 lambda
中拉出 c
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x k c = k (c . \((y:ys),r) -> (ys,(x,y):r))
用obfuscate代替它的定义
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x = obfuscate (\((y:ys),r) -> (ys,(x,y):r))
从 lambda
中拉出 obfuscate
zipRev xs ys = foldr f id xs snd (ys,[])
where
f = obfuscate . \x ((y:ys),r) -> (ys,(x,y):r)
从f
中拉出obfuscate
zipRev xs ys = foldr (obfuscate . f) id xs snd (ys,[])
where
f x ((y:ys),r) = (ys,(x,y):r)
因为obfuscate遵循函子定律，我们可以把它从foldr
中拉出来
zipRev xs ys = obfuscate (flip (foldr f) xs) id snd (ys,[])
where
f x ((y:ys),r) = (ys,(x,y):r)
内联obfuscate
zipRev xs ys = (\k c -> k (c . flip (foldr f) xs)) id snd (ys,[])
where
f x ((y:ys),r) = (ys,(x,y):r)
Beta-reduce
zipRev xs ys = (id (snd . flip (foldr f) xs)) (ys,[])
where
f x ((y:ys),r) = (ys,(x,y):r)
简化
zipRev xs ys = snd (foldr f (ys,[]) xs)
where
f x (y:ys,r) = (ys,(x,y):r)
从 foldr
中提取 fmap 有效函数的理由
foldr (fmap . f) z [x1,x2,...,xn]
展开foldr
(fmap . f) x1 . (fmap . f) x2 . ... . (fmap . f) xn $ z
内联内部 .s
fmap (f x1) . fmap (f x2) . ... . fmap (f xn) $ z
应用函子定律
fmap (f x1 . f x2 . ... . f xn) $ z
Eta-expand括号里的部分
fmap (\z2 -> f x1 . f x2 . ... . f xn $ z2) z
根据 foldr
编写 lambda 主体
fmap (\z2 -> foldr f z2 [x1,x2,...,xn]) z
根据 flip
编写 lambda 主体
fmap (flip (foldr f) [x1,x2,...,xn]) z
奖励：从 foldr
中提取 contramap 有效函数的理由
foldr (contramap . f) z [x1,x2,...,xn]
展开foldr
(contramap . f) x1 . (contramap . f) x2 . ... . (contramap . f) xn $ z
内联内部 .s
contramap (f x1) . contramap (f x2) . ... . contramap (f xn) $ z
应用逆变定律
contramap (f xn . ... . f x2 . f x1) $ z
Eta-expand括号里的部分
contramap (\z2 -> f xn . ... . f x2 . f x1 $ z2) z
根据 foldr
编写 lambda 主体
contramap (\z2 -> foldr f z2 [xn,...,x2,x1]) z
根据 flip
编写 lambda 主体
contramap (flip (foldr f) [xn,...,x2,x1]) z
应用foldr f z (reverse xs) = foldl (flip f) z xs
contramap (flip (foldl (flip f)) [x1,x2,...,xn]) z
我正在通读 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)
我不明白您如何 "cancel out" 堆叠延续以从顶部代码块到达底部代码块。您寻找什么模式来进行这种转换，为什么它有效？
函数 f :: a -> b 可以 "disguised" 在双重延续中作为函数 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。这意味着您可以经常使用此转换来解开 double-continuation 计算，这些计算将 obfuscated 函数组合在一起，方法是将 obfuscate 从组合中分解出来。这个问题就是这种理清的一个例子。
顶部代码块中的 f 是底部代码块中 f 的 obfuscated 版本（更准确地说，顶部 f x 是 obfuscated 版本底部 f x)。您可以通过注意 top f 如何将外部延续应用于转换其输入的函数，然后将整个事物应用于内部延续，就像在 obfuscate.[=35 的主体中一样=]
所以我们可以开始理清zipRev:
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x = obfuscate (\(y:ys,r) -> (ys,(x,y):r))
因为这里foldr的作用是把一堆obfuscated个函数相互组合起来（然后全部应用到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！
给定一个函数
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合成一堆它的副本。我们正在做的是用函数组合的 double-lift 替换 double-lifted 函数的组合，这只是函子定律的归纳应用：
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
让我们试着从初级的角度来理解这段代码。它到底有什么作用，有人想知道吗？
zipRev xs ys = foldr f id xs snd (ys,[])
where
-- f x k c = k (\(y:ys, r) -> c (ys, (x,y):r))
f x k c = k (g x c)
-- = (k . g x) c -- so,
-- f x k = k . g x
g x c (y:ys, r) = c (ys, (x,y):r)
这里我们使用了lambda lifting to recover the g combinator。
那么因为 f x k = k . g x 是 k 到 x 的左边 ，输入列表被翻译成一个反向链作品，
foldr f id [x1, x2, x3, ..., xn] where f x k = k . g x
===>>
(((...(id . g xn) . ... . g x3) . g x2) . g x1)
因此，它只是做了左折叠会做的事情，
zipRev [] ys = []
zipRev [x1, x2, x3, ..., xn] ys
= (id . g xn . ... . g x3 . g x2 . g x1) snd (ys, [])
= g xn (g xn1 ( ... ( g x3 ( g x2 ( g x1 snd)))...)) (ys, [])
where ----c--------------------------------------------
g x c (y:ys, r) = c (ys, (x,y):r)
所以我们去了 xs 列表的最深处，然后我们回来在路上消费 ys 列表 left-to-right（即 top-down）回到 xs 列表中的 right-to-left（即 bottom-up）。这直接编码为带有严格缩减器的右折叠，因此流程确实是 xs 上的 right-to-left。链中的 bottom-most 操作 (snd) 最后完成，因此在新代码中它成为最顶层（仍然最后完成）：
zipRev xs ys = snd (foldr h (ys,[]) xs)
where
h x (y:ys, r) = (ys, (x,y):r)
g x c在原代码中作为延续，用c作为second-tier延续；但实际上一直都是从右边开始的常规弃牌。
所以它确实将反向的第一个列表与第二个列表压缩在一起。这也不安全；它遗漏了一个子句：
g x c ([], r) = c ([], r) -- or just `r`
g x c (y:ys, r) = c (ys, (x,y):r)
(update:) duplode（和 Joseph Sible）的答案以更适合任务的方式对 lambda 进行了一些不同的提升。它是这样的：
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x k c = k (\((y:ys), r) -> c (ys, (x,y):r))
= k (c . (\((y:ys), r) -> (ys, (x,y):r)) )
= k (c . g x)
g x = (\((y:ys), r) -> (ys, (x,y):r))
{- f x k c = k ((. g x) c) = (k . (. g x)) c = (. (. g x)) k c
f x = (. (. g x)) -}
那么
foldr f id [ x1, x2, ... , xn ] snd (ys,[]) =
= ( (. (. g x1)) $ (. (. g x2)) $ ... $ (. (. g xn)) id ) snd (ys,[]) -- 1,2...n
= ( id . (. g xn) . ... . (. g x2) . (. g x1) ) snd (ys,[]) -- n...2,1
= ( snd . g x1 . g x2 . ... . g xn ) (ys,[]) -- 1,2...n!
= snd $ g x1 $ g x2 $ ... $ g xn (ys,[])
= snd $ foldr g (ys,[]) [x1, x2, ..., xn ]
简单。 :) 翻转两次根本就不是翻转。
让我们从一些外观调整开始：
-- Note that `g x` is an endomorphism.
g :: a -> ([b], [(a,b)]) -> ([b], [(a,b)])
g x ((y:ys),r) = (ys,(x,y):r)
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x k = \c -> k (c . g x)
f 将延续 (c . g x) 提供给另一个函数 (k, "double continuation",
虽然我们可能合理地期望随着折叠的进行重复使用 f 将以某种方式组成由列表元素组成的 g x 自同态，但自同态的组成顺序可能不是很明显，所以我们最好通过几个步骤来确定：
-- x0 is the first element, x1 the second, etc.
f x0 k0
\c -> k0 (c . g x0)
\c -> (f x1 k1) (c . g x0) -- k0 is the result of a fold step.
\c -> (\d -> k1 (d . g x1)) (c . g x0) -- Renaming a variable for clarity.
\c -> k1 (c . g x0 . g x1)
-- etc .
-- xa is the *last* element, xb the next-to-last, etc.
-- ka is the initial value passed to foldr.
\c -> (f xa ka) (c . g x0 . g x1 . . . g xb)
\c -> (\d -> ka (d . g xa)) (c . g x0 . g x1 . . . g xb)
\c -> ka (c . g x0 . g x1 . . . g xb . g xa)
ka，传递给 foldr 的初始值是 id，这使事情变得相当简单：
foldr f id xs = \c -> c . g x0 . g x1 . . . g xa
由于我们对传递给 foldr f id xs 的 c 参数所做的一切都是 post-composing 它与自同态，我们不妨将其排除在外：
zipRev xs ys = (snd . foldr h id xs) (ys,[])
where
h x e = g x . e
请注意我们是如何从 c . g x 发展到 g x . e 的。这可以说是原始实施中 CPS 欺骗的附带影响。
最后一步是注意 h x e = g x . e 如何与我们对 implement foldr in terms of foldMap for the Endo monoid 所做的完全对应。或者，更明确地说：
foldEndo g i xs = foldr g i xs -- The goal is obtaining an Endo-like definition.
foldEndo _ i [] = i
foldEndo g i (x : xs) = g x (foldEndo g i xs)
foldEndo g i xs = go xs i
where
go [] = \j -> j
go (x : xs) = \j -> g x (foldEndo g j xs)
foldEndo g i xs = go xs i
where
go [] = \j -> j
go (x : xs) = \j -> g x (go xs j)
foldEndo g i xs = go xs i
where
go [] = id
go (x : xs) = g x . go xs
foldEndo g i xs = go xs i
where
h x e = g x . e
go [] = id
go (x : xs) = h x (go xs)
foldEndo g i xs = go xs i
where
h x e = g x . e
go xs = foldr h id xs
foldEndo g i xs = foldr h id xs i
where
h x e = g x . e
这最终让我们找到了我们要找的东西：
zipRev xs ys = snd (foldr g (ys,[]) xs)
见解
- 延续不直接抵消。它们最终只能被取消（beta-reducing），因为有可能将它们排除在外。
- 您正在寻找的进行此转换的模式是
\k c -> k (c . f)（或者如果您喜欢不可读的 pointfree，(. (. f))）对于任何f（请注意f不是 lambda 的参数）。 - 作为
obfuscate是他们对fmap的定义。 - 从
foldr中提取这样的函数的技巧适用于任何可能是有效的函数fmap。
从第一个代码块到第二个代码块的完整转换
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x k c = k (\((y:ys),r) -> c (ys,(x,y):r))
从 lambda
中拉出c
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x k c = k (c . \((y:ys),r) -> (ys,(x,y):r))
用obfuscate代替它的定义
zipRev xs ys = foldr f id xs snd (ys,[])
where
f x = obfuscate (\((y:ys),r) -> (ys,(x,y):r))
从 lambda
中拉出obfuscate
zipRev xs ys = foldr f id xs snd (ys,[])
where
f = obfuscate . \x ((y:ys),r) -> (ys,(x,y):r)
从f
obfuscate
zipRev xs ys = foldr (obfuscate . f) id xs snd (ys,[])
where
f x ((y:ys),r) = (ys,(x,y):r)
因为obfuscate遵循函子定律，我们可以把它从foldr
zipRev xs ys = obfuscate (flip (foldr f) xs) id snd (ys,[])
where
f x ((y:ys),r) = (ys,(x,y):r)
内联obfuscate
zipRev xs ys = (\k c -> k (c . flip (foldr f) xs)) id snd (ys,[])
where
f x ((y:ys),r) = (ys,(x,y):r)
Beta-reduce
zipRev xs ys = (id (snd . flip (foldr f) xs)) (ys,[])
where
f x ((y:ys),r) = (ys,(x,y):r)
简化
zipRev xs ys = snd (foldr f (ys,[]) xs)
where
f x (y:ys,r) = (ys,(x,y):r)
从 foldr
中提取 fmap 有效函数的理由
foldr (fmap . f) z [x1,x2,...,xn]
展开foldr
(fmap . f) x1 . (fmap . f) x2 . ... . (fmap . f) xn $ z
内联内部 .s
fmap (f x1) . fmap (f x2) . ... . fmap (f xn) $ z
应用函子定律
fmap (f x1 . f x2 . ... . f xn) $ z
Eta-expand括号里的部分
fmap (\z2 -> f x1 . f x2 . ... . f xn $ z2) z
根据 foldr
fmap (\z2 -> foldr f z2 [x1,x2,...,xn]) z
根据 flip
fmap (flip (foldr f) [x1,x2,...,xn]) z
奖励：从 foldr
中提取 contramap 有效函数的理由
foldr (contramap . f) z [x1,x2,...,xn]
展开foldr
(contramap . f) x1 . (contramap . f) x2 . ... . (contramap . f) xn $ z
内联内部 .s
contramap (f x1) . contramap (f x2) . ... . contramap (f xn) $ z
应用逆变定律
contramap (f xn . ... . f x2 . f x1) $ z
Eta-expand括号里的部分
contramap (\z2 -> f xn . ... . f x2 . f x1 $ z2) z
根据 foldr
contramap (\z2 -> foldr f z2 [xn,...,x2,x1]) z
根据 flip
contramap (flip (foldr f) [xn,...,x2,x1]) z
应用foldr f z (reverse xs) = foldl (flip f) z xs
contramap (flip (foldl (flip f)) [x1,x2,...,xn]) z