chapter11.tex

\chapter{Неявное рекурсивное замедление}
\label{ch:11}

В Разделе~\ref{sc:9.2.3} мы видели, что избыточное ленивое
представление двоичных чисел может поддерживать как функцию
увеличения, так и уменьшения за амортизированное время $O(1)$. В
Разделе~\ref{sc:10.1.2} мы видели, что гетерогенные типы и полиморфная
рекурсия позволяют строить чрезвычайно простые реализации числовых
представлений, например, двоичных списков с произвольным доступом. В
этой главе мы сочетаем и расширяем эти идеи, получая в результате
методику, называемую \term{неявное рекурсивное замедление}{implicit
  recursive slowdown}.

Каплан и Тарждан \cite{KaplanTarjan1995, KaplanTarjan1996b,
  KaplanTarjan1996a} исследовали родственную методику под названием
\term{рекурсивное замедление}{recursive slowdown}, основанную, в
отличие от нашей, не на ленивых двоичных числах, а на сегментированных
двоичных числах (Раздел~\ref{sc:9.2.4}). Сходства и различия
реализаций, основанных на рекурсивном замедлении и на неявном
рекурсивном замедлении, в сущности, аналогичны сходствам и различиям
между этими двумя системами счисления.

\section{Очереди и деки}
\label{sc:11.1}

Напомним устройство двоичных списков с произвольным доступом из
Раздела~\ref{sc:10.1.2}, имеющих тип
\begin{lstlisting}
  datatype $\alpha$ RList =
       Nil | Zero of ($\alpha$ $\times$ $\alpha$) RList | One of $\alpha$ $\times$ ($\alpha$ $\times$ $\alpha$) RList
\end{lstlisting}
Чтобы упростить дальнейшее обсуждение, давайте заменим этот тип на
\begin{lstlisting}
  datatype $\alpha$ Digit = Zero | One of $\alpha$
  datatype $\alpha$ RList = Shallow of $\alpha$ Digit | Deep of $\alpha$ Digit $\times$ ($\alpha$ $\times$ $\alpha$) RList
\end{lstlisting}
Мелкий (\lstinline!Shallow!) список содержит от нуля до одного
элемента. Глубокий (\lstinline!Deep!) список содержит ноль или один
элемент, а также список пар. С этим типом мы можем играть во многие из
игр, освоенных нами при рассмотрении двоичных списков с произвольным
доступом в Главе~\ref{ch:9}. Например, можно поддержать функцию
\lstinline!head! за время $O(1)$, переключившись на безнулевое
представление вроде
\begin{lstlisting}
  datatype $\alpha$ Digit = Zero | One of $\alpha$ | Two of $\alpha$ $\times$ $\alpha$
  datatype $\alpha$ RList = Shallow of $\alpha$ Digit | Deep of $\alpha$ Digit $\times$ ($\alpha$ $\times$ $\alpha$) RList
\end{lstlisting}
В этом представлении все цифры в глубоком (\lstinline!Deep!) узле
должны быть единицами или двойками. Конструктор ноль-\lstinline!Zero!
используется только в пустом списке \lstinline!Shallow Zero!.

Подобным образом, задержав список пар в каждом глубоком узле, мы можем
заставить либо \lstinline!cons!, либо \lstinline!tail! работать за
амортизированное время $O(1)$, а вторую из этих операций за
амортизированное время $O(\log n)$.
\begin{lstlisting}
  datatype $\alpha$ RList =
         Shallow of $\alpha$ Digit
       | Deep of $\alpha$ Digit $\times$ ($\alpha$ $\times$ $\alpha$) RList susp
\end{lstlisting}
Позволив выбирать из трёх ненулевых цифр в каждом глубоком узле, мы
можем заставить все три функции \lstinline!cons!, \lstinline!head! и
\lstinline!tail! работать за время $O(1)$.
\begin{lstlisting}
  datatype $\alpha$ Digit =
       Zero | One of $\alpha$ | Two of $\alpha$ $\times$ $\alpha$ | Three of $\alpha$ $\times$ $\alpha$ $\times$ $\alpha$
\end{lstlisting}
Как и прежде, конструктор \lstinline!Zero! используется только в
пустом списке.

Чтобы расширить эту схему для поддержки очередей и деков, достаточно
добавить вторую цифру в каждый глубокий узел.
\begin{lstlisting}
  datatype $\alpha$ Queue =
         Shallow of $\alpha$ Digit
       | Deep of $\alpha$ Digit $\times$ ($\alpha$ $\times$ $\alpha$) Queue susp $\times$ $\alpha$ Digit
\end{lstlisting}
Первая цифра представляет первые несколько элементов очереди, а
вторая~--- последние несколько элементов. Оставшиеся элементы хранятся
в задержанной очереди пар, которую мы называем \term{срединной
  очередью}{middle queue}.

Выбор типа цифры зависит от того, какие функции мы хотим поддерживать
на каждом конце очереди. В следующей таблице приведены разрешённые
значения для головной цифры очереди, поддерживающей каждое данное
сочетание функций.
$$
\begin{array}{c|c}
  \mbox{поддерживаемые функции} & \mbox{разрешённые цифры} \\
  \hline
  \lstinline!cons! & \lstinline!Zero!, \lstinline!One! \\
  \lstinline!cons/head! & \lstinline!One!, \lstinline!Two! \\
  \lstinline!head/tail! & \lstinline!One!, \lstinline!Two! \\
  \lstinline!cons/head/tail! & \lstinline!One!, \lstinline!Two!, \lstinline!Three! \\
\end{array}
$$
Те же правила выбора относятся и к хвостовой цифре.

В качестве конкретного примера давайте разработаем реализацию
очередей, поддерживающую \lstinline!snoc! на хвостовом конце и
\lstinline!head! и \lstinline!tail! на головном (т.~е., обыкновенных
очередей-FIFO). Обратившись к таблице, мы решаем, что головная цифра
глубокого узла может быть единица-\lstinline!One! или
двойка-\lstinline!Two!, а хвостовая цифра может быть
ноль-\lstinline!Zero! или единица-\lstinline!One!. Цифра в мелком узле
может быть \lstinline!Zero! или \lstinline!One!.

Чтобы добавить к глубокой очереди новый элемент \lstinline!y! через
\lstinline!snoc!, мы смотрим на хвостовую цифру. Если это ноль
(\lstinline!Zero!), мы заменяем хвостовую цифру на
единицу-\lstinline!One y!. Если это \lstinline!One x!, то мы заменяем её на \lstinline!Zero!
и добавляем пару \lstinline!(x, y)! к срединной очереди. Кроме того,
требуется выписать несколько особых случаев для добавления элементов к
мелкой очереди.
\begin{lstlisting}
  fun snoc (Shallow Zero, y) = Shallow (One y)
    | snoc (Shallow (One x), y) = Deep (Two (x, y), $\$$empty, Zero)
    | snoc (Deep (f, m, Zero), y) = Deep (f, m, One y)
    | snoc (Deep (f, m, One x), y) =
        Deep (f, $\$$snoc (force m, (x, y)), Zero)
\end{lstlisting}

Чтобы удалить элемент из глубокой очереди через
\lstinline!tail!, мы смотрим на головную цифру. Если это
\lstinline!Two (x, y)!, мы отбрасываем \lstinline!x! и устанавливаем
головную цифру в \lstinline!One y!. Если это \lstinline!One x!, мы
<<занимаем>> в срединной очереди пару \lstinline!(y, z)! и
устанавливаем головную цифру в \lstinline!Two (y, z)!. Опять же, нужно
учесть ещё несколько особых случаев для работы с мелкими очередями.
\begin{lstlisting}
  fun tail (Shallow (One x)) = empty
    | tail (Deep (Two (x, y), m, r)) = Deep (One y, m, r)
    | tail (Deep (One x, $\$$q, r)) =
        if isEmpty q then Shallow r
        else let val (y, z) = head q
             in Deep (Two (y, z), $\$$tail q, r) end
\end{lstlisting}
Заметим, что в последнем варианте \lstinline!tail! мы вынуждаем
срединную очередь. Полный код приведен на Рис.~\ref{fig:11.1}.

\begin{figure}
  \centering

  \caption{Очереди на основе неявного рекурсивного замедления.}
  \label{fig:11.1}
\end{figure}

Теперь мы хотим показать, что \lstinline!snoc! и \lstinline!tail!
работают за амортизированное время $O(1)$. Заметим, что
\lstinline!snoc! никак не обращается к головной цифре, а
\lstinline!tail!~--- к хвостовой цифре. Если мы рассматриваем каждую
из функций по отдельности, то \lstinline!snoc! оказывается аналогичен
функции \lstinline!inc! для ленивых двоичных чисел, а \lstinline!tail!
оказывается аналогичен функции \lstinline!dec! для безнулевых ленивых
двоичных чисел. Модифицируя доказательства для \lstinline!inc! и
\lstinline!dec!, мы легко можем показать, что \lstinline!snoc! и
\lstinline!tail! работают за амортизированное время $O(1)$, если
каждая из них используется отдельно от другой.

Основная идея неявного рекурсивного замедления состоит в том, что
когда функции вроде \lstinline!snoc! и \lstinline!tail! \emph{почти}
независимы друг от друга, мы можем сочетать их доказательства, просто
сложив долги, используемые в каждом из доказательств. Доказательство
для \lstinline!snoc! использует одну единицу долга, если хвостовая
цифра равна \lstinline!Zero!, и ноль единиц, если хвостовая цифра равна
\lstinline!One!. Доказательство для \lstinline!tail! использует одну
единицу долга, если головная цифра равна \lstinline!Two! и ноль
единиц, если головная цифра равна \lstinline!One!. Нижеследующее
доказательство сочетает эти два понятия долга.

\begin{theorem}\label{th:11.1}
  Функции \lstinline!snoc! и \lstinline!tail! работают за
  амортизированное время $O(1)$.

  \noindent
  \emph{Доказательство.} Мы анализируем реализацию очередей, используя
  метод банкира. Долг присваивается каждой задержке; задержки у нас
  всегда находятся в среднем поле какой-либо глубокой очереди.  Мы
  принимаем инвариант долга, позволяющий каждой задержке иметь размер
  долга, зависящий от цифр в головном и хвостовом поле. Среднее поле
  глубокой очереди может иметь до $|f| - |r|$ единиц долга, где $|f|$
  равно одному или двум, а $|r|$ равно нулю или одному.

  Нераздельная стоимость каждой из функций равна $O(1)$, так что нам
  остаётся показать, что ни одна из функций не высвобождает больше,
  чем $O(1)$ единиц долга. Мы приводим только доказательство для
  \lstinline!tail!. Доказательство для \lstinline!snoc! немного проще.

  Мы проводим рассуждения методом передачи долга, который
  близкородствен методу наследования долга.  Каждый раз, когда
  вложенная задержка получает больше долга, чем ей разрешено иметь, мы
  передаём этот долг объемлющей задержке, которая служит средним полем
  предыдущего узла \lstinline!Deep!. Передача долга является
  безопасной операцией, поскольку объемлющая задержка всегда
  вынуждается раньше вложенной.  Передача ответственности за
  высвобождение долга от вложенной задержки к объемлющей гарантирует,
  что этот долг будет высвобожден прежде, чем будет вынуждена
  объемлющая задержка, а следовательно, и раньше, чем может быть вынуждена
  внутренняя.

  Мы показываем, что каждый вызов \lstinline!tail! передает одну
  единицу долга в объемлющую задержку, кроме самого внешнего вызова, у
  которого объемлющей задержки нет. Этот вызов просто высвобождает
  лишний долг.

  Каждый каскад вызовов \lstinline!tail! заканчивается на вызове,
  заменяющем \lstinline!Two! на
  \lstinline!One!. (Для простоты описания, мы сейчас не учитываем
  возможность добраться до мелкой очереди.) Это уменьшает разрешённый
  размер долга для \lstinline!m! на один, так что мы передаём эту
  лишнюю единицу в объемлющую задержку.

  Всякий промежуточный вызов \lstinline!tail! заменяет \lstinline!f! с
  единицы-\lstinline!One! на двойку-\lstinline!Two! и вызывает
  \lstinline!tail! рекурсивно. Есть два подслучая:
  \begin{itemize}
  \item \lstinline!r! равно \lstinline!Zero!. Очередь \lstinline!m! имеет одну
    единицу долга, и эту единицу требуется высвободить, прежде чем мы можем
    вынудить \lstinline!m!. Мы передаём эту единицу в объемлющую
    задержку. Кроме того, создаём единицу долга, чтобы покрыть
    нераздельную стоимость рекурсивного вызова.  Наконец, нашей
    задержке передаётся одна единицы долга из рекурсивного вызова.
    Поскольку нашей задержке разрешено иметь до двух единиц долга,
    баланс оказывается в порядке.
  \item \lstinline!r! равно \lstinline!One!. Очередь \lstinline!m! не
    имеет долга, так что мы бесплатно можем её вынудить. Создаём одну
    единицу долга, чтобы покрыть нераздельную стоимость рекурсивного
    вызова. Кроме того, из рекурсивного вызова нам передаётся ещё одна
    единица долга. Поскольку разрешённый размер долга для текущей
    задержки равен одному, мы одну единицу долга оставляем у себя, а
    другую передаём в объемлющую задержку.
  \end{itemize}
\end{theorem}

\begin{exercise}\label{ex:11.1}
  Реализуйте для этих очередей функции \lstinline!lookup! и
  \lstinline!update!. Эти функции должны работать за амортизированное
  время $O(\log i)$. Может быть полезно снабдить каждую очередь
  полем, содержащим её размер.
\end{exercise}

\begin{exercise}\label{ex:11.2}
  С помощью методик, описанных в этом разделе, реализуйте двусторонние
  очереди.
\end{exercise}

\section{Двусторонние очереди с конкатенацией}
\label{sc:11.2}

Наконец, мы реализуем с помощью неявного рекурсивного замедления
двусторонние очереди с конкатенацией, чья сигнатура приведена на
Рис.~\ref{sc:11.2}. Сначала мы описываем относительно простую
реализацию, поддерживающую $\concat$ за амортизированное время $O(\log
n)$, а остальные операции за амортизированное время $O(1)$. Затем мы
строим намного более сложную реализацию, которая улучшает время работы
$\concat$ до $O(1)$.

\begin{figure}
  \centering

  (*\mbox{ Возбуждает }Empty\mbox{, если дек пуст }*)\\
  (*\mbox{ Возбуждает }Empty\mbox{, если дек пуст }*)\\
  (*\mbox{ Возбуждает }Empty\mbox{, если дек пуст }*)\\
  (*\mbox{ Возбуждает }Empty\mbox{, если дек пуст }*)\\

  \caption{Сигнатура для двусторонних очередей с конкатенацией.}
  \label{fig:11.2}
\end{figure}

Рассмотрим следующую реализацию двусторонних очередей с конкатенацией,
или c-деков. C-дек является либо \term{мелким}{shallow}, либо
\term{глубоким}{deep}. Мелкий c-дек~--- это просто обыкновенный дек,
например, дек по методу банкира из Раздела~\ref{sc:8.4.2}. Глубокий
c-дек состоит из трёх частей: \term{front}{голова},
\term{середина}{middle} и \term{хвост}{rear}. Голова и хвост являются
обыкновенными деками, содержащими не меньше двух элементов
каждый. Середина является c-деком с обыкновенными деками в качестве
элементов, каждый из которых не короче двух. Мы предполагаем, что есть
реализация \lstinline!D!, реализующая сигнатуру \lstinline!Deque!, и
все её функции работают за время $O(1)$ (амортизированное или
жёсткое).
\begin{lstlisting}
  datatype $\alpha$ Cat =
         Shallow of $\alpha$ D.Queue
       | Deep of $\alpha$ D.Queue $\times$ $\alpha$ D.Deque Cat susp $\times$ $\alpha$ D.Queue
\end{lstlisting}
Заметим, что это определение предполагает полиморфную рекурсию.

Чтобы добавить элемент к какому-либо концу, мы просто добавляем его в
головной или хвостовой дек. Например, \lstinline!cons! реализован как
\begin{lstlisting}
  fun cons (x, Shallow d) = Shallow (D.cons (x, d))
    | cons (x, Deep (f, m, r)) = Deep (D.cons (x, f), m, r)
\end{lstlisting}
Чтобы уничтожить элемент на каком-либо конце, мы уничтожаем элемент из
головного либо хвостового дека. Если при этом длина этого дека падает
ниже двух, мы извлекаем следующий дек из середины и делаем его новой
головой либо хвостом. С добавлением остающегося элемента из старого
дека новый дек содержит по крайней мере три элемента. Например, код
\lstinline!tail! выглядит как
\begin{lstlisting}
  fun tail (Shallow d) = Shallow (D.tail d)
    | tail (Deep (f, m, r) =
        let f' = D.tail f
        in
           if not (tooSmall f') then Deep (f', m, r)
           else if isEmpty (force m) then Shallow (dappendL (f', r))
           else Deep (dappendL (f', head (force m)), $\$$tail (force m), r)
        end
\end{lstlisting}
где функция \lstinline!tooSmall! возвращает истину, если длина дека
меньше двух, а \lstinline!dappendL! добавляет дек длины один или два к
деку произвольной длины.

Заметим, что вызовы \lstinline!tail! распространяются на следующий
уровень c-дека только в том случае, когда длина головного дека равна
двум. В терминах из Раздела~\ref{sc:9.2.3} мы можем сказать, что дек
длиной три или более \term{безопасен}{safe}, а дек длиной два
\term{опасен}{dangerous}.  Каждый раз, когда \lstinline!tail!
рекурсивно себя вызывает на следующем уровне, он переводит головной
дек из опасного состояния в безопасное, так что ни на каком уровне
c-дека два последовательных вызова \lstinline!tail! не могут
распространиться на следующий уровень. Мы легко можем доказать, что
\lstinline!tail! работает за амортизированное время $O(1)$, позволив
безопасному деку иметь одну единицу долга, а опасному ноль.

\begin{exercise}\label{ex:11.3}
  Докажите, что \lstinline!tail! и \lstinline!init! вместе работают за
  амортизированное время $O(1)$, сочетая их правила накопления долга
  согласно методике неявного рекурсивного замедления.
\end{exercise}

Как реализовать конкатенацию? Чтобы сконкатенировать два глубоких
c-дека \lstinline!c$_1$! и \lstinline!c$_2$!, мы сохраняем голову
\lstinline!c$_1$! как новую голову, хвост \lstinline!c$_2$! как новый
хвост, а из оставшихся элементов собираем новую середину: хвост
\lstinline!c$_1$! вставляем в середину \lstinline!c$_1$!, голову
\lstinline!c$_2$! в середину \lstinline!c$_2$!, а затем конкатенируем
результаты.
\begin{lstlisting}
  fun (Deep (f$_1$, m$_1$, r$_1$)) $\concat$ (Deep (f$_2$, m$_2$, r$_2$)) =
        Deep (f$_1$, $\$$(snoc (force m$_1$, r$_1$) $\concat$ cons (f$_2$, force m$_2$)), r$_2$)
\end{lstlisting}
(Разумеется, есть ещё варианты, когда \lstinline!c$_1$! или
\lstinline!c$_2$! являются мелкими.) Заметим, что глубина рекурсии
$\concat$ равна глубине более мелкого c-дека. Кроме того, $\concat$
создаёт $O(1)$ долга на каждом уровне, и весь этот долг нужно
немедленно высвободить, чтобы восстановить инвариант долга для
\lstinline!tail! и \lstinline!init!. Следовательно, время работы
$\concat$ равно $O(\min (\log n_1, \log n_2))$, где $n_i$~--- длина
\lstinline!c$_i$!.

Полный код этой реализации c-деков приведён на Рис.~\ref{fig:11.3}.

\begin{figure}
  \centering
  (* $\mbox{предполагает полиморфную рекурсию!}$ *)  \\
  \mbox{\ldots{} \lstinline!snoc!, \lstinline!last! и \lstinline!init!
    определяются симметричным образом \ldots}\\

  \caption{Простые деки с конкатенацией.}
  \label{fig:11.3}
\end{figure}

Чтобы улучшить время работы $\concat$ до $O(1)$, мы изменяем
представление c-деков так, чтобы операция $\concat$ не вызывала сама
себя рекурсивно. Основная идея состоит в том, чтобы $\concat$ каждого уровня
обращалась на следующем уровне только к \lstinline!cons! и
\lstinline!snoc!. Вместо трёх сегментов мы теперь заставляем глубокие
c-деки содержать пять сегментов: $(f, a, m, b, r)$. $f$, $m$ и $r$
представляют собой обыкновенные деки; $f$ и $r$ содержат при этом не
менее трёх элементов каждый, а $m$ не менее двух элементов. $a$ и $b$
представляют собой c-деки \term{составных элементов}{compound
  elements}. Вырожденный составной элемент является обыкновенным деком,
содержащим не менее двух элементов.  Полный составной элемент содержит
три сегмента: $(f, c, r)$, где $f$ и $r$~--- обыкновенные деки,
содержащие не меньше чем по два элемента каждый, а $m$~--- c-дек
составных элементов. Этот тип данных может быть записан на Стандартном
ML (с полиморфной рекурсией) так:
\begin{lstlisting}
  datatype $\alpha$ Cat =
         Shallow of $\alpha$ D.Queue
       | Deep of $\alpha$ D.Queue                      (* $\ge 3$ *)
                 $\times$ $\alpha$ CmpdElem Cat susp
                 $\times$ $\alpha$ D.Queue                     (* $\ge 2$ *)
                 $\times$ $\alpha$ CmpdElem Cat susp
                 $\times$ $\alpha$ D.Queue                     (* $\ge 3$ *)
  and $\alpha$ CmpdElem =
              Simple of $\alpha$ D.Queue               (* $\ge 2$ *)
            | Cmpd of $\alpha$ D.Queue                 (* $\ge 2$ *)
                      $\times$ $\alpha$ CmpdElem Cat susp
                      $\times$ $\alpha$ D.Queue                (* $\ge 2$ *)
\end{lstlisting}
Если нам даны глубокие c-деки
\lstinline!c$_1$ = Deep (f$_1$, a$_1$, m$_1$, b$_1$, r$_1$)! и
\lstinline!c$_2$ = Deep (f$_2$, a$_2$, m$_2$, b$_2$, r$_2$)!, их
конкатенация вычисляется следующим образом: прежде всего,
\lstinline!f$_1$! сохраняется как голова результата, а
\lstinline!r$_2$! как хвост результата. Затем мы строим новый
срединный дек из последнего элемента \lstinline!r$_1$! и первого
элемента \lstinline!f$_2$!.  Затем мы порождаем составной элемент из
\lstinline!m$_1$!, \lstinline!b$_1$! и остатка \lstinline!r$_1$!, и
прицепляем его к концу \lstinline!a$_1$! через \lstinline!snoc!. Это
будет сегмент \lstinline!a! результата. Наконец, мы порождаем
составной элемент из остатка \lstinline!f$_2$!, \lstinline!a$_2$! и
\lstinline!m$_2$!, и присоединяем его к началу \lstinline!b$_2$!. Это
будет сегмент \lstinline!b! результата. Вся реализация выглядит как
\begin{lstlisting}
  fun (Deep (f$_1$, a$_1$, m$_1$, b$_1$, r$_1$)) $\concat$ (Deep (f$_2$, a$_2$, m$_2$, b$_2$, r$_2$)) =
        let val (r$'_1$, m, f$'_2$) = share (r$_1$, f$_2$)
            val a$'_1$ - $\$$snoc (force a$_1$, Cmpd (m$_1$, b$_1$, r$'_1$))
            val b$'_2$ = $\$$cons (Cmpd (f$'_2$, a$_2$, m$_2$), force b$_2$)
        in Deep (f$_1$, a$'_1$, m, b$'_2$, r$_2$) end
\end{lstlisting}
где
\begin{lstlisting}
  fun share (f, r) =
        let val m = D.cons (D.last f, D.cons (D.head r, D.empty))
        in (D.init f, m, D.tail r)
  fun cons (x, Deep (f, a, m, b, r)) = Deep (D.cons (x, f), a, m, b, r)
  fun snoc (Deep (f, a, m, b, r), x) = Deep (f, a, m, b, D.snoc (r, x))
\end{lstlisting}
(Ради простоты описания мы опускаем варианты с участием мелких
c-деков.)

К сожалению, \lstinline!tail! и \lstinline!init! в этой реализации
устроены весьма коряво. Поскольку эти две функции симметричны, мы
описываем только \lstinline!tail!. Если у нас есть c-дек
\lstinline!Deep (f, a, m, b, r)!, возможны шесть вариантов:
\begin{itemize}
\item $|\lstinline!f!| > 3$
\item $|\lstinline!f!| = 3$
  \begin{itemize}
  \item \lstinline!a! непуст.
    \begin{itemize}
    \item Первый составной элемент \lstinline!a! вырожден.
    \item Первый составной элемент \lstinline!a! невырожден.
    \end{itemize}
  \item \lstinline!a! пуст, а \lstinline!b! непуст.
    \begin{itemize}
    \item Первый составной элемент \lstinline!b! вырожден.
    \item Первый составной элемент \lstinline!b! невырожден.
    \end{itemize}
  \item \lstinline!a! и \lstinline!b! оба пусты.
  \end{itemize}
\end{itemize}
Мы описываем поведение \lstinline!tail c! в первых трёх
случаях. Код для оставшихся случаев можно найти в полной реализации,
приведенной на Рис.~\ref{fig:11.4} и \ref{fig:11.5}. Если
$|\lstinline!f!| > 3$, мы просто заменяем \lstinline!f! на
\lstinline!D.tail f!. Если $|\lstinline!f!| = 3$, то
уничтожение первого элемента \lstinline!f! сделает его размер меньше
разрешённого. Следовательно, нам нужно вынуть новый головной дек из
\lstinline!a! и состыковать его с остающимися в \lstinline!f! двумя
элементами. Новый \lstinline!f! содержит не меньше четырёх элементов,
так что следующий вызов \lstinline!tail! пойдёт по ветке
$|\lstinline!f!| > 3$.

\begin{figure}
  \centering

  (* \mbox{Предполагается, что \lstinline!D! поддерживает функцию \lstinline!size!} *)\\
  \mbox{\ldots{} \lstinline!snoc! и \lstinline!last! определяются симметричным образом \ldots}\\

  \caption{Деки с конкатенацией, использующие неявное рекурсивное замедление (часть I).}
  \label{fig:11.4}
\end{figure}

\begin{figure}
  \centering
  \mbox{\ldots{} \lstinline!replaceLast! и \lstinline!init! определяются симметричным образом \ldots}\\

  \caption{Деки с конкатенацией, использующие неявное рекурсивное замедление (часть II).}
  \label{fig:11.5}
\end{figure}

Когда мы извлекаем первый составной элемент из \lstinline!a!, чтобы
построить новый головной дек, этот составной элемент может быть
вырожденным или невырожденным. Если он вырожденный (т.~е.,
обыкновенный дек), новым значением \lstinline!a! будет
\lstinline!$\$$tail (force a)!. Если же мы получаем полный составной
элемент \lstinline!Cmpd (f', c', r')!, то \lstinline!f'! оказывается
новым значением \lstinline!f! (вместе с остающимися элементами старого
\lstinline!f!), а новое значение \lstinline!a! будет
$$
\lstinline!$\$$(force c' $\concat$ cons (Simple r', tail (force a)))!
$$
Заметим, однако, что в результате комбинации \lstinline!cons! и
\lstinline!tail! мы просто заменяем первый элемент
\lstinline!a!. Можно сделать это напрямую, избежав тем самым ненужного
вызова \lstinline!tail!, с помощью функции \lstinline!replaceHead!.
\begin{lstlisting}
  fun replaceHead (x, Shallow d) = Shallow (D.cons (x, D.tail d))
    | replaceHead (x, Deep (f, a, m, b, r) =
        Deep (D.cons (x, D.tail f), a, m, b, r)
\end{lstlisting}
Оставшиеся варианты \lstinline!tail! устроены похожим образом;
каждый из них производит $O(1)$ работы, а затем делает максимум один
вызов \lstinline!tail!.

\begin{remark}
  Этот код можно записать намного короче и намного понятнее с
  использованием языковой конструкции, называемой
  \term{взгляды}{views} \cite{Wadler1987, BurtonCameron1993,
    PalaoGostanzaPenaNunez1996}, позволяющей устраивать сопоставление
  с образцом на абстрактных типах данных. Детали можно найти в
  \cite{Okasaki1997}. В Стандартном ML взгляды не поддерживаются.
\end{remark}

В функциях \lstinline!cons!, \lstinline!snoc!, \lstinline!head! и
\lstinline!last! ленивое вычисление не используется, и легко видеть,
что все они работают за время $O(1)$. Остальные функции мы анализируем
методом банкира с использованием передачи долга.

Как всегда, мы присваиваем долг каждой задержке. Задержки содержатся в
сегментах \lstinline!a! и \lstinline!b! глубокого c-дека, а также в
средних сегментах (\lstinline!c!) составных элементов. Каждому полю
\lstinline!c! мы разрешаем иметь до четырёх единиц долга, а полям
\lstinline!a! и \lstinline!b! мы позволяем иметь от нуля до пяти
единиц, в зависимости от длины полей \lstinline!f! и
\lstinline!r!. Базовый лимит полей \lstinline!a! и \lstinline!b! равен
нулю. Если в поле \lstinline!f! содержится более трёх элементов, то
лимит поля \lstinline!a! увеличивается на четыре, а лимит поля
\lstinline!b! на одну единицу. Подобным образом, если поле
\lstinline!r! содержит более трёх элементов, то лимит поля
\lstinline!b! увеличивается на четыре, а лимит поля \lstinline!a! на
одну единицу.

\begin{theorem}\label{th:11.2}
  Функции $\concat$, \lstinline!tail! и \lstinline!init! работают за
  амортизированное время $O(1)$.

  \noindent
  \emph{Доказательство.} ($\concat$) Интересный случай~---
  конкатенация двух c-деков
  \lstinline!Deep (f$_1$, a$_1$, m$_1$, b$_1$, r$_1$)! и
  \lstinline!Deep (f$_2$, a$_2$, m$_2$, b$_2$, r$_2$)!.
  В этом случае $\concat$ производит $O(1)$ нераздельной работы и
  высвобождает не более четырёх единиц долга. Во-первых, мы создаём
  две единицы долга для задержанных вызовов \lstinline!snoc! и
  \lstinline!cons! для \lstinline!a! и \lstinline!b!
  соответственно. Эти две единицы мы всегда высвобождаем. Кроме того,
  если на \lstinline!b$_1$! или \lstinline!a$_2$! висит пять единиц
  долга, нам нужно высвободить одну единицу, когда этот сегмент
  становится серединой составного элемента.  Наконец, если в
  \lstinline!f$_1$! содержится только три элемента, а в
  \lstinline!f$_2$! более трёх элементов, нам нужно высвободить
  единицу долга из \lstinline!b$_2$!, поскольку он становится новым
  \lstinline!b!; и то же самое справедливо для \lstinline!r$_1$! и
  \lstinline!r$_2$!. Заметим, однако, что если на \lstinline!b$_1$!
  висит пять единиц долга, то \lstinline!f$_1$! содержит более трёх
  элементов, а если на \lstinline!a$_2$! висит пять единиц долга, то
  \lstinline!r$_2$! содержит более трёх элементов. Следовательно,
  всего нам нужно высвободить не больше четырёх единиц
  долга, или, по крайней мере, передать этот долг объемлющей задержке.

  (\lstinline!tail! и \lstinline!init!) Поскольку функции
  \lstinline!tail! и \lstinline!init! симметричны, мы приводим
  рассуждение только для \lstinline!tail!. Простым просмотром можно
  убедиться, что \lstinline!tail! совершает $O(1)$ нераздельной
  работы, так что нам остаётся показать, что она высвобождает не более
  $O(1)$ долга. Мы покажем, что размер высвобождаемого долга не
  превышает пять единиц.

  Поскольку \lstinline!tail! может вызывать сама себя рекурсивно, нам
  нужно учитывать возможность каскада вызовов \lstinline!tail!. Мы
  используем в рассуждениях передачу долга. Пусть у нас есть глубокий
  c-дек \lstinline!Deep (f, a, m, b, r)!. Нужно рассмотреть каждый
  вариант поведения \lstinline!tail!.

  Если $|\lstinline!f!| > 3$, мы находимся в конце каскада. Нового
  долга не создаётся, но извлечение элемента из \lstinline!f! может
  уменьшить разрешённый размер долга для \lstinline!a! на четыре
  единицы, а \lstinline!b! на одну единицу, так что мы передаём этот
  долг объемлющей задержке.

  Если $|\lstinline!f!| > 3$, то предположим, что \lstinline!a!
  непуст. (Случаи с пустым \lstinline!a! не содержат принципиальных
  отличий.) Если $|\lstinline!r!| > 3$, то \lstinline!a!
  может иметь одну единицу долга, которую мы передаём в объемлющую
  задержку. В противном случае \lstinline!a! не должен иметь
  долга. Если голова \lstinline!a! является вырожденным составным
  элементом (т.~е., простым деком элементов), то он становится новым
  значением \lstinline!f! вместе с оставшимися элементами старого
  \lstinline!f!. Новое значение \lstinline!a! представляет собой
  задержку от результата применения \lstinline!tail! к старому
  \lstinline!a!. Эта задержка получает до пяти единиц долга из
  рекурсивного вызова \lstinline!tail!. Поскольку новый разрешённый
  размер долга для \lstinline!a! не меньше четырёх, мы передаём не
  более одной единицы долга в объемлющую задержку, и всего
  передаваемых единиц долга получается не больше двух. (На самом деле,
  размер передаваемого долга не больше одного, поскольку здесь мы
  передаём одну единицу в точности в тех случаях, когда нам не нужно
  было передавать одну единицу долга из исходного \lstinline!a!.)

  Если же голова \lstinline!a! является невырожденным составным
  элементом \lstinline!Cmpd (f', c', r')!, то \lstinline!f'!
  становится новым значением \lstinline!f! вместе с остающимися
  элементами старого \lstinline!f!. Вычисление нового \lstinline!a!
  требует вызовов $\concat$ и \lstinline!replaceHead!. Полное число
  получаемых при этом единиц долга равно девяти: четыре от
  \lstinline!c'!, четыре от $\concat$ и одна свежесозданная единица
  долга от \lstinline!replaceHead!. Разрешённый размер долга для
  нового \lstinline!a! равен либо четырём, либо пяти, так что либо
  четыре, либо пять единиц долга мы передаём объемлющей
  задержке. Поскольку четыре единицы требуется передавать ровно в тех
  случаях, когда одну единицу нужно было передать из старого значения
  \lstinline!a!, всего требуется передать не более пяти единиц долга.
\end{theorem}

\begin{exercise}\label{ex:11.4}
  Пусть имеется реализация \lstinline!D! деков без
  конкатенации. Реализуйте списки с конкатенацией, используя тип
  \begin{lstlisting}
    datatype $\alpha$ Cat =
           Shallow of $\alpha$ D.Queue
         | Deep of $\alpha$ D.Queue $\times$ $\alpha$ CmpdElem Cat susp $\times$ $\alpha$ D.Queue
    and $\alpha$ CmpdElem = Cmpd of $\alpha$ D.Queue $\times$ $\alpha$ CmpdElem Cat susp
  \end{lstlisting}
  причём как головной дек глубокого (\lstinline!Deep!) узла, так и дек
  в узле \lstinline!Cmpd! должны содержать не менее двух
  элементов. Докажите, что все функции в вашей реализации работают за
  амортизированное время $O(1)$ при условии, что все функции в
  \lstinline!D! работают за время $O(1)$ (ограничение может быть
  жёстким или амортизированным).
\end{exercise}

\section{Примечания}
\label{sc:11.3}

\noindent
\textbf{Рекурсивное замедление} Понятие рекурсивного замедления было
введено Капланом и Тарьяном в \cite{KaplanTarjan1995} и снова
использовано ими же в \cite{KaplanTarjan1996b}, но оно
близкородственно ограничениям регулярности у Гибаса и
др. \cite{Guibas-etal1977}. Бродал \cite{Brodal1995} пользовался
похожим методом при реализации куч.

\textbf{Деки с конкатенацией} Бухсбаум и Тарьян
\cite{BuchsbaumTarjan1995} представляют чисто функциональную
реализацию деков с конкатенацией, которая поддерживает
\lstinline!tail! и \lstinline!init! за время $O(\log^* n)$ в худшем
случае, а все остальные операции за $O(1)$ в худшем случае. Наша
реализация улучшает этот показатель до $O(1)$ для всех операций, но
ограничения получаются амортизированными, а не жёсткими. Независимо от
нас, Каплан и Тарьян разработали похожую реализацию с жёсткими
показателями $O(1)$. Однако детали их реализации весьма сложны.

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "pfds"
%%% End: