Схема: использование абстрактных функций списка без рекурсии

Question

Как написать функцию, используя функции абстрактного списка (foldr, foldl, map и filter) без рекурсии, которая использует список чисел (list a1 a2 a3 ...) и производит переменную сумму a1 - a2 + a3 ...

Answer 1

Вот подсказка:

a1 - a2 + a3 - a4 ... aN

совпадает с

a1 - (a2 - (a3 - (a4 - ... (aN - 0) ...)))

Очевидно ли, как решить это сейчас?

Answer 2

Это домашняя работа?Что ж, мы можем разбить эту проблему на две подзадачи:

• Взять список (a1 a2 a3 a4 ... a2n-1 a2n) и поочередно отвергнуть элементы из него, чтобы получить (a1 (- a2) a3 (- a4) ... a2n-1 (- a2n)).
• Суммировать элементы этогорезультирующий список.

Вторая часть - тривиальная:

(define (sum xs)
  (foldl + 0 xs))

Первая - более сложная, но не слишком сложная.Вам необходимо преобразовать список, сохраняя логическое состояние, которое указывает, проверяете ли вы четный или нечетный элемент, и отменять или нет соответственно.Я вижу три способа сделать это:

• Мутационный путь: поместить состояние в замыкание, которое вы передаете в map.Затем замыкание изменяет свою среду от одного вызова к следующему.
• Сохранение состояния в результатах сгиба: результатом сгиба является пара, которая содержит "реальный" результат и состояние в качестве элемента.
• Используйте другой вид функции абстрактного списка.

Вот пример третьего подхода (и если это для домашней работы, держу пари, ваш учитель может быть просто недоверчив, что вы придумали его):

(define (contextual-foldr compute-next
                          compute-init
                          advance-context
                          left-context
                          xs)
  (if (null? xs)
      (compute-rightmost-result left-context)
      (compute-next left-context
                    (car xs)
                    (contextual-foldr compute-next
                                      compute-init
                                      advance-context
                                      (advance-context (car xs) left-context)
                                      (cdr xs)))))

(define (contextual-map contextual-fn advance-context left-context xs)
  (contextual-foldr (lambda (left elem rest)
                      (cons (fn left elem) rest))
                    '()
                    advance-context
                    left-context
                    xs))

(define (alternate-negations xs)
  (contextual-map (lambda (negate? elem)
                    (if negate?
                        (- elem)
                        elem))
                  not
                  #f
                  xs))

Answer 3

Вот возможное решение:

(define (sum-abstract-list-functions lst)
  (car
   (foldl
    (lambda (e acc)
      (cons (+ (car acc) (* e (cdr acc)))
            (- (cdr acc))))
    '(0 . 1)
    lst)))

Я использую только foldl, cons, car, cdr. Трюк? накапливая два значения: фактическую сумму (в части car аккумулятора) и знак тока (+/- 1 в части cdr аккумулятора). Аккумулятор инициализируется в 0 для суммы и +1 для знака, и в конце я возвращаю сумму, car часть аккумулятора. Используйте это так:

(sum-abstract-list-functions (list 1 2 3 4 5))
> 3

РЕДАКТИРОВАТЬ:

Как уже указывалось, это решение является самым простым из всех:

(define (sum-abstract-list-functions lst)
  (foldr - 0 lst))