Инструменты пользователя

Инструменты сайта


examination:flp:question6

6. Различная интерпретация списка в языке РС – Лисп.

Список представляет собой рекурсивную структуру данных, которая является либо пустым списком, либо cons-ячейку, cdr-частью которой является список. Поэтому список может интерпретироваться как цепочка cons-ячеек, связанных через их cdr-компоненты, и заканчивается символом NIL, соответствующему пустому списку. Компоненты car этих cons-ячеек называются элементами списка. Каждому элементу списка соответствует некоторая cons-ячейка. Пустой список не содержит ни одного элемента.

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

(a b c) ; Список из трех символов

(2.0s0 (a 1) \#\*) ; Список из трех объектов: короткого числа с плавающей запятой, другого списка и буквы

Поэтому пустой список NIL может быть представлен как '(), поскольку представляет собой список без элементов.

Точечный список представляет собой вариант списка, в котором последняя cons-ячейка в cdr-части содержит не NIL, а некоторый другой объект, отличный от cons-ячейки. Название этого списка связано со специальной нотацией, принятой для его записи: элементы списка, как обычно, заключены в скобки, но последний элемент отделяется от предпоследнего не пробелом или иным разделителем, а точкой. В предельном случае так же может быть записана и ``отдельно стоящая cons-ячейка, в которой car- и cdr-части заключены в скобки и разделены точкой, окруженной пробелами. Например: (a . 4 ) ; cons-ячейка, car-часть которой является символом, а cdr-часть - целое число (a b c . d) ; Точечный список с тремя элементами, последняя cons-ячека содержит в cdr-части d Допускается использовать запись вида (a b . (c d)), которая обозначает то же самое, что и (a b c d). В стандартных программах вывода Лиспа первый формат вывода не используется, но это не мешает вам баловаться ``нестандартным представлением.

В литературе (к сожалению, преимущественно иностранной, поскольку на русском языке о Лиспе пишут мало) довольно часто термин list используется как по отношению к обычным, так и к точечным спискам. В тех случаях, когда различие между этими типами списков имеет значение, мы будем использовать название ``обычные списки'' по отношению к спискам, заканчивающимся символом NIL. Большинство функций, работающих со списками, ориентированы именно на такие, обычные списки. Поэтому использовать в этих функциях вместо обычных точечные списки как правило не допускается.

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

Списки, точечные списки и деревья не являются взаимоисключающими типами данных. Это просто несколько способов взглянуть на одну и ту же структуру данных. В качестве примера еще одного альтернативного подхода можно упомянуть ассоциативные списки. Еще раз подчеркну, что ни один из этих терминов не обозначает реальный тип данных в Лиспе. К базовому типу данных относятся только cons-ячейки, а также nil, который является единственным объектом, принадлежащему типу null. Тип данных Лиспа list обозначает только объединение объектов типов cons и null, и лишь с этой точки зрения к нему могут быть отнесены как обычные, так и точечные списки.

examination/flp/question6.txt · Последние изменения: 2014/01/15 12:17 (внешнее изменение)