使用相同的辅助功能使用 foldr 和 foldl 反转列表

Question

1. (define (rev1 ls) (foldr g '() (map f ls))) 
2. (define (rev2 ls) (foldl g '() (map f ls)))

我需要定义 f 和 g 以便 rev1 和 rev2 产生给定列表 ls 的反向，其中其他定义如下

(define (foldl op z ls) 
   (if (null? ls) 
       z 
       (foldl op (op z (car ls)) (cdr ls))))

(define (snoc x y) (cons y x))

(define (foldr op z ls)
     (if (null? ls)
        z
        (op (car ls) (foldr op z (cdr ls)))))

我不确定如何定义 f 和 g 使 1 和 2 都产生相反的参数列表。

Answer 1

这是一个相当人为的练习，但无论如何 - 这些程序应该有效：

(define f list)

(define (g e acc)
  (append acc e))

例如：

(rev1 '(1 2 3 4 5))
=> '(5 4 3 2 1)

(rev2 '(1 2 3 4 5))
=> '(5 4 3 2 1)

Answer 2

有趣的问题。你可以用递归思维和等式推理来攻击它（在代码中用等号代替等号）。

首先重写：

(rev1 ls) 
 = (letrec ( (rev1 (lambda (ls)
                     (foldr g '() (map f ls)) )) ) 
     (rev1 ls))

 = (letrec ( (rev1 (lambda (ls)
                     (foldr g '() (map f ls)) )) ) 
     (foldr g '() (map f ls)))

 = (letrec ( (rev1  (lambda (ls)
                      (foldr g '() (map f ls)) )) 
             (foldr (lambda (op z ls)
                     (if (null? ls)
                       z
                       (op (car ls) (foldr op z (cdr ls)))) )) ) 
     (foldr g '() (map f ls)))

 = (letrec ( (foldr (lambda (op z ls)
                     (if (null? ls)
                       z
                       (op (car ls) (foldr op z (cdr ls)))) ))
             (rev11 (lambda (ls)
                      (if (null? ls)
                        '()
                        (g (f (car ls)) (foldr g '() (map f (cdr ls))))) )) ) 
     (rev11 ls))

 = (letrec ( (rev11 (lambda (ls)
                      (if (null? ls)
                        '()
                        (g (f (car ls)) (rev11 (cdr ls)))) )) ) 
     (rev11 ls))

因为(map f (cons x xs)) == (cons (f x) (map f xs))。

同样，

(rev2 ls)
 = (letrec ( (rev2 (lambda (ls)
                     (foldl g '() (map f ls)) )) )
     (rev2 ls))

 = (letrec ( (rev2  (lambda (ls)
                      (foldl g '() (map f ls)) ))
             (foldl (lambda (op z ls) 
                      (if (null? ls) 
                        z 
                        (foldl op (op z (car ls)) (cdr ls))) )) )
     (foldl g '() (map f ls)))

 = (letrec ( (rev22 (lambda (z ls) 
                      (if (null? ls) 
                        z 
                        (rev22 (g z (f (car ls))) (cdr ls))) )) )
     (rev22 '() ls))

（完成二次推导中遗漏的步骤）。

因此我们推导出了新的定义

(define (rev11 ls)    (if (null? ls)    ; (rev1 ls) == (rev11 ls)
                        '()
                        (g (f (car ls)) (rev11 (cdr ls)))) )

(define (rev22 z ls)  (if (null? ls)    ; (rev2 ls) == (rev22 '() ls)
                        z 
                        (rev22 (g z (f (car ls))) (cdr ls))) )

现在我们可以应用一些递归思想。假设 rev11 做了它应该做的事——反转给定的列表。因此，对于列表 ls == [a,b,c,...,n]、

(rev1 ls)
  = (rev11 ls)
  = (rev11 [a,b,c,...,n])
  = (g (f a) (rev11 [b,c,...,n]))
  = (g (f a) [n,...,c,b])    ; by assumption
  ; must be equal to
  = [n,...,c,b,a]

我们如何将 a 和列表 xs 结合起来得到一个新的列表，就像 xs 的末尾有 a 一样？

  = (append [n,...,c,b] (list a))

因此 f == list 和 (g x y) == (append y x)。我们已经得出了 !

中的定义

现在我们必须看看 rev22 发生了什么。如果f和g不一样，说明原题无解

(rev2 ls)
= (rev22 '() ls)
= (rev22 '() [a,b,c,...,n])
= (rev22 (g '() (f a)) [b,c,...,n])
= (rev22 (g (g '() (f a)) (f b)) [c,...,n])
= ...

很容易看出，相同的 f 和 g 在这里也起作用。

非巧合的是，rev22 等价于 append-reverse, or Common Lisp's revappend，参数顺序翻转。

另一种更伪代码的两种定义写法，[]代表'()，{x}代表(f x) 和 x + y 对于 (g x y)，是

(rev1 [a,b,...,n]) = {a} + ({b} + ({c} + (... + ({n} + [])...)))
                   = {a} + (rev1 [b,...,n])

(rev2 [a,...,m,n]) = (...((([] + {a}) + {b}) + {c}) + ...) + {n}
                   = (rev2 [a,...,m]) + {n}

现在解决方案似乎不言自明了！

请注意，您的 foldl 定义使用 Haskell's order of arguments to the g operator. In Racket 顺序被翻转 – z 作为 last 参数出现，而不是第一。因此，等式将变为

(rev1 [a,b,...,n]) = {a} + (rev1 [b,...,n])
(rev2 [a,...,m,n]) = {n} + (rev2 [a,...,m])

并且对于第二个等式 + == g == append 没有翻转参数顺序。那么修改后的谜题好像解不出来了

使用相同的辅助功能使用 foldr 和 foldl 反转列表

Reverse a list with foldr and foldl using the same auxiliary functions

scheme

reverse

list

fold