Динамические структуры данных. Алексеев А.Ю - 19 стр.

< L_list( El ) > ::= < Null_list > | < Non_null_list( El ) >
< Null_lis t> ::= Nil
< Non_null_list( El ) > ::= < Pair( El ) >
< Pair( El ) > ::= ( < Head_l( El ) > . < Tail_l( El ) > )
< Head_l( El ) > ::= < El >
< Tail_l( El ) > ::= < L_list( El ) >
     Здесь L_list( El ) – линейный список из элементов типа El, Null_list – пус-
той список, Non_null_list( El ) – непустой линейный список, Head_l( El ) – "го-
лова" списка, Tail_l( El ) – "хвост" списка, Pair( El ) – упорядоченная пара "го-
лова"–"хвост", т.е. элемент соответствующего декартова произведения. Тер-
минальным символом Nil обозначен пустой список, а терминальные символы
( . ) использованы для обозначения элемента декартова произведения. Выбор
других терминальных символов в определении линейного списка породил бы
другое сходное представление списка, сохранив при этом существенные ха-
рактеристики его структуры.
     Скобочное представление списка из элементов a, b, c, d типа El согласно
приведенному определению есть конструкция вида ( a . ( b . ( c . ( d . Nil ) ) ) )
или в сокращенной записи ( a b c d ). Пустой список представляется символом
Nil или парой скобок ( ), а список из одного элемента ( d . Nil ) в сокращенной
записи имеет вид ( d ). Переход к сокращенной записи производится с помо-
щью отбрасывания конструкции «. Nil» и удаления необходимое число раз
пары скобок вместе с предшествующей открывающей скобке точкой. Пробе-
лы в сокращенной записи используются для обеспечения однозначности про-
чтения конструкции, количество их выбирается произвольно. Если вместо
пробелов в качестве разделителя использовать, например запятую, то сокра-
щенная скобочная запись списка из элементов a, b, c, d будет иметь вид
( a , b , c , d ).
     Зададим не зависящую от формы представления списка функциональную
спецификацию линейного списка, определив c помощью системы правил (ак-
сиом) А1-А5, справедливых для всех x типа El, всех y типа L_list( El ), всех z
типа Non_null_list( El ), четыре базовые функции: предикат (индикатор) Null
(список пуст), селекторы Head ("голова" списка) и Tail ("хвост" списка), кон-
структор Cons :
        0) Nil :     → Null_list;
        1) Null : L_list( El ) → Boolean;
        2) Head : Non_null_list( El ) → El;
        3) Tail : Non_null_list( El ) → L_list( El );
        4) Cons : El ⊗ L_list( El ) → Non_null_list( El );
        A1) Null( Nil ) = true;
        A2) Null( Cons( x , y ) ) = false;
        A3) Head( Cons( x , y ) ) = x;
        A4) Tail( Cons( x , y ) ) = y;
        A5) Cons( Head( z ) , Tail( z ) ) = z.


                                       19