Альтернативная сумма с использованием Foldr / Foldl (Racket)

Вернемся снова с еще одним вопросом Racket. Я новичок в функциях высшего порядка в целом, так что дайте мне немного свободы.

В настоящее время пытаюсь найти переменную сумму, используя функции foldr / foldl, а не рекурсию.

например (altsum '(1 3 5 7)) должно равняться 1 - 3 + 5 - 7, что в сумме составляет -4.

Я подумал о нескольких возможных способах решения этой проблемы:

  1. Получите числа для сложения в один список и числа для вычитания в другом списке и сложите их вместе.
  2. Каким-то образом используйте длину списка, чтобы определить, прибавлять или вычитать.
  3. Может быть, сгенерируйте какую-то маску '(1 -1 1 -1), умножьте соответственно, затем сложите и сложите все.

Однако я понятия не имею, с чего начать с foldl / foldr, когда все операции не одинаковы для каждого элемента в списке, поэтому у меня возникают проблемы с реализацией какой-либо из моих идей. Кроме того, всякий раз, когда я пытаюсь добавить более двух переменных в свой анонимный класс foldl, я понятия не имею, какие переменные впоследствии относятся к каким переменным в анонимном классе.

Приветствуется любая помощь или указатели.


fold scheme racket alternating
person user2980932    schedule 15.06.2018    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Здесь мы можем использовать две процедуры более высокого порядка: foldr для обработки списка и build-list для создания списка чередующихся операций для выполнения. Обратите внимание, что foldr может принимать более одного входного списка, в этом случае мы берем список чисел и список операций и перебираем их поэлементно, накапливая результат:

(define (altsum lst)
  (foldr (lambda (ele op acc) (op acc ele))
         0
         lst
         (build-list (length lst)
                     (lambda (i) (if (even? i) + -)))))

Работает как положено:

(altsum '(1 3 5 7))
=> -4
person Óscar López    schedule 15.06.2018

arrow_upward
1
arrow_downward

Ваша идея в порядке. Вы можете использовать range, чтобы составить список чисел от 0 до длины-1 и использовать нечетность каждого для определения + или -:

(define (alt-sum lst)
  (foldl (lambda (index e acc)
          (define op (if (even? index) + -)) 
          (op acc e))
        0
        (range (length lst))
        lst))

В качестве альтернативы можно использовать библиотеку списков SRFI-1 с fold что позволяет создавать списки разной длины, а также бесконечные списки, и вместе с circular-list вы можете изменять его между + и - на протяжении lst.

(require srfi/1) ; For R6RS you import (srfi :1)

(define (alt-sum lst)
  (fold (lambda (op n result)
           (op result n))
         0
         (circular-list + -)
         lst))

(alt-sum '(1 3 5 7))
; ==> -4
person Sylwester    schedule 15.06.2018
comment
Не могу поверить, что забыл про четность / нечетность чередующихся сумм. В очередной раз благодарим за помощь. Мне также нравится функция кругового списка в библиотеке списков SRFI-1, поэтому спасибо за упоминание о ней. - person user2980932; 16.06.2018