时间戳

首页 > 解决方案 > 在 Scheme 中使用 foldl 实现函数 foldr

functional-programming - 在 Scheme 中使用 foldl 实现函数 foldr

问题描述

foldr(fold-right) 基本上是递归计算以存储在列表中的值的从右到左的顺序执行。并且foldl是 的倒数foldr。我想知道人们可以foldr使用来实现该功能foldl吗？任何想法都值得赞赏，在此先感谢。

标签： functional-programmingschemeracket

解决方案

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

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

我们在下面验证他们的输出——</p> 

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

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

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

推荐阅读