Основы функционального программирования/Структуры данных и базисные операции

ВведениеПравить

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

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

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

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

  1. Операция создания пары —  . Эта операция также называется конструктором или составителем.
  2. Операция отсечения головы —  . Это первая селективная операция.
  3. Операция отсечения хвоста —  . Это вторая селективная операция.

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

  1.  
  2.  
  3.  

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

 

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

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

  1. Пустой список  
  2.  

Главное свойство списка:  .

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

 

  (при  ).

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

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

  1.  .
  2.  .

Т. е. видно, что списочная структура — либо атом, либо список состоящий из списочных структур. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение:  . Для списочных структур вводится такое понятие, как уровень вложенности.

Несколько слов о программной реализацииПравить

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

Каждый объект занимает в памяти машины какое-то место. Однако атомы представляют собой указатели (адреса) на ячейки, в которых содержатся объекты. В этом случае пара   графически может быть представлена так, как показано на рисунке 1.

 
Рисунок 1. Представление пары в памяти компьютера

Адрес ячейки, которая содержит указатели на   и  , и есть объект  . Как видно на рисунке, пара представлена двумя адресами — указатель на голову и указатель на хвост. Традиционно первый указатель (на рисунке выделен голубым цветом) называется a-поле, а второй указатель (на рисунке — зеленоватый) называется d-поле.

Для удобства представления объекты, на которые указывают a- и d-поля, в дальнейшем будут записываться непосредственно в сами поля. Пустой список будет обозначаться перечёркнутым квадратом (указатель ни на что не указывает).

Таким образом, списочная структура, которая рассмотрена несколькими параграфами ранее ( ) может быть представлена так, как показано на рисунке 2.

 
Рисунок 2. Графическое представление списочной структуры  

На этом рисунке также хорошо проиллюстрировано понятие уровня вложенности — атомы   и   имеют уровень вложенности 1, атомы   и   — 2, а атом   — 3 соответственно.

Остаётся отметить, что операция   требует расхода памяти, ибо при конструировании пары выделяется память под указатели. С другой стороны обе операции   и   не требуют памяти, они просто возвращают адрес, который содержится соответственно в a- или d-поле.

ПримерыПравить

Пример 5. Операция  .

Для начала необходимо рассмотреть более подробно работу операции  . Пояснение работы будет проведено на трёх более или менее общих примерах:

  1.   (при этом результат не является элементом  ).
  2.  
  3.  

Пример 6. Функция определения длины списка  .

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

Осмысленно, что операция   возвращает первый элемент списка, а операция   возвращает список из оставшихся элементов. Пусть известна длина списка, полученного при помощи операции  , тогда длина исходного списка будет равна известной длине, увеличенной на единицу. В этом случае можно легко записать определение самой функции  :

 

 

Пример 7. Функция слияния двух списков  .

Реализовать функцию слияния (или сцепления) списков можно многими способами. Первое, что приходит в голову — деструктивное присваивание. Т. е. заменить указатель на   в конце первого списка на указатель на голову второго списка и тем самым получить результат в первом списке. Однако здесь изменяется сам первый список. Такие приёмы запрещены в функциональном программировании (хотя, в очередной раз необходимо заметить, что в некоторых функциональных языках всё-таки есть такая возможность).

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

 

 

Последний пример показывает, как при помощи постепенного конструирования можно построить новый список, который равен сцепке двух заданных.

УпражненияПравить

  1. Построить функции, вычисляющие  -ый элемент следующих рядов:
    1.  
    2.  
    3.  
    4.  
    5.  
  2. Объяснить результаты операции  , показанные в примере 5. Для объяснения можно воспользоваться графическим методом.
  3. Объяснить результат работы функции   (пример 7). Пояснить, почему функция не является деструктивной.
  4. Построить функции, работающие со списками:
    1.   — функция вычленения  -ого элемента из заданного списка.
    2.   — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
    3.   — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
    4.   — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
    5.   — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.

Ответы для самопроверкиПравить

Большинство ответов для самопроверки представляют собой лишь одни из возможных вариантов (в большинстве случаев наиболее интуитивные).

  1. Функции, вычисляющие  -ый элемент рядов:
    1.  :
      •  
      •  
    2.  :
      •  
      •  
    3.  :
      •  
      •  
    4.  :
      •  
      •  
    5.  :
      •  
      •  
      •  
      •  
  2. Объяснение работы операции   можно легко провести в три приёма (равно так же, как и приведено в примере). Для того чтобы не загромождать объяснения, здесь наряду с функциональной записью операции   также используется инфиксная запись посредством символа двоеточия.
    1. Первый пример работы операции — определение самой операции. Рассматривать его нет смысла, ибо операция   определяется именно таким образом.
    2.   (Эти преобразование проведены по определению списка).
    3.  .
  3. В качестве примера работы функции   рассмотрим сцепку двух списков, каждый из которых состоит из двух элементов:   и  . Опять же для того, чтобы не загромождать объяснение, для записи операции   используется инфиксная форма. Для более полного понимания приведённого объяснения необходимо помнить определение списка.
      •  
       .
  4. Функции, работающие со списками:
    1.  :
      •  
      •  
      •  
    2.  :
      •  
      •  
      •  
    3.  :
      •  
      •  
      •  
    4.  :
      •  
      •  
    5.  :
      •  
      •