scheme - Racket:如何使用 foldr 编写 foldl

Question

我目前正在准备考试，我认为用 foldr 编写 foldl 是一个很好的测试题。

无论如何，我知道 (foldl f base lst) 返回 (f xn (f x(n-1) . . . (f x1 base)第一个是 (x1 . . . xn)

所以我目前拥有的是:

(define (foldl/w/foldr f base lst)

(foldr (lambda (x y) (f y (f x base))) base lst)))

这不太行，我不确定如何继续。

Answer 1

使用 Haskell 的 documentation作为起点(正如@soegaard 在评论中提到的那样)，这是使用 Racket 语法解决此问题的有效解决方案:

(define (foldl/w/foldr f base lst)
  ((foldr (λ (ele acc) (λ (x) (acc (f ele x))))
          identity
          lst)
   base))

例如:

(foldl/w/foldr cons '() '(1 2 3 4 5))
=> '(5 4 3 2 1)
(foldl/w/foldr + 0 '(1 2 3 4 5))
=> 15

理解这一点的关键是，我们正在使用延迟计算而不是值来累积 lambdas，最后我们调用传递基值的所有 lambdas 链来开始计算。另请注意，identity 过程用作第一个累加器，我们在其上累加了更多的 lambda。例如，这个调用:

(foldl/w/foldr + 0 '(1 2))

将被评估如下:

((lambda (x)              ; this lambda is the value returned by foldr
   ((lambda (x)
      (identity (+ 1 x))) ; add first element in the list (this gets executed last)
    (+ 2 x)))             ; add second element in the list (this gets executed first)
 0) ; at the end, we invoke the chain of lambdas starting with the base value
=> 3