Реализовать функцию foldr с использованием foldl на схеме

голоса
1

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

Задан 20/10/2018 в 05:00
источник пользователем
На других языках...                            


2 ответов

голоса
2

Я задаюсь вопросом , что люди могли реализовать функцию , 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, но это будет проходить список ввода дважды. Причина каждый раз существует, так что вы можете обработать список в любом направлении , не пересекая ее несколько раз ...

Ответил 21/10/2018 в 05:25
источник пользователем

голоса
0

Решение

Просто обратный ввод-список , прежде чем передать все аргументы 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 ())))))
Ответил 20/10/2018 в 10:29
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more