Схема получения последнего элемента в списке

Question

Я очень плохо знаком со схемой и идеями car, cdr и т. Д. У меня есть эта функция для возврата последнего элемента списка, но сейчас он просто возвращает пустой список.

 (define (last mylist)
      (if (list? mylist)
              (if (null? mylist)
                  (if (null? (cdr mylist))
                      '()
                      (last (cdr mylist)) 
                   )
              )        
      )
)

Answer 1

По одному вашему отступу очень очевидно, что вы переходите на Scheme с другого языка программирования

Но вы также используете if неправильно - в схеме нельзя иметь одну ветку if заявление. Ну, в Scheme вообще нет операторов, только выражения и if выражения всегда будут принимать 3 операнда (аргумента)

1. предикат (условие)
2. последующее (что произойдет, если предикат верен)
3. альтернатива (что происходит, когда предикат ложен)

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

(define (last mylist)
  (if (null? mylist)
      #f
      (if (null? (cdr mylist))
          (car mylist)
          (last (cdr mylist)))))

Наконец, схема предлагает cond это помогает предотвратить вложение ненужного кода для последовательности условий

(define (last mylist)
  (cond ((null? mylist)
         #f)
        ((null? (cdr mylist))
         (car mylist))
        (else
         (last (cdr mylist)))))

(last '())
;; #f

(last '(1))
;; 1

(last '(1 2))
;; 2

(last '(1 2 3))
;; 3

За рамками этого ответа находится возвращаемое значение #f за (last '()) - Я бы сказал, что зовет last в пустом списке должен иметь такой же эффект вызова car в пустом списке. Но я оставлю это на ваше усмотрение.

Answer 2

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

• сформулировать определение данных для непустых списков (или взять его из книги)
• написать заявление о цели, подпись и заголовок для вашей функции
• НАПИСАТЬ ТЕСТОВЫЕ СЛУЧАИ (ваши тестовые примеры здесь очень помогут. (Имейте в виду, что вам не нужно тестировать входные данные, которые не разрешены вашим определением данных)
• добавить шаблон, связанный с вашим определением данных (также появляется в книге)
• заполните пустые места в шаблоне, чтобы завершить определение
• отладки.

Answer 3

Когда вы задали вопрос (null? (cdr mylist)), ты должен был вернуться (car mylist) если это правда, а не '(), Поскольку в этот момент это означает, что mylist это список с одним атомом.

(define (last mylist)
  (cond ((null? mylist) '())
        ((null? (cdr mylist)) (car mylist))
        (else (last (cdr mylist)))))

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

Эта книга "Маленький интриган" приложила все усилия, чтобы помочь мне представить, что происходит в программе Scheme.

Answer 4

Если (null? mylist) не держит, что это? Непустой список.

Непустые списки могут иметь один или несколько элементов.

Сколько элементов имеют такие списки, что их последний элемент является их первым?

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

(define (last mylist)
      (if (list? mylist)
              (if (null? mylist)
                  '()
                  ;; {1}
                  (last (cdr mylist))
                  ;;
                  )))

в {1} ты звонишь (last (cdr mylist)) безусловно. Но что, если вы достигли конца списка? Что если останется только один элемент? В таком случае вам нужно будет вернуть его как результат. Итак, замените безусловный код на if выражение для достижения этой цели.

Answer 5

Я думаю, что это ближе всего к вашему исходному коду:

(define (last mylist)
  (if (list? mylist)
      (if (null? mylist)
          '() ; input list is empty
          (if (null? (cdr mylist))
              (car mylist) ; list only has one remaining element so this is it
              (last (cdr mylist)))) ; otherwise, recurse
      #f)) ; input is not a list

Когда используешь if, обязательно всегда заполняйте как истинную, так и ложную ветви.