折叠和折叠如何工作,在一个例子中分解？

Question

好的,我是scheme/racket/lisp的新手.我在练创造我自己的功能,语法和递归,所以我想我自己foldl和foldr功能是做什么的预定义的版本做.我不能这样做,因为我只是不明白这些功能是如何工作的.我在这里看到过类似的问题,但我仍然没有得到它.细分的一些例子会有所帮助!这是我的(不正确的)过程:

(foldl - 0 '(1 2 3 4))我这样做0 -(4-3-2-1),得到2,这是正确的答案

(foldl - 0 '(4 3 2 1))我做到了0-(1-2-3-4)8但应该是-2.

(foldr - 0 '(1 2 3 4))我这样做0-(1-2-3-4)又得到了8,但它应该是-2.

(foldr - 0 '(4 3 2 1))我这样做0-(4-3-2-1),得到2,这是正确的答案.

我究竟做错了什么？

Answer 1

我们来看看:(foldr - 0 '(1 2 3 4)).

这里的文字'(1 2 3 4)构造了一个列表,其元素是数字1,2,3和4.让我们明确构建列表:

(cons 1 (cons 2 (cons 3 (cons 4 empty))))

人们可以将其foldr视为一个替换cons为函数f并使用值清空的函数v.

因此

(foldr f 0 (cons 1 (cons 2 (cons 3 (cons 4 empty)))))

变

           (f 1    (f 2    (f 3    (f 4 v)))))

如果函数f为-且值为v0,您将得到:

(- 1 (- 2 (- 3 (- 4 0)))))

我们可以计算结果:

  (- 1 (- 2 (- 3 (- 4 0))))
= (- 1 (- 2 (- 3 4)))
= (- 1 (- 2 -1))
= (- 1 3)
= -2

请注意,(foldr cons empty a-list)生成副本a-list.

foldl另一方面,该函数使用另一方的值:

> (foldl cons empty '(1 2 3 4))
'(4 3 2 1)

换一种说法:

(foldl f v '(1 2 3 4))

变

(f 4 (f 3 (f 2 (f 1 v)))).

如果f是函数-且值为0,那么我们得到:

  (- 4 (- 3 (- 2 (- 1 0))))
= (- 4 (- 3 (- 2 1)))
= (- 4 (- 3 1))
= (- 4 2)
= 2

注意(foldl cons empty a-list)产生相反的a-list.