Функциональное программирование: что такое “неподходящий список”?

Я думаю, это проще объяснить с помощью Scheme.

Список - это цепочка пар, которые заканчиваются пустым списком. Другими словами, список заканчивается парой, cdr которой равен ()

(a . (b . (c . (d . (e . ()))))) 

;; same as

(a b c d e)

Цепочка пар, которая не заканчивается в пустом списке, называется неправильным списком. Обратите внимание, что неправильный список - это не список. Список и обозначения, разделенные точками, могут быть объединены для представления неправильных списков, как показывают следующие эквивалентные обозначения:

 (a b c . d)
 (a . (b . (c . d)))

Пример обычной ошибки, которая приводит к созданию неправильного списка:

scheme> (cons 1 (cons 2 3))
(1 2 . 3)

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

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

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

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

Scheme>(list 1 2 3 4)
(1 2 3 4)

Предоставлено: Введение в схему

Чтобы понять, что такое неправильный список, вы должны сначала понять определение правильного списка.

В частности, "аккуратное открытие" списков состоит в том, что вы можете представить список, используя только формы с фиксированным числом элементов, а именно:

;; a list is either 
;; - empty, or
;; - (cons v l), where v is a value and l is a list.

Это "определение данных" (используя термины "Как разрабатывать программы") имеет все виды хорошие свойства. Один из самых приятных моментов состоит в том, что если мы определяем поведение или значение функции в каждой «ветви» определения данных, мы гарантированно не пропустим ни одного случая. Что еще более важно, подобные структуры обычно приводят к хорошим чистым рекурсивным решениям.

Классический пример «длины»:

(define (length l)
  (cond [(empty? l) 0]
        [else (+ 1 (length (rest l))]))

Конечно, в Haskell все красивее:

length []    = 0
length (f:r) = 1 + length r

Итак, какое это имеет отношение к неправильным спискам?

Что ж, неправильный список использует это определение данных вместо этого :

;; an improper list is either
;; - a value, or
;; - (cons v l), where v is a value and l is an improper list

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

(define (length l)
  (cond [(cons? l) (+ 1 (length (rest l)))]
        [else 1]))

Проблема в том, что я уничтожил хорошее свойство: если я беру два значения и помещаю их в неправильный список с помощью (cons ab), результат будет иметь длину два . Чтобы понять почему, Предположим, я рассматриваю значения (cons 3 4) и (cons 4 5). Результатом будет (cons (cons (cons 3 4) (cons 4 5)), который можно интерпретировать или как неправильный список, содержащий (cons 3 4) и (cons 4 5), или как неправильный список, содержащий (cons 3 4), 4 и 5.

В языке с более строгой системой типов (например, Haskell) понятие «неправильный список» не так много смысл; вы могли бы интерпретировать его как тип данных, в базовом случае которого есть две вещи, что, вероятно, тоже не то, что вам нужно.

В языке с более строгой системой типов (например, Haskell) понятие «неправильный список» не имеет такого большого смысла; вы могли бы интерпретировать его как тип данных, в базовом случае которого есть две вещи, что, вероятно, тоже не то, что вам нужно.

В языке с более строгой системой типов (например, Haskell) понятие «неправильный список» не имеет такого большого смысла; вы могли бы интерпретировать его как тип данных, в базовом случае которого есть две вещи, что, вероятно, тоже не то, что вам нужно.

Определение списка в Erlang дается в руководстве - в частности, в разделе 2.10

В Erlang единственное, что вам действительно нужно знать о неправильных списках, - это как чтобы избежать их, и способ сделать это очень просто - все сводится к первой «вещи», на которой вы собираетесь построить свой список. Следующие элементы создают правильные списки:

A = [].
B = [term()].
C = [term(), term(), term()].

Во всех этих случаях синтаксис гарантирует, что существует скрытый «пустой» хвост, который соответствует типу «[]» в конце ... .

Итак, из них все следующие операции производят правильный список:

X = [term() | A].
Y = [term() | B].
Z = [term() | C]. 

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

Что делает полезным, так это то, что вы можете кормить каждую из X , Y или Z в такую ​​функцию, как:

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

Например, предположим, вы вызываете следующую сумму в Erlang в неправильном списке:

sum([H|T]) -> H + sum(T);
sum([]) -> 0.

Тогда будет сгенерировано исключение, поскольку последний хвост - это не пустой список, а атом.

In Common Lisp improper lists are defined as:

• dotted lists that have a non-NIL terminating 'atom'.

Example

  (a b c d . f)

or

• circular lists

Example

  #1=(1 2 3 . #1#)

Список состоит из ячеек, каждая из которых состоит из двух указателей. Первый указывает на элемент данных, второй - на следующую ячейку или nil в конце списка.

Если второй не указывает на ячейку (или nil), список неправильный. Функциональные языки, скорее всего, позволят вам создавать ячейки, поэтому вы должны иметь возможность генерировать неправильные списки.

В Erlang (и, вероятно, также и на других языках FP) вы можете сэкономить немного памяти, сохранив свои 2-кортежи как неправильные списки :

2> erts_debug:flat_size({1,2}).
3
3> erts_debug:flat_size([1|2]).
2

В Erlang правильный список - это тот, где [H | Т] .

H - это голова списка, а T - остальная часть списка в виде другого списка.

Неправильный список не соответствует этому определению.

Я думаю, возможно, это относится к «паре с точками» в LISP, например, к списку, конечная cons-ячейка которого имеет атом, а не ссылку на другую cons-ячейку или NIL в cdr.

EDIT

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

http://en.wikipedia.org/wiki/Lisp_ (programming_language)

, найдите «неправильный» и проверьте сноски.