Реализуйте функцию foldr, используя foldl в Scheme

Question

foldr (сложение-вправо) в основном это рекурсивное вычисление выполняется в порядке справа налево значений, хранящихся в списке.И foldl является обратной foldr.Мне интересно, могут ли люди реализовать функцию foldr, используя foldl?Любая идея ценится, спасибо заранее.

Answer 1

Мне интересно, могли бы люди реализовать функцию 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))))

Мы проверяем их вывод ниже -

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

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

Так что вы, конечно, могли бы реализовать foldr, используя reverse и foldl, но это дважды обойдёт список ввода.Причина существования каждого сгиба заключается в том, что вы можете обрабатывать список в любом направлении, не просматривая его более одного раза ...

Answer 2

Решение

Просто переверните список ввода перед тем, как передать все аргументы foldl:

(define (myfoldr func init-val lst)
  (foldl func init-val (reverse lst)))

Проверьте его

Сначала:

(foldr (lambda (el acc) (list el acc))
       '()
       '(1 2 3 4 5))

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

(foldl (lambda (el acc) (list el acc))
       '()
       '(1 2 3 4 5))

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

А теперь:

(myfoldr (lambda (el acc) (list el acc))
         '()
         '(1 2 3 4 5))

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

foldl от foldr

(define (myfoldl func initial-val lst)
  (foldr func init-val (reverse lst)))

Тест:

(myfoldl (lambda (el acc) (list el acc))
         '()
         '(1 2 3 4 5))

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