球拍：如何使用foldr编写foldl

Question

我正在准备考试，并认为用foldr编写foldl将是一个很好的问题，以进行测试。

无论如何，我知道（foldl f base lst）返回（f xn（f x（n-1）...（f x1 base），其中lst为（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过程被用作第一个累加器，并且我们在它上面积累了更多的lambdas。例如，这个电话：

(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

Answer 2

我不是一个Lisp程序员，所以这可能在语法上并不完美，但它会是类似的

foldl f a l = (foldr (lambda (h p) (lambda (x) (p (f x h))) )
                     l
                     (lambda (x) (x))
                     a))

诀窍是累积函数而不是结果值。我将四个参数应用于foldr，因为在这种情况下，常规foldr返回函数，将“a”作为参数。