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

   Пример 1.4. Функция Reverse, обращающая список.
    Например, Reverse( y ) = ( d c b a ) для y = ( a b c d ).
   Reverse( y ) = if Null( y ) then Nil
                else Concat ( Reverse( Tail( y) ), Cons( Head( y ), Nil ) ).
   Для лучшего понимания работы функции Reverse рассмотрим последова-
тельность вызовов функций и возвращаемых ими значений при обращении
списка из двух элементов y = ( a b ) (рис.1.18).

Вызовы                                           Возвращаемые значения
Reverse( (a b) )                          (ba)
Concat( Reverse(( b )),Cons( a, Nil ))    (ba)
* Reverse( (b) )                          (b)
Concat(Reverse( Nil ),Cons( b, Nil ))     (b)
* Reverse( Nil )                          Nil
* Cons( b,Nil )                           (b)
* Cons( a,Nil )                           (a)
Cons( b, Concat( Nil, (a) ) )             (ba)
* Concat( Nil, (a) )                      (a)

Рис. 1.18. Последовательность вызовов функций при обращении списка из двух элементов

   Вызов функции, с которого начинается вычисление значения фактического
параметра ранее вызванной функции, на рисунке помечен символом *. Воз-
вращаемые значения, формируемые в процессе вычислений позднее по вре-
мени, сдвинуты вправо относительно ранее сформированных значений. На
рисунке для краткости не отражены вызовы селекторов Head и Tail. Вместо
этого на соответствующие места подставлены возвращаемые ими значения.
   Заметим, что количество вызовов конструктора Cons при обращении спи-
ска из n элементов равно n + ( n − 1 ) + .. + 1 = n ( n + 1 ) / 2 и может быть дос-
таточно велико при большом n. Это важно, поскольку, как станет ясно из
дальнейшего изложения, именно количество вызовов конструктора Cons в
значительной степени определяет объем потребляемых вычислительных ре-
сурсов. В следующем примере рассмотрено другое определение функции об-
ращения списка, позволяющее сократить объем вычислений.
   Пример 1.5. Функция Reverse1, обращающая список. С целью уменьшения
количества вызовов конструктора Cons введена вспомогательная функция Rev,
второй параметр которой используется как "накапливающий".
   Rev( y, z ) = if Null( y ) then z
               else Rev ( Tail( y ), Cons ( Head( y ), z ) );
   Reverse1 ( y ) = Rev ( y, Nil ).
   Последовательность вызовов функций и возвращаемых ими значений при
обращении списка из двух элементов y = ( a b ), порождаемая вызовом функ-
ции Reverse1, приведена на рис. 1.19.



                                         21