使用foldr实现zip

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

1> Darius Bacon..：

---

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所示.

2> Will Ness..：

---

答案已经在这里给出,但不是(说明性的)推导.所以即使经过这么多年,也许值得添加它.

它实际上非常简单.第一,

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 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

我们安排的信息通道从左向右沿列表中,通过调用 r1与其他输入列表中ys1,作为下一个步骤.就是这样.foldr f z [x2,x3,...,xn]ys1 = f x2r2ys1

---

当ys短于xs(或相同的长度),则[]对于情况f火灾和处理停止.但是,如果ys是长于xs随后f的[]情况下,将不会触发,我们会得到最终的应用,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).

所以r是"什么是有更多做ys的时候有更多x的",并且z = const [],在nil中-案例foldr,是"什么是用做ys时,有没有更多x的".或者f可以自行停止,[]在ys疲惫时返回.

---

注意如何ys用作一种累积值,它沿着列表从左向右传递xs,从一次调用f到下一次("累积"步骤,这里,从中剥离头元素).

当然,这对应于左侧折叠,其中累积步骤是"应用函数",z = id当"不再有xs" 时返回最终累积值:

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

等等

3> mattiast..：

---

我发现了一种使用与你的方法非常相似的方法:

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

4> Claudiu..：

---

对于非原生的Haskellers,我已经编写了这个算法的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 func

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))))

这是一个func,它带有一个包含两个元素的列表,现在,并将它们拉为(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拉开它的论点3.

这继续等......

5> 小智..：

---

所有这些解决方案的问题zip在于它们只折叠在一个列表或另一个列表上,如果它们都是"好的生产者",则在列表融合的说法中可能是一个问题.你真正需要的是一个折叠两个列表的解决方案.幸运的是,有一篇关于这个问题的论文,称为"具有超功能的协同折叠".

你需要一个辅助类型,一个超函数,它基本上是一个以另一个超函数作为参数的函数.

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函数串起来,端到端,直到它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确实称为列表融合,GHC.Base模块中讨论过这种情况,但可能应该更为人所知.作为一个好的列表生成器并使用build它foldr可以防止大量无用的生产和立即消耗列表元素,并且可以暴露进一步的优化.