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

   Пустой список рассматривается здесь как значение типа L_list( El ), воз-
вращаемое функцией без параметров Nil. Доступ к элементам списка осуще-
ствляется с помощью соответствующей суперпозиции вызовов функций Head
и Tail. Так, например, если y = (a b c d), то Head( Tail( y ) ) = b, а
Head( Tail( Tail( Tail( y ) ) ) ) = d.
   Способ использования функции Cons для конструирования списков пояс-
няется приведенными далее примерами:

     ( a ) = ( a . Nil ) = Cons( a , Nil );
     ( a b c ) = ( a. ( b. ( c . Nil ) ) ) = Cons( a , Cons ( b , Cons ( c , Nil ) ) ).

   Отметим, что построение каждой "точечной" пары (значения типа
Pair( El ) ) в скобочной записи списка требует однократного применения кон-
структора Cons.
   Отвлекаясь от конкретного (скобочного) представления и опираясь на
функциональную спецификацию линейного списка, можно дать новое опре-
деление типа Pair( El )

     < Pair ( El ) > ::= Cons( < Head_l ( El ) > , < Tail_l ( El ) > )

в котором с помощью терминальных символов «Cons ( , )» явно указывается
на возможность построения пары "голова"–"хвост" (списка типа
Non_null_list ) только с помощью вызова конструктора Cons. Такое "операци-
онное" представление списка вполне соответствует ранее рассмотренному.
Так список из элементов a, b ,c типа El представляется теперь как
Cons(a,Cons(b,Cons(c,Nil))). Нетрудно проверить, что правило А5 становится
при этом излишним и может быть выведено из аксиом А3, А4.
   Рассмотрим примеры рекурсивных определений некоторых функций обра-
ботки линейных списков с применением определенных выше базовых функ-
ций. В формулировках примеров и комментариях к ним использована сокра-
щенная скобочная запись списков. Паскалеподобная нотация, примененная в
определениях функций, ясна без дополнительных пояснений.
   Пример 1.1. Функция Sum, вычисляющая сумму элементов списка.
                 Sum( y ) = if Null( y ) then 0
            else Head( y ) + Sum( Tail( y ) ).
   Пример 1.2. Функция Concat, соединяющая два списка в один.
   Например, Concat( y , z ) = (a b c d) для y = (a b), z = (c d).
   Concat( y , z ) = if Null( y ) then z
                   else Cons( Head( y ), Concat( Tail( y ), z)).
   Отметим, что конструктор Cons вызывается при выполнении функции
Concat столько раз, сколько элементов в списке y.
   Пример 1.3. Функция Append, добавляющая элемент в конец списка.
   Например, Append( y, x ) = ( a b c ) для y = ( a b ), x = c
   Append( y, x ) = Concat( y, Cons( x, Nil ) ).

                                            20