накопительная рекурсивная функция для создания списка промежуточных итогов от последнего до первого - PullRequest
Новая
       79

накопительная рекурсивная функция для создания списка промежуточных итогов от последнего до первого

1 голос
/ 08 мая 2020

Пытаясь сделать это '(3 2 1) -> '(6 3 1) с накопительной рекурсией, я могу получить желаемый результат (своего рода), я имею в виду, что мои первые и вторые, кажется, расположены в правильном порядке, но мои (cons ожидает список, и я даю ему номер. Любая помощь приветствуется.

Если я заменю (cons на (list в помощнике, а я (reverse переменную li в функции, я получу '(6 3 1), которое я хотел бы, но с (list (list (list '() спереди. Я бы хотел '(6 3 1)

Вот что у меня 

(define (subtotal li)
  (subtotal-help (reverse li) 0))

(define (subtotal-help li acc)
  (cond
    [(empty? li) empty]
    [else  (list (subtotal-help (rest li)
                    (+ (first li) acc))
             (+ (first li) acc))]))

Ответы [ 2 ]

2 голосов
/ 08 мая 2020

Вы должны использовать cons для построения списка вывода, а не list. Ваш код близок к правильному, нам просто нужно перетасовать вещи и добавить один дополнительный reverse в конце: 

(define (subtotal li)
  (reverse
   (subtotal-help (reverse li) 0)))

(define (subtotal-help li acc)
  (cond
    [(empty? li) empty]
    [else (cons (+ (first li) acc)
                (subtotal-help (rest li) (+ (first li) acc)))]))

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

(define (subtotal li)
  (cond
    [(empty? li) empty]
    [else (let ((lst (reverse li)))
            (subtotal-help (rest lst) (list (first lst))))]))

(define (subtotal-help li acc)
  (cond
    [(empty? li) acc]
    [else (subtotal-help (rest li)
                         (cons (+ (first li) (first acc))
                               acc))]))

В любом случае, это работает как ожидалось: 

(subtotal '(3 2 1))
=> '(6 3 1)
1 голос
/ 08 мая 2020

Прекрасный ответ @ ÓscarLópez отвечает на непосредственный вопрос OP, но есть и другие способы решения проблемы, которые, возможно, не совсем то, что ищет профессор OP.

Можно было бы map через входной список вместе с диапазоном индексов в списке, используя drop, чтобы уменьшить список для каждого apply, который суммирует оставшийся список. Здесь _x - это (игнорируемое) значение, взятое из входного списка с помощью map, n - количество элементов в drop, а xs - это входной список: 

(define (subtotal-list xs)
  (map (lambda (_x n)
         (apply + (drop xs n)))
       xs
       (range (length xs))))

scratch.rkt> (subtotal-list '(3 2 1))
'(6 3 1)
scratch.rkt> (subtotal-list '())
'()

Между прочим, в Common Lisp есть хорошая идиома для такого рода вещей, которая работает аналогично с помощью макроса LOOP. Здесь x берет не элементы из списка xs, а весь список, и на каждой итерации x уменьшается с помощью cdr (по умолчанию): 

(defun subtotal-list-cl (xs)
  (loop
     :for x :on xs
     :collect (apply #'+ x)))

SCRATCH> (subtotal-list-cl '(3 2 1))
(6 3 1)
SCRATCH> (subtotal-list-cl '())
NIL

Возвращаясь к текущему назначению, если требуется итеративная вспомогательная процедура и если разрешено apply, то может быть определена более краткая версия хвостовой рекурсивной процедуры. Здесь, поскольку промежуточные результаты cons выводятся на переднюю часть аккумулятора, аккумулятор должен быть перевернут в конце: 

(define (subtotal-list-iter xs)
  (subtotal-list-helper xs '()))

(define (subtotal-list-helper xs acc)
  (if (null? xs) (reverse acc)
      (subtotal-list-helper (rest xs)
                            (cons (apply + xs) acc))))

scratch.rkt> (subtotal-list-iter '(3 2 1))
'(6 3 1)
scratch.rkt> (subtotal-list-iter '())
'()
...