Reverse a list in Scheme with foldl and foldr

问题:

How can you define a function to reverse a list in Scheme by using foldr and foldl?

What we want is a succinct solution to reverse a list in Scheme using a foldl call and a different solution using a foldr call, as defined:

(define (foldl operation lst initial)
    (if (null? lst) initial
        (foldl operation 
               (cdr lst) 
               (operation (car lst) initial))))

and

(define (foldr operation lst initial)
    (if (null? lst) initial
        (operation 
            (car lst) 
            (foldr operation (cdr lst) initial))))

The astute person will observe that the foldl implementation is tail-recursive because the returned value is computed as each recursive step is called - at the last step the entire answer is already computed and simply returned up the chain.

The foldr implementation is not tail-recursive because it must build the returned value by using the values that are passed back up the recursive chain.

Therefore, the two Scheme implementations that we are interested in should be in the following form,

(define (rev1 lst)
    (foldl ___________________________

**Solution:**
(define (rev1 lst)
    (foldl cons lst '()))

and

(define (rev2 lst)
    (foldr ___________________________

**Solution 1:**
(define (rev2 lst)
    (foldr 
       (lambda (element accumulator) 
               (foldr cons accumulator (cons element '())))
       lst '())) 

**Solution 2:**
(define (rev2 lst)
    (foldr 
       (lambda (element accumulator) 
               (append accumulator (cons element '())))
       lst '())) 

The end goal is to be able to call the following,

(rev1 '(1 2 3)) -> (3 2 1)
(rev2 '(1 2 3)) -> (3 2 1)

The foldl solution should be relatively trivial (based on our intuition), but the foldr solution will probably require some more thought.

Previous questions similar (but far less documented) to this question ended up unanswered and/or closed.

回答1:

This looks like homework, so I'll give you some hints to get you started. The foldl case is trivial, you just have to discover the right function to pass, and remember: foldl can be visualised as processing the list backwards (last element first, first element last), so all you have to do is stick together the current element in the list with the accumulated value:

(define (rev1 lst)
  (foldl <???> lst '()))

The foldr case is only slightly harder, just remember that foldr processes the elements in the list in the same order as they appear in the input list. Again, you have to discover the correct procedures to call:

(define (rev2 lst)
  (foldr (lambda (e a)
           <???>)
         lst
         '()))

You need to somehow put e (the current element) at the end of a, the accumulated value. Hint: you'll find that append and list are useful here.

回答2:

Your rev1 'solution' doesn't compile... it would if you replaced list with l

> (define (rev1 l) 
    (foldl cons l '()))
> (rev1 '(1 2 3))
(3 2 1)

For your rev2 this works as the body:

> (foldr (lambda (a b) (append b (list a))) '(1 2 3) '())
(3 2 1)