Разница между CDR, CAR и REST, FIRST и возможной реализацией?

Я немного узнал о функциональном программировании в LISP, и вот что я натолкнулся: LISP использует функции CAR, CDR, а также функции FIRST и REST. Оба связаны со списками.

Из того, что я узнал до сих пор, есть разница между этими двумя, но я не совсем понимаю, в чем разница.

Кто-нибудь может подвести итог для меня? И как мне в конечном итоге реализовать FIRST / REST с использованием CDR, CAR?

Изменить: Поскольку в принятом ответе упоминается документация, но нет ссылки, здесь приведена ссылка на документацию для CAR / CDR, а здесь - для FIRST / REST.

Кроме того - важное примечание - эта связанная документация является "просто замечаниями по реализации" для CLISP, который является широко используемой средой. Как правило, почти невозможно найти "официальную документацию" для таких языков, как этот.

Источник

4 ответа

Решение

С точки зрения того, что они делают, car и cdr эквивалентны первым и остальным. Это совершенно ясно в документации. HyperSpec говорит в записи для первого, второго и т. Д.:

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

(first list)    ==   (car list)
(second list)   ==   (car (cdr list))
(third list)    ==   (car (cddr list))

...

Заметки:

first функционально эквивалентен car, второй функционально эквивалентен cadr, третий функционально эквивалентен caddr, а четвертый функционально эквивалентен cadddr.

Теперь, когда вы используете эти функции, есть разница не в функциональности, а в стиле. Это также вызывается в HyperSpec, например, в записи об отдыхе:

Заметки:

Отдых часто предпочтительнее стилистически, чем cdr, когда аргумент состоит в том, чтобы субъективно рассматривать его как список, а не как минусы.

Например, рассмотрим два способа отображения структур, построенных из cons-ячеек. В первом мы отображаемдерево cons-ячеек, вызывая некоторую функцию с каждым листом (т.е. не-cons) дерева. Мы проверяем, является ли что-то минусом с consp, и если это так, мы возвращаемся на его машину и cdr. Мы объединяем результаты в новую ячейку cons, вызывая cons.

(defun map-over-cons (function tree)
  (if (not (consp tree))
      (funcall function tree)
      (cons (map-over-cons function (car tree))
            (map-over-cons function (cdr tree)))))

В качестве альтернативы, когда мы отображаем список, мы обычно проверяем состояние терминала с помощью endp (или null, но endp подчеркивает, что мы ищем конец списка, а не просто ищем nil), и вызываем функцию на первый из списка и вернитесь в остальную часть списка. Несмотря на то, что довольно часто можно увидеть результат, созданный с использованием cons, на самом деле существует список *, который будет выполнять ту же задачу при вызове с двумя аргументами (в общем, он может сделать немного больше), который подчеркивает, что список создается:

(defun map-over-list (function list)
  (if (endp list)
      '()
      (list* (funcall function (first list))
             (map-over-list function (rest list)))))

Любая из этих функций может быть написана с использованием car, cdr и cons, либо с first, rest и list *, либо с любой их комбинацией, но придерживание одной или другой помогает людям, которые могут прочитать код позже (включая оригинал автор) и сигнализирует о намерениях автора.

И как мне в конечном итоге реализовать FIRST/REST с использованием CDR, CAR?

Как насчет:

(defun first (x) (car x))
(defun rest (x) (cdr x))

или, возможно, даже лучше, если у вас есть функция символа:

(setf (symbol-function 'first) (symbol-function 'car))
(setf (symbol-function 'rest) (symbol-function 'cdr))
Источник

Операции first а также rest сигнализирует о том, что вы работаете со списком: серия пар, заканчивающаяся пустым списком, т.е. он имеет форму (список x1 ... xn)

Операции car а также cdr сигнализирует о том, что вы работаете над структурой данных с парами, которая потенциально не является списком.

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

Источник

Классически, car и cdr были больше ориентированы на машины, а first и rest были более абстрактными функциями. На самом деле, нет никакой разницы между ними. Все привязались к машине и CDR, поэтому машина и CDR преобладали.

Если вам трудно найти какие-либо различия между автомобилем и первым, это потому, что их нет. Посмотрите сначала как псевдоним для автомобиля.

Определения?

(defun first (x) (car x))
(defun rest (x) (cdr x))
Источник

Во-первых, ни один из них не является предикатом (или, по крайней мере, они не являются тем, что программисты на Лиспе называют "предикатами"; в этом контексте "предикат" означает "функцию, которая возвращает логическое значение").

Что касается вопроса, давайте на минутку запрыгнем в REPL.

; SLIME 2014-12-23
CL-USER> (describe #'car)
#<FUNCTION CAR>
  [compiled function]

Lambda-list: (LIST)
Declared type: (FUNCTION (LIST) (VALUES T &OPTIONAL))
Documentation:
  Return the 1st object in a list.
Known attributes: foldable, flushable, unsafely-flushable
Source file: SYS:SRC;CODE;LIST.LISP
; No value
CL-USER> (describe #'first)
#<FUNCTION FIRST>
  [compiled function]

Lambda-list: (LIST)
Declared type: (FUNCTION (LIST) (VALUES T &OPTIONAL))
Documentation:
  Return the 1st object in a list or NIL if the list is empty.
Known attributes: foldable, flushable, unsafely-flushable
Source file: SYS:SRC;CODE;LIST.LISP
; No value
CL-USER> (describe #'cdr)
#<FUNCTION CDR>
  [compiled function]

Lambda-list: (LIST)
Declared type: (FUNCTION (LIST) (VALUES T &OPTIONAL))
Documentation:
  Return all but the first object in a list.
Known attributes: foldable, flushable, unsafely-flushable
Source file: SYS:SRC;CODE;LIST.LISP
; No value
CL-USER> (describe #'rest)
#<FUNCTION REST>
  [compiled function]

Lambda-list: (LIST)
Declared type: (FUNCTION (LIST) (VALUES T &OPTIONAL))
Documentation:
  Means the same as the cdr of a list.
Known attributes: foldable, flushable, unsafely-flushable
Source file: SYS:SRC;CODE;LIST.LISP
; No value

Итак, согласно документации и их подписи, car эквивалентно first а также cdr эквивалентно rest, Давайте проверим это.

CL-USER> (cons 1 2)
(1 . 2)
CL-USER> (car (cons 1 2))
1
CL-USER> (first (cons 1 2))
1
CL-USER> (cdr (cons 1 2))
2
CL-USER> (rest (cons 1 2))
2
CL-USER> (cons 1 nil)
(1)
CL-USER> (car (cons 1 nil))
1
CL-USER> (first (cons 1 nil))
1
CL-USER> (cdr (cons 1 nil))
NIL
CL-USER> (rest (cons 1 nil))
NIL
CL-USER> nil
NIL
CL-USER> (car nil)
NIL
CL-USER> (first nil)
NIL
CL-USER> (cdr nil)
NIL
CL-USER> (rest nil)
NIL

Итак, они кажутся одинаковыми.

Источник
Другие вопросы по тегам