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

м
Пришло время уделить некоторое внимание рассмотрению программной реализации [[w:Линейный список|списков]] и списочных структур. Это необходимо для более тонкого понимания того, что происходит во время работы [[w:Функциональное программирование|функциональной программы]], как на каком-либо реализованном функциональном языке, так и на абстрактном языке.
 
Каждый объект занимает в [[w:Компьютерная память|памяти]] машины какое-то место. Однако атомы представляют собой указатели (адреса) на ячейки, в которых содержатся объекты. В этом случае пара <math>z = x:y</math> графически может быть представлена так, как показано на следующем рисунке 1.
 
[[Изображение:Fp_figure_01.gif|thumb|Рисунок 1. Представление пары в памяти компьютера]]
 
Адрес ячейки, которая содержит указатели на <math>x</math> и <math>y</math>, и есть объект <math>z</math>. Как видно на рисунке, пара представлена двумя адресами — указатель на голову и указатель на хвост. Традиционно первый указатель (на рисунке выделен голубым цветом) называется a-поле, а второй указатель (на рисунке — зеленоватый) называется d-поле.
Для удобства представления объекты, на которые указывают a- и d-поля, в дальнейшем будут записываться непосредственно в сами поля. Пустой список будет обозначаться перечёркнутым квадратом (указатель ни на что не указывает).
 
Таким образом, списочная структура, которая рассмотрена несколькими параграфами ранее (<math>[a_{1}, [a_{2}, a_{3}, [a_{4}]], a_{5}]</math>) может быть представлена так, как показано на следующем рисунке: 2.
 
[[Изображение:Fp_figure_02.gif|thumb|Рисунок 2. Графическое представление списочной структуры <math>[a_{1}a1, [a_{2}a2, a_{3}a3, [a_{4}a4] ], a_{5}a5]]]</math>
 
На этом рисунке также хорошо проиллюстрировано понятие уровня вложенности — атомы <math>a_{1}</math> и <math>a_{5}</math> имеют уровень вложенности 1, атомы <math>a_{2}</math> и <math>a_{3}</math> — 2, а атом <math>a_{4}</math> — 3 соответственно.
271

правка