preface.tex

\chapter*{Предисловие}

Я впервые познакомился с языком Стандартный ML в 1989 году. Мне всегда
нравилось программировать эффективные реализации структур данных,
и я немедленно занялся переводом некоторых своих любимых программ
на Стандартный ML. Для некоторых структур перевод оказался достаточно
простым и, к моему большому удовольствию, получался код значительно более краткий
и ясный, чем предыдущие версии, написанные мной на C, Pascal или
Ada.  Однако не всегда результат оказывался столь приятным. Раз за
разом мне приходилось использовать разрушающее присваивание, которое в
Стандартном ML не приветствуется, а во многих других функциональных
языках вообще запрещено.  Я пытался обращаться к литературе, но
нашел лишь несколько разрозненных статей.  Понемногу я стал понимать,
что столкнулся с неисследованной областью, и начал искать новые
способы решения задач.

Сейчас, восемь лет спустя, мой поиск продолжается. Всё ещё есть много
примеров структур данных, которые я просто не знаю как эффективно
реализовать на функциональном языке. Однако за это время я получил
множество уроков о том, что в функциональных языках
\textit{работает}.  Эта книга является попыткой записать выученные
уроки, и я надеюсь, что она послужит справочником для функциональных
программистов, а также как текст для тех, кто хочет больше узнать о
структурах данных в функциональном окружении.

\textbf{Стандартный ML.} Несмотря на то, что структуры данных из этой
книги можно реализовать практически на любом функциональном языке, я
во всех примерах буду использовать Стандартный ML.  У этого языка
имеются следующие преимущества для моих целей: (1) энергичный
порядок вычислений, что значительно упрощает рассуждения о том,
сколько времени потребует тот или иной алгоритм, и (2) замечательная
система модулей, идеально подходящая для выражения абстрактных типов
данных.  Однако пользователи других языков, например, Haskell или
Lisp, смогут без труда адаптировать мои примеры к своим вычислительным
окружениям. (В приложении я привожу переводы большинства примеров на
Haskell.) Даже программисты на C или Java должны быть способны
реализовать эти структуры данных, хотя в случае C отсутствие
автоматической сборки мусора иногда будет доставлять неприятности.

Читателям, незнакомым со Стандартным ML, я рекомендую в качестве
введения книги \textit{ML для программиста-практика} Полсона
\cite{Paulson1996} или \textit{Элементы программирования на ML}
Ульмана \cite{Ullman1994}.

\textbf{Прочие предварительные требования.} Эта книга не рассчитана
служить первоначальным общим введением в структуры данных. Я
предполагаю, что читателю достаточно знакомы основные абстрактные
структуры данных~--- стеки, очереди, кучи (приоритетные очереди) и
конечные отображения (словари).  Кроме того, я предполагаю знакомство
с основами анализа алгоритмов, особенно с нотацией <<большого O>>
(напр., $O(n \log n)$). Обычно эти вопросы рассматриваются во втором
курсе для студентов, изучающих информатику.

\textbf{Благодарности.} Мое понимание функциональных структур данных
чрезвычайно обогатилось в результате дискуссий со многими
специалистами на протяжении многих лет.  Мне бы особенно хотелось
поблагодарить Питера Ли, Генри Бейкера, Герта Бродала, Боба Харпера,
Хаима Каплана, Грэма Мосса, Саймона Пейтон Джонса и Боба Тарждана.



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