20

我目前正在阅读 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使用相同的技术来实现，但我似乎没有取得任何进展。甚至可能吗？

4

7 回答 7

19 
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所示。

于 2008-10-24T20:47:12.707 回答
13

答案已经在这里给出，但不是（说明性的）推导。因此，即使经过这么多年，也许值得添加它。

其实很简单。第一的，

折叠 fz xs
   = 折叠 fz [x1,x2,x3,...,xn] = f x1 (折叠 fz [x2,x3,...,xn]) 
   = ... = f x1 (f x2 (f x3 (.. . (f xn z) ...)))

因此通过 eta 展开，

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

在这里很明显，如果f在它的第二个参数中是非强制的，它首先在x1and上工作ys，在哪里。f x1r1ysr1 =(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

我们通过调用输入列表的其余部分来安排信息从左到右的传递，作为下一步。就是这样。 r1ys1foldr f z [x2,x3,...,xn]ys1 = f x2r2ys1

当ys短于xs（或相同长度）时，[]火灾f和处理停止。但是 if ysis long than xsthenf的[]情况不会触发，我们将进入最终应用程序，f xnz(yn:ysn)

f xn z (yn:ysn) = (xn,yn) : z 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它扮演着成功延续f的角色，在发出对之后，当处理要继续时调用(x,y)。

“当有更多s 时如何处理更多”也是如此，并且中的-caser是“当没有更多s 时如何处理”。或者可以自己停下来，累了就回来。ysxz = const []nilfoldrysxf[]ys

请注意如何ys将其用作一种累积值，它沿着 list 从左到右传递xs，从一次调用f到下一次调用（“累积”步骤在这里是从其中剥离一个 head 元素）。

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

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

并且由于组合函数可以决定是否继续，现在可以有可以提前停止的左折叠：

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

等等

于 2014-10-09T18:04:31.303 回答
10

我找到了一种使用与您的方法非常相似的方法：

myzip = foldr step (const []) :: [a] -> [b] -> [(a,b)]
    where step a f (b:bs) = (a,b):(f bs)
          step a f [] = []
于 2008-10-24T20:47:08.273 回答
8

对于这里的非本地 Haskeller，我编写了该算法的 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是一个函数，当应用于列表时，将返回列表的 zip 与给定函数的列表折叠在一起。lambda由于惰性求值，Haskell 隐藏了内部。

进一步分解：

输入 zip：'(1 2 3) 调用 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))))

这是一个函数，它现在接受一个包含两个元素的列表，然后用 zip 压缩它们(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，在这种情况下，是(list 9 1)

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

而且，您还记得，f它的论点用 .zip 压缩3。

这继续等等......

于 2008-10-24T21:00:15.347 回答
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将所有pushed 函数首尾相连，直到遇到 abase或无限循环。

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

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 所做的称为列表融合的东西，在 GHC.Base 模块中讨论过，但可能应该更知名。成为一个好的列表生成器并使用buildwithfoldr可以防止大量无用的生成和立即消耗列表元素，并且可以进一步优化。

于 2017-03-01T21:47:52.047 回答
2

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

zip xs ys = foldr step done xs ys

在这里，我们需要导出stepand done，无论它们是什么。Recallfoldr的类型，实例化为列表：

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

但是，我们的foldr调用必须实例化为如下所示，因为我们必须接受的不是一个，而是两个列表参数：

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

因为->是右关联的，这相当于：

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

我们([b] -> [(a,b)])对应state于原始foldr类型签名中的类型变量，因此我们必须用它替换每一个出现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]并压缩元素。（请记住，如果原始列表之一较长，则多余的值将被丢弃）。IOW，我们的构造必须具有类型[b] -> [(a,b)]。

3 `step` done是我们的基本情况，其中done是一个初始值，如0. foldr (+) 0 [1..3]我们不想在 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

PS：如果你受到优雅折叠的启发，请阅读使用 foldr 编写 foldl，然后阅读 Graham Hutton 的关于 fold 的普遍性和表现力的教程。

于 2016-01-12T12:44:24.050 回答
0

一个简单的方法：

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)
于 2017-11-30T04:38:36.947 回答