Схема - Рекурсия: Сумма последовательных элементов списка

Question

Я пытаюсь написать функцию, используя схему, которая:

1. взять список целых чисел с более чем двумя элементами в качестве параметра
2. сумма п -й элемент и (п + 1) -й элемент
3. возвращение этого список

Результат должен быть следующими:

> (SumNeighbors (list 1 2 3 4)) 
(3 5 7) 

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

(define (SumNeighbors lst) 
    (if (not (null? (cdr lst))) 
     (append (list (+ (car lst) (car (cdr lst)))) (SumNeighbors (cdr lst))))) 

Любая помощь будет оценена.

Answer 1

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

(define (SumNeighbors lst) 
    (if <???>     ; if there's only one element left 
     <???>     ; we're done, return the empty list 
     (cons     ; otherwise call `cons` 
     (+ <???> <???>)   ; add first and second elements 
     (SumNeighbors <???>)))) ; and advance recursion 

Обратите внимание на следующее:

• Ваше решение отсутствует базовый вариант - то, что происходит, когда список, который мы просматриваем, имеет только один элемент? пришло время закончить рекурсию! и потому что мы строим список в качестве вывода, каково должно быть возвращаемое значение?
• Мы обычно используем cons для создания выходного списка, а не append. Это естественный способ построения списка.
• Часть этой процедуры, которая выходит за пределы шаблона решения, заключается в том, что мы останавливаемся, когда в списке остается только один elment, а не когда список пуст (как и обычный случай)

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

Answer 2

#!r6rs 
(import (except (rnrs base) map) 
     (only (srfi :1) map)) 

(define (sum-neighbors lst) 
    (map + lst (cdr lst))) 

Чем выше порядок функции map, как определено в SRFI-1 поддерживает неровные аргументы длина. Он остановится в кратчайшем списке.

Если вы звоните (sum-neighbors '(1 2 3 4)) станет (map + (1 2 3 4) (2 3 4)), который так же, как (cons (+ 1 2) (cons (+ 2 3) (cons (+ 3 4) '())))