在方案中使用 foldl 实现函数折叠器

Question

foldr(右折叠(基本上是递归计算是按列表中存储的值的从右到左的顺序执行的。foldl与foldr相反.我想知道人们可以使用foldlfoldr实现该功能吗？任何想法都是值得赞赏的，提前感谢。

Answer 1

我想知道人们可以使用foldlfoldr实现该功能...

foldl从左到右遍历列表一次 - 它也是尾递归的

(define (foldl f acc xs)
(if (null? xs)
acc
(foldl f
(f acc (car xs))
(cdr xs))))

foldr遍历列表一次，将调用堆叠起来f直到列表的最后一个元素 - 它不是尾递归的

(define (foldr f acc xs)
(if (null? xs)
acc
(f (foldr f acc (cdr xs))
(car xs))))

我们在下面验证他们的输出——

(foldl list 'init '(a b c))
;; '(((init a) b) c)
(foldr list 'init '(a b c))
;; '(((init c) b) a)

当然，您可以使用reverse和foldl来实现foldr，但这将遍历输入列表两次。每个折叠存在的原因是，您可以在任一方向上处理列表，而无需多次遍历它......

Answer 2

解决方案

只需在将所有参数传递给foldl之前反转输入列表：

(define (myfoldr func init-val lst)
(foldl func init-val (reverse lst)))

测试它

第一：

(foldr (lambda (el acc) (list el acc))
'()
'(1 2 3 4 5))
;; => '(1 (2 (3 (4 (5 ())))))
(foldl (lambda (el acc) (list el acc))
'()
'(1 2 3 4 5))
;; => '(5 (4 (3 (2 (1 ())))))

现在：

(myfoldr (lambda (el acc) (list el acc))
'()
'(1 2 3 4 5))
;; => '(1 (2 (3 (4 (5 ())))))

foldlfoldr

(define (myfoldl func initial-val lst)
(foldr func init-val (reverse lst)))

测试：

(myfoldl (lambda (el acc) (list el acc))
'()
'(1 2 3 4 5))
;; => '(5 (4 (3 (2 (1 ())))))