Структуры данных и базисные операции

Программирование в функциональных обозначениях

Лекция №19

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

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

Пусть заданы объекты некоторого первичного типа A. Сейчас совершенно не важно, что именно представляют собой эти выделенные объекты. Обычно считается, что на этих объектах определён набор базисных операций и предикатов. По традиции, которая пошла ещё от МакКарти (автор Lisp’а), такие объекты называются атомами. В теории фактический способ реализации базисных операций и предикатов совершенно не важен, их существование просто постулируется. Однако каждый конкретный функциональный язык реализует базисный набор по-своему.

В качестве базисных операций традиционно (и в первую очередь это объясняется теоретической необходимостью) выделяются следующие три:

1. Операция создания пары — prefix (x, y) º x: y º [x | y]. Эта операция также называется конструктором или составителем.

2. Операция отсечения головы — head (x) º h (x). Это первая селективная операция.

3. Операция отсечения хвоста — tail (x) º t (x). Это вторая селективная операция.

Селективные операции отсечения головы и хвоста также называют просто селекторами. Выделенные операции связаны друг с другом следующими тремя аксиомами:

1. head (x: y) = x

2. tail (x: y) = y

3. prefix (head (x: y), tail (x: y)) = (x: y)

Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество S-выражений (обозначение — Sexpr (A)). Например:

a₁: (a₂: a₃) Î Sexpr

Для дальнейших исследований вводится фиксированный атом, который также принадлежит первичному типу A. Этот атом в дальнейшем будет называться «пустым списком» и обозначаться символами [] (хотя в разных языках функционального программирования могут существовать свои обозначения для пустого списка). Теперь можно определить то, чем собственно занимается функциональное программирование — собственное подмножество List (A) Ì Sexpr (A), которое называется «список над A».

Определение:

1°. Пустой список [] Î List (A)

2°. x Î A & y Î List (A) ® x: y Î List (A)

Главное свойство списка: x Î List (A) & x ¹ [] ® head (x) Î A; tail (x) Î List (A).

Для обозначения списка из n элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: [a₁, a₂,..., a_n]. Применяя к такому списку определенным образом операции head и tail можно добраться до любого элемента списка, т.к.:

head ([a₁, a₂,..., a_n]) = a₁

tail ([a₁, a₂,..., a_n]) = [a₂,..., a_n] (при n > 0).

Кроме списков вводится еще один тип данных, который носит название «списочная структура над A» (обозначение — List_str (A)), при этом можно построить следющую структуру отношений: List (A) Ì List_str (A) Ì Sexpr (A). Определение списочной структуры выглядит следующим образом:

Определение:

1°. a Î A ® a Î List_str (A)

2°. List (List_str (A)) Ì List_str (A)

Т.е. видно, что списочная структура — это список, элементами которого могут быть как атомы, так и другие списочные структуры, в том числе и обыкновенные списки. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: [a₁, [a₂, a₃, [a₄]], a₅]. Для списочных структур вводится такое понятие, как уровень вложенности.

Дата добавления: 2014-01-07