Схема - добавление в конец списка - PullRequest
Новая
       21

Схема - добавление в конец списка

2 голосов
/ 29 июня 2019

Мне очень жаль за такой простой вопрос. Это так тривиально, я не смог найти кого-то онлайн с этой проблемой. Так что я был бы признателен за помощь.

Я хочу написать очень простую функцию, которая принимает список и элемент и добавляет этот элемент в конец списка.

Функция, которую я написал рекурсивно, переходит в конец списка и возвращает новый элемент. Это так расстраивает, что это не работает. Это самая простая функция, которую я когда-либо видел 

(define (my-append lst item)
  (if (null? lst)
    item
    (cons (car lst) (my-append (cdr lst) item))))

(display (my-append (list 1 2 3 4) 5))

Отображает 

(1 2 3 4 . 5)

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

Я просто хочу увидеть 

(1 2 3 4 5)

Я бы очень признателен за некоторую помощь, потому что я чрезвычайно разочарован этим. Если это поможет, я запускаю этот код с помощью онлайн-компилятора https://repl.it/languages/scheme

Ответы [ 2 ]

3 голосов
/ 29 июня 2019

. есть, потому что последняя пара в вашем результирующем списке не имеет своего cdr, указывающего на пустой список.Правильный список - это цепочка пар, где последний cdr в цепочке указывает на пустой список.Например, 

(list 1 2 3 4 5)
# is equivalent to
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '()))))

Но список, который вы создаете: 

(cons 1 (cons 2 (cons 3 (cons 4 5)))

Вы получаете . в списке по той же причине, что (cons 4 5) печатается как (4 . 5).

При написании рекурсивной функции вам необходимо подумать о следующем:

  1. Каков базовый случай ввода?
  2. Что должна вернуть функция для этогоinput?
  3. В неосновных случаях как мне упростить ввод, чтобы приблизиться к основанию?
  4. Как объединить результат рекурсивного вызова с вводом?

У вас все в порядке, кроме шага 2.

Рассмотрим базовый случай: 

(my-append '() 5)

Это должно вернуть (5), верно?Но ваша функция просто вернет 5.Это означает, что вам нужно обернуть item в список в базовом случае. 

(define (my-append lst item)
  (if (null? lst)
    (list item)
    (cons (car lst) (my-append (cdr lst) item))))

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

3 голосов
/ 29 июня 2019

Вам просто нужно закончить рекурсию списком , а не элементом.Вместо этого: 

(if (null? lst)
    item

Сделайте это: 

(if (null? lst)
    (list item)

Для пояснения - список в схеме должен заканчиваться пустым списком '().Если ваша рекурсия заканчивается предметом, в конце вы получите что-то вроде этого: 

(cons 4 5)
=> '(4 . 5)

Это cons пара .Правильный список заканчивается пустым списком: 

(cons 4 (cons 5 '()))
=> '(4 5)

Что совпадает с: 

(cons 4 (list 5))
=> '(4 5)

Кстати, это идиоматический способ добавить элемент в конец:

(define (my-append lst item)
  (append lst (list item)))
...