Изучай Haskell во имя добра! (Липовача) - страница 43

, то есть, по сути, >[(1,'a'),(2,'b')].

Давайте реализуем ещё одну функцию из стандартной библиотеки – >elem. Она принимает элемент и список и проверяет, есть ли заданный элемент в этом списке. Как обычно, базовый случай — это пустой список. Мы знаем, что в пустом списке нет элементов, так что в нём определённо нет ничего, что мы могли бы искать.

>elem' :: (Eq a) => a –> [a] –> Bool

>elem' a [] = False

>elem' a (x:xs)

>  | a == x = True

>  | otherwise = a `elem'` xs

Довольно просто и ожидаемо. Если «голова» не является искомым элементом, мы проверяем «хвост». Если мы достигли пустого списка, то результат – >False.

Итак, у нас есть список элементов, которые могут быть отсортированы. Их тип – экземпляр класса >Ord. А теперь требуется их отсортировать! Для этого предусмотрен очень классный алгоритм, называемый быстрой сортировкой (quicksort). Это довольно-таки хитроумный способ. В то время как его реализация на императивных языках занимает многим более 10 строк, на языке Haskell он намного короче и элегантнее. Настолько, что быстрая сортировка на Haskell стала притчей во языцех. Только ленивый не приводил пример определения функции >quicksort, чтобы наглядно продемонстрировать изящество языка. Давайте и мы напишем её, несмотря на то что подобный пример уже считается дурным тоном.

Итак, сигнатура функции будет следующей:

>quicksort :: (Ord a) => [a] –> [a]

Ничего удивительного тут нет. Базовый случай? Пустой список, как и следовало ожидать. Отсортированный пустой список – это пустой список. Затем следует основной алгоритм: отсортированный список – это список, в котором все элементы, меньшие либо равные «голове» списка, идут впереди (в отсортированном порядке), посередине следует «голова» списка, а потом – все элементы, большие «головы» списка (также отсортированные). Заметьте, в определении мы упомянули сортировку дважды, так что нам, возможно, придётся делать два рекурсивных вызова в теле функции. Также обратите внимание на то, что мы описали алгоритм, просто дав определение отсортированному списку. Мы не указывали явно: «делай это, затем делай то…» В этом красота функционального программирования! Как нам отфильтровать список, чтобы получить только те элементы, которые больше «головы» списка, и те, которые меньше? С помощью генераторов списков.

Если у нас, скажем, есть список >[5,1,9,4,6,7,3] и мы хотим отсортировать его, этот алгоритм сначала возьмёт «голову», которая равна >5, и затем поместит её в середину двух списков, где хранятся элементы меньшие и большие «головы» списка. То есть в нашем примере получается следующее: