57
худшем случае будет достигать n
2
, в то время как интуитивно ясно, что
скорость работы хорошего алгоритма разглаживания дерева должна
зависеть от количества узлов в дереве линейно.
Скорость работы функции разглаживания дерева можно увеличить,
если использовать дополнительные накапливающие аргументы функции,
как мы это уже делали раньше, программируя функции для вычисления
значения члена последовательности Фибоначчи по его
номеру и для
обращения списка. Дополнительным накапливающим аргументом для
функции разглаживания дерева мог бы быть список, к голове которого
присоединяется результат разглаживания дерева. Если обозначить
вспомогательную рекурсивную функцию flatten', то результат ее
работы определяется следующим соотношением:
flatten' tree list = (flatten tree) ++ list
Определение функции flatten' можно легко построить без
использования операции соединения списков. После этого достаточно
будет выразить результат работы функции flatten через flatten'.
Вот как будет выглядеть часть программы, содержащая уравнения для
функций flatten и flatten' (листинг 1.29):
Листинг 1.29. Более эффективная функция разглаживания дерева
flatten' Null list = list
flatten' (Tree node tl tr) list =
flatten' tl (node : (flatten' tr list))
flatten tree = flatten' tree []
В следующей главе мы рассмотрим еще одно определение функции
разглаживания дерева, в котором результат тоже будет достигаться за
линейное время. А сейчас давайте рассмотрим более подробно аппарат
определения классов и их реализаций в языке Haskell.
Класс – это набор операций (функций), которые могут применяться к
объектам определенных типов. В языке Haskell классы
определяются
формально, то есть просто объявляется список описаний типов для
некоторого набора функций и бинарных операций. Конкретный тип будет
принадлежать объявленному классу, если для него определены все
функции, объявленные в классе. В языке Haskell изначально определено
довольно большое количество классов, которым принадлежат стандартные
типы языка. Так, например, имеется класс Eq,
содержащий операции
сравнения '==' и '!='. Все стандартные примитивные типы, такие как
Int, Char, Bool принадлежат этому классу, так как для них определены
соответствующие операции. Для того, чтобы объявить, что заданный тип
принадлежит некоторому классу, надо предоставить реализацию всех
функций, определенных в классе.
Рассмотрим определение класса Eq как оно определено в
стандартной библиотеке языка.