使用foldr实现zip

Question

我目前正在阅读《Real World Haskell》第4章，并试图理解如何用foldr实现foldl。

(这是他们的代码:)

myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

我想尝试使用相同的技术来实现zip，但是似乎没有取得任何进展。这种实现方式是否可行？

- itsadok

Answer 1

zip2 xs ys = foldr step done xs ys
  where done ys = []
        step x zipsfn []     = []
        step x zipsfn (y:ys) = (x, y) : (zipsfn ys)

这是如何工作的：(foldr step done xs) 返回一个消耗ys的函数；因此，我们沿着xs列表向下构建一个嵌套的函数组合，每个函数将应用于ys的相应部分。

如何想到它：我从之前看到的类似示例的一般想法开始，写下

zip2 xs ys = foldr step done xs ys

接着，每一行都被填写为使类型和值正确的内容。最好先考虑简单的情况，再考虑更难的情况。

第一行可以更简单地写成

zip2 = foldr step done

正如mattiast所展示的。

- Darius Bacon

---

你很邪恶... 你不是在说将 (foldr step done xs) 应用到 ys 上吗？ - Claudiu

但是从等式的角度来看会更容易理解。我从第一行开始，然后依次填写每个剩余部分，以使类型和值正确。 - Darius Bacon

步进函数最终如何需要三个参数？据我所知，步进函数只需要两个参数（累加器和列表的下一个元素）。这里第三个参数用于什么？ - Tom Crayford

foldr只使用2个参数来调用它，对吗？所以从foldr调用的结果是一个带有一个参数的新函数。最终，该函数在定义zip2的顶级表达式中应用于ys。（在Haskell中，类似f x y z = u这样的定义与f = \x -> \y -> \z -> u的含义相同） - Darius Bacon

在链接中有一篇论文证明了如何使用foldr来编写函数。您能否使用相同的方法证明上述函数？ - Dragno

Answer 2

答案已经在这里给出了，但是没有（图解）推导过程。因此即使这么多年过去了，也值得加上它。

这其实非常简单。首先，

foldr f z xs 
   = foldr f z [x1,x2,x3,...,xn] = f x1 (foldr f z [x2,x3,...,xn])
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...)))

因此通过 eta 扩展，

foldr f z xs ys
   = foldr f z [x1,x2,x3,...,xn] ys = f x1 (foldr f z [x2,x3,...,xn]) ys
   = ... = f x1 (f x2 (f x3 (... (f xn z) ...))) ys

如此显然，如果 f 在第二个参数中不强制求值，那么它会先处理 x1 和 ys，其中 f x1r1ys，其中 r1 =(f x2 (f x3 (... (f xn z) ...)))= foldr f z [x2,x3,...,xn]。

因此，使用

f x1 r1 [] = []
f x1 r1 (y1:ys1) = (x1,y1) : r1 ys1

我们通过使用输入列表的其余部分 ys1 来排列信息从左向右沿着列表进行传递，f x2r2ys1，作为下一步。就是这样。

---

当 ys 比 xs（或相同长度）短时，f 的 [] 情况会触发并停止处理。但如果 ys 长于 xs，那么 f 的 [] 情况就不会触发，我们将获得最终的 f xnz(yn:ysn) 应用：

由于我们已经到达了xs的末尾，因此zip处理必须停止：

z _ = []

这意味着应该使用定义z = const []：

zip xs ys = foldr f (const []) xs ys
  where
    f x r []     = []
    f x r (y:ys) = (x,y) : r ys

从 f 的角度来看，r 扮演着一个“成功继续”的角色，在发出对 (x, y) 的处理后，f 调用它以进行处理。

因此，r 就是“当有更多的 x 时会发生什么”，并且 z = const []，即在 foldr 中的空情况，就是“当没有更多的 x 时会发生什么”。或者当 ys 用尽时，f 可以自行停止并返回 []。

---

请注意，ys 被用作一种累积值，沿着列表 xs 从左到右传递，从一次调用 f 到下一次（这里的“累积”步骤是将其头元素剥离）。

自然地，这对应于左折叠，在其中，累积步骤是“应用函数”，使用 z = id 在“没有更多的 x”时返回最终累积值：

foldl f a xs =~ foldr (\x r a-> r (f a x)) id xs a

同样地，对于有限列表，

foldr f a xs =~ foldl (\r x a-> r (f x a)) id xs a

由于组合函数可以决定是否继续，现在可以有一个能够提前停止的左折叠（left fold）：

foldlWhile t f a xs = foldr cons id xs a
  where 
    cons x r a = if t x then r (f a x) else a

或者跳过左折叠，foldlWhen t ...，具有

    cons x r a = if t x then r (f a x) else r a

etc.

- Will Ness

Answer 3

我找到了一种与你的方法非常相似的方式:

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []

- mattiast

Answer 4

对于不是母语为Haskell的人，我编写了一个Scheme版本的算法，以便更清楚地了解实际发生的情况：

> (define (zip lista listb)
    ((foldr (lambda (el func)
           (lambda (a)
             (if (empty? a)
                 empty
                 (cons (cons el (first a)) (func (rest a))))))
         (lambda (a) empty)
         lista) listb))
> (zip '(1 2 3 4) '(5 6 7 8))
(list (cons 1 5) (cons 2 6) (cons 3 7) (cons 4 8))

foldr函数返回一个函数，应用到一个列表上会返回该列表与另一个给定的列表合并所得的结果。由于Haskell采用了惰性评估，因此隐藏了内部的lambda。

---

进一步解释：

以输入'(1 2 3)进行zip操作。 然后将得到的列表传递给foldr函数。

el->3, func->(lambda (a) empty)

这将扩展为：

(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a))))

如果现在返回这个结果，我们将得到一个接受一个元素列表并返回一个包含3个元素的元组的函数。

> (define f (lambda (a) (cons (cons 3 (first a)) ((lambda (a) empty) (rest a)))))
> (f (list 9))
(list (cons 3 9))

继续往下，foldr现在使用func进行调用。

el->3, func->f ;using f for shorthand
(lambda (a) (cons (cons el (first a)) (func (rest a))))
(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

这是一个接受包含两个元素的列表作为参数的函数，现在将它们与 (list 2 3) 进行压缩：

> (define g (lambda (a) (cons (cons 2 (first a)) (f (rest a)))))
> (g (list 9 1))
(list (cons 2 9) (cons 3 1))

发生了什么？

(lambda (a) (cons (cons 2 (first a)) (f (rest a))))

在这种情况下，a 是 (列表 9 1)。

(cons (cons 2 (first (list 9 1))) (f (rest (list 9 1))))
(cons (cons 2 9) (f (list 1)))

正如你所记得的那样，f 将其参数与 3 进行压缩。

然后这个过程继续等等...

- Claudiu

Answer 5

所有这些有关 zip 的解决方案都存在一个问题，那就是它们只能在一个列表或另一个列表上进行折叠，如果两个列表都是“好的生产者”（即列表融合的术语），这可能会成为一个问题。实际上，您需要的是一个可以同时遍历这两个列表的解决方案。幸运的是，有一篇论文专门讨论了这个问题，名为 "Coroutining Folds with Hyperfunctions"。

您需要一个辅助类型，超函数，它基本上是一种将另一个超函数作为其参数的函数。

newtype H a b = H { invoke :: H b a -> b }

这里使用的超函数基本上像普通函数的“堆栈”一样运作。

push :: (a -> b) -> H a b -> H a b
push f q = H $ \k -> f $ invoke k q

您还需要一种将两个超函数放在一起的方法，端对端。

(.#.) :: H b c -> H a b -> H a c
f .#. g = H $ \k -> invoke f $ g .#. k

这与法律相关的是 push：

(push f x) .#. (push g y) = push (f . g) (x .#. y)

这实际上是一个关联运算符，这是它的身份标识：

self :: H a a
self = H $ \k -> invoke k self

你还需要一些东西，它可以忽略“堆栈”上的所有其他内容并返回特定的值：

base :: b -> H a b
base b = H $ const b

最后，您需要一种从超函数中获取值的方式：

run :: H a a -> a
run q = invoke q self

run函数将所有push的函数按顺序连接起来，直到遇到base或无限循环为止。

现在，您可以使用将信息从一个列表传递到另一个列表的函数将两个列表合并成超级函数，并组装最终值。

zip xs ys = run $ foldr (\x h -> push (first x) h) (base []) xs .#. foldr (\y h -> push (second y) h) (base Nothing) ys where
  first _ Nothing = []
  first x (Just (y, xys)) = (x, y):xys

  second y xys = Just (y, xys)

折叠两个列表的原因是因为 GHC 所做的一种称为 list fusion 的操作，这在 GHC.Base 模块 中有所提及，但可能应该更为广为人知。作为一个优秀的列表生产者，使用 build 和 foldr 可以防止大量无用的列表元素生产和立即消耗，并且可以暴露出更多的优化。

- Zemyla

Answer 6

我尝试理解这个优雅的解决方案，所以我试着自己推导类型和评估。因此，我们需要编写一个函数：

zip xs ys = foldr step done xs ys

在这里，我们需要推导出step和done，无论它们是什么。回想一下foldr的类型，在应用于列表时：

foldr :: (a -> state -> state) -> state -> [a] -> state

然而，我们的foldr调用必须被实例化为以下内容之一，因为我们必须接受不只是一个，而是两个列表参数：

foldr :: (a -> ? -> ?) -> ? -> [a] -> [b] -> [(a,b)]

因为 -> 是右结合的，所以这等同于：

foldr :: (a -> ? -> ?) -> ? -> [a] -> ([b] -> [(a,b)])

我们的 ([b] -> [(a,b)]) 对应于原始的 foldr 类型签名中的 state 类型变量，因此我们必须用它替换每个出现的 state：

foldr :: (a -> ([b] -> [(a,b)]) -> ([b] -> [(a,b)]))
      -> ([b] -> [(a,b)])
      -> [a]
      -> ([b] -> [(a,b)])

这意味着我们传递给foldr的参数必须具有以下类型：

step :: a -> ([b] -> [(a,b)]) -> [b] -> [(a,b)]
done :: [b] -> [(a,b)]
xs :: [a]
ys :: [b]

回顾一下，foldr (+) 0 [1,2,3]扩展成:

1 + (2 + (3 + 0))

因此，如果 xs = [1,2,3] 并且 ys = [4,5,6,7]，我们的 foldr 调用将扩展为：

1 `step` (2 `step` (3 `step` done)) $ [4,5,6,7]

这意味着我们的1 `step` (2 `step` (3 `step` done))结构必须创建一个递归函数，该函数将遍历[4,5,6,7]并压缩元素。 （请记住，如果原始列表中有一个更长，那么多余的值将被丢弃）。 换句话说，我们的结构必须具有类型[b] -> [(a,b)]。 3 `step` done是我们的基本情况，其中done是初始值，例如在foldr (+) 0 [1..3]中的0。 我们不想在3之后压缩任何内容，因为3是xs的最终值，所以我们必须终止递归。 如何在基本情况下终止列表上的递归？ 您返回空列表[]。 但请注意done类型签名：

done :: [b] -> [(a,b)]

因此，我们不能仅仅返回[]，我们必须返回一个函数来忽略所接收到的任何内容。因此使用const：

done = const [] -- this is equivalent to done = \_ -> []

现在让我们开始确定什么是“step”。它将类型为“a”的值与类型为“[b] -> [(a,b)]”的函数结合起来，并返回类型为“[b] -> [(a,b)]”的函数。

在“3 `step` done”中，我们知道稍后要进入我们的压缩列表的结果值必须是“(3,6)”（从原始的“xs”和“ys”得知）。因此，“3 `step` done”必须计算为：

\(y:ys) -> (3,y) : done ys

记住，我们必须返回一个函数，在其中将元素压缩在一起，上面的代码是有意义且类型检查的。

现在我们假设了step应该如何评估，让我们继续评估。以下是我们foldr评估中所有缩减步骤的样子：

3 `step` done -- becomes
(\(y:ys) -> (3,y) : done ys)
2 `step` (\(y:ys) -> (3,y) : done ys) -- becomes
(\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys)
1 `step` (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) -- becomes
(\(y:ys) -> (1,y) : (\(y:ys) -> (2,y) : (\(y:ys) -> (3,y) : done ys) ys) ys)

评估结果导致了此步骤的实现（请注意，我们通过返回空列表来解决ys提前用完元素的问题）：

step x f = \[] -> []
step x f = \(y:ys) -> (x,y) : f ys

因此，完整的 zip 函数实现如下：

zip :: [a] -> [b] -> [(a,b)]
zip xs ys = foldr step done xs ys
  where done = const []
        step x f [] = []
        step x f (y:ys) = (x,y) : f ys

P.S.: 如果您受到折叠优雅的启发，请阅读使用foldr编写foldl，然后再阅读Graham Hutton的关于fold的普适性和表达能力的教程。

- Mirzhan Irkegulov

---

非常好，从类型开始很好，使用通用的示例数据然后泛化也很好，尽管我仍然更喜欢从上到下进行，因为这才是foldr实际上正在做的。 :) - Will Ness

Answer 7

一个简单的方法：

lZip, rZip :: Foldable t => [b] -> t a -> [(a, b)]

-- implement zip using fold?
lZip xs ys = reverse.fst $ foldl f ([],xs) ys
     where f  (zs, (y:ys)) x = ((x,y):zs, ys)

-- Or;
rZip xs ys = fst $ foldr f ([],reverse xs) ys
     where f x (zs, (y:ys))  = ((x,y):zs, ys)

- guthrie

---

请注意，如果 xs 和 ys 的长度不同，则 rZip 将无法正常工作。 - Torsten Grust