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

Полная запись                                           Сокращенная запись
a                                                       a
Nil                                                     ( )
( a . ( b . ( c . Nil ) ) )                             (abc)
( a . ( ( b . ( c . Nil ) ) . ( d . ( e . Nil ) ) ) )   (a(bc)de)

                               Рис. 1.20. Примеры иерархических списков

   Зададим аналогично тому, как это было сделано в 1.6 для линейного спи-
ска, функциональную спецификацию иерархического списка, определив c по-
мощью системы правил (аксиом) А1–А7, справедливых для всех t типа El, всех
u типа L_lis t( S_expr ( El ) ), всех v типа Non_null_list ( S_expr ( El ) ), всех w
типа S_expr ( El ), константу Nil, обозначающую пустой список, четыре ранее
уже встречавшиеся базовые функции Null, Head, Tail, Cons, а также предикат
Atom, проверяющий S–выражение на атомарность:
   0) Nil : → Null_list;
   1) Null : L_list ( S_expr ( El ) ) → Boolean;
   2) Head : Non_null_list ( S_expr ( El ) ) → S_expr ( El );
   3) Tail : Non_null_list ( S_expr ( El ) ) → L_list ( S_expr ( El ) );
   4) Cons : S_expr( El ) ⊗ L_list( S_expr( El ) ) → Non_null_list( S_expr( El ) );
   5) Atom : S_expr( El ) → Boolean;

    A1) Null ( Nil ) = true;
    A2) Null ( Cons ( w, u ) ) = false;
    A3) Head ( Cons ( w, u ) ) = w;
    A4) Tail ( Cons ( w, u ) ) = u;
    A5) Cons ( Head( v ), Tail( v ) ) = v.
    A6) Atom ( t ) = true;
    A7) Atom ( u ) = false;
    Согласно правилу A7 Atom ( Nil ) = false, что отличается от распространен-
ного представления пустого списка как атома специального вида, но соответ-
ствует приведенному ранее определению иерархического списка. Доступ к
компонентам S–выражения, которыми могут быть как атомы, так и списки,
осуществляется с помощью селекторов Head и Tail. Так, например, если
u = ( a ( b c ) d e ), то
    Head ( Tail ( u ) ) = ( b c );
    Head ( Tail ( Head ( Tail ( u ) ) ) ) = c.
    Рассмотрим теперь примеры использования функции Cons для конструи-
рования списков:
 ( a (b c) d e ) = ( a . ( ( b . ( c . Nil ) ) . ( d . ( e .Nil ) ) ) )=
            Cons ( a, Cons ( Cons ( b, Cons ( c, Nil ) ) , Cons ( d, Cons ( e, Nil ) ) ) );
(a (( ) (b c) d) e) = (a.( (Nil . ( ( b . (c . Nil) ) . (d . Nil) ) ) . (e . Nil) ) ) =
      Cons(a, Cons(Cons(Nil,Cons(Cons(b,Cons(c,Nil)),Cons(d,Nil))),Cons(e,Nil))).

                                                        23