Функциональное программирование

         

Списки и функциональные выражения


Основной единицей данных для LISP-системы является список.

Списки задаются следующим индуктивным определением.

  1. Пустой список () (обозначаемый также nil) является списком.
  2. Если l1,. . . , ln, n ≥ 1 - атомы либо списки, то (l1, . . . , ln) - также список.

Элементами списка (l1, . . . , ln) называются l1, . . . , ln. Равенство списков задается следующим индуктивным определением.

  1. l = nil тогда и только тогда, когда l также есть nil.
  2. (l1, . . . , ln) = (k1, . . . , km) тогда и только тогда, когда n = m и соответствующие li = ki.

Пример 8.2.2. Все списки (), (()), ((())) и т. д. различны. Различны также и списки nil, (nil, nil), (nil, nil, nil) и так далее. Попарно различны и списки ((a,b), c), (a, (b,c)), (a,b,c), где a, b, c - различные атомы.

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

Вершины списка l задаются следующим индуктивным определением.

  1. Элементы списка являются его вершинами.
  2. Вершины элементов списка являются его вершинами.

Длиной списка называется количество элементов в нем. Глубиной списка называется максимальное количество вложенных пар скобок в нем. Соединением списков (l1, . . . , ln) и (k1, . . . , km) называется список

(l1, . . . , ln, k1, . . . , km).

Замена вершины a списка l на атом либо список m получается заменой поддерева l, соответствующего a, на дерево для m. Замена обозначается l[a | m]. Через l[a || m] будем обозначать результат замены нескольких вхождений вершины a на m.

Атомами в языке lisp являются числа, имена, истина T. Ложью служит пустой список nil, который в принципе атомом не является, но в языке lisp при проверке на то, является ли он атомом, выдается истина. Точно так же выдается истина и при проверке, является ли он списком. Однако все списковые операции применимы к nil, а те, которые работают с атомами, часто к нему неприменимы.

Содержание  Назад  Вперед




Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий