Миран Липовача - Изучай Haskell во имя добра!

• Название: Изучай Haskell во имя добра!
• Автор: Миран Липовача
• Жанр: Программирование
• Год: 2012
• ISBN: 978-5-94074-749-9

На взгляд автора, сущность программирования заключается в решении проблем. Программист всегда думает о проблеме и возможных решениях – либо пишет код для выражения этих решений.

Язык Haskell имеет множество впечатляющих возможностей, но главное его свойство в том, что меняется не только способ написания кода, но и сам способ размышления о проблемах и возможных решениях. Этим Haskell действительно отличается от большинства языков программирования. С его помощью мир можно представить и описать нестандартным образом. И поскольку Haskell предлагает совершенно новые способы размышления о проблемах, изучение этого языка может изменить и стиль программирования на всех прочих.

Ещё одно необычное свойство Haskell состоит в том, что в этом языке придаётся особое значение рассуждениям о типах данных. Как следствие, вы помещаете больше внимания и меньше кода в ваши программы.

Вне зависимости от того, в каком направлении вы намерены двигаться, путешествуя в мире программирования, небольшой заход в страну Haskell себя оправдает. А если вы решите там остаться, то наверняка найдёте чем заняться и чему поучиться!

Эта книга поможет многим читателям найти свой путь к Haskell.

Отображения, монады, моноиды и другое!

Всё сказано в названии: «Изучай Хаскель во имя добра!» – весёлый иллюстрированный самоучитель по этому сложному функциональному языку.

С помощью оригинальных рисунков автора, отсылке к поп-культуре, и, самое главное, благодаря полезным примерам кода, эта книга обучает основам функционального программирования так, как вы никогда не смогли бы себе представить.

Вы начнете изучение с простого материала: основы синтаксиса, рекурсия, типы и классы типов. Затем, когда вы преуспеете в основах, начнется настоящий мастер-класс от профессионала: вы изучите, как использовать аппликативные функторы, монады, застежки, и другие легендарные конструкции Хаскеля, о которых вы читали только в сказках.

Продираясь сквозь образные (и порой безумные) примеры автора, вы научитесь:

• Смеяться в лицо побочным эффектам, поскольку вы овладеете техниками чистого функционального программирования.

• Использовать волшебство «ленивости» Хаскеля для игры с бесконечными наборами данных.

• Организовывать свои программы, создавая собственные типы, классы типов и модули.

• Использовать элегантную систему ввода-вывода Хаскеля, чтобы делиться гениальностью ваших программ с окружающим миром.

Нет лучшего способа изучить этот мощный язык, чем чтение «Изучай Хаскель во имя добра!», кроме, разве что, поедания мозга его создателей.

Миран Липовача (Miran Lipovača) изучает информатику в Любляне (Словения). Помимо его любви к Хаскелю, ему нравится заниматься боксом, играть на бас-гитаре и, конечно же, рисовать. У него есть увлечение танцующими скелетами и числом 71, а когда он проходит через автоматические двери, он притворяется, что на самом деле открывает их силой своей мысли.

---

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

quicksort [] = []

quicksort (x:xs) =

  let smallerSorted = quicksort (filter (<= x) xs)

      biggerSorted = quicksort (filter (> x) xs)

  in  smallerSorted ++ [x] ++ biggerSorted

Ещё немного примеров использования map и filter

Давайте найдём наибольшее число меньше 100 000, которое делится на число 3829 без остатка. Для этого отфильтруем множество возможных вариантов, в которых, как мы знаем, есть решение.

largestDivisible :: Integer

largestDivisible = head (filter p [100000,99999..])

  where p x = x `mod` 3829 == 0

Для начала мы создали список всех чисел меньших 100 000 в порядке убывания. Затем отфильтровали список с помощью предиката. Поскольку числа отсортированы в убывающем порядке, наибольшее из них, удовлетворяющее предикату, будет первым элементом отфильтрованного списка. Нам даже не нужно использовать конечный список для нашего базового множества. Снова «лень в действии»! Поскольку мы используем только «голову» списка, нам неважно, конечен полученный список или бесконечен. Вычисления прекращаются, как только находится первое подходящее решение.

Теперь мы собираемся найти сумму всех нечётных квадратов меньших 10 000. Но для начала познакомимся с функцией takeWhile: она пригодится в нашем решении. Она принимает предикат и список, а затем начинает обход списка с его «головы», возвращая те его элементы, которые удовлетворяют предикату. Как только найден элемент, не удовлетворяющий предикату, обход останавливается. Если бы мы хотели получить первое слово строки "слоны умеют веселиться", мы могли бы сделать такой вызов: takeWhile (/=' ') "слоны умеют веселиться", и функция вернула бы "слоны".

Итак, в первую очередь начнём применять функцию (^2) к бесконечному списку [1..]. Затем отфильтруем список, чтобы в нём были только нечётные элементы. Далее возьмём из него значения, меньшие 10000. И, наконец, получим сумму элементов этого списка. Нам даже не нужно задавать для этого функцию – достаточно будет одной строки в GHCi:

ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

166650

Потрясающе! Мы начали с некоторых начальных данных (бесконечный список натуральных чисел) и затем применяли к ним функцию, фильтровали, прореживали до тех пор, пока список не удовлетворил нашим запросам, а затем просуммировали его. Можно было бы воспользоваться генераторами списков для той же цели:

ghci> sum (takeWhile (<10000) [m | m <– [n^2 | n <– [1..]], odd m])

166650

В следующей задаче мы будем иметь дело с рядами Коллатца. Берём натуральное число. Если это число чётное, делим его на два. Если нечётное – умножаем его на 3 и прибавляем единицу. Берём получившееся значение и снова повторяем всю процедуру, получаем новое число, и т. д. В сущности, у нас получается цепочка чисел. С какого бы значения мы ни начали, цепочка заканчивается на единице. Если бы начальным значением было 13, мы бы получили такую последовательность: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Всё по вышеприведённой схеме: 13 × 3 + 1 равняется 40; 40, разделённое на 2, равно 20, и т. д. Как мы видим, цепочка имеет 10 элементов.

Теперь требуется выяснить: если взять все стартовые числа от 1 до 100, как много цепочек имеют длину больше 15? Для начала напишем функцию, которая создаёт цепочку:

chain :: Integer -> [Integer]

chain 1 = [1]

chain n

    | even n = n:chain (n `div` 2)

    | odd n  = n:chain (n*3 + 1)

Так как цепочка заканчивается на единице, это базовый случай. Получилась довольно-таки стандартная рекурсивная функция.

ghci> chain 10

[10,5,16,8,4,2,1]

ghci> chain 1

[1]

ghci> chain 30

[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]

Так! Вроде бы работает правильно. Ну а теперь функция, которая ответит на наш вопрос:

numLongChains :: Int

numLongChains = length (filter isLong (map chain [1..100]))

  where isLong xs = length xs > 15

Мы применяем функцию chain к списку [1..100], чтобы получить список цепочек; цепочки также являются списками. Затем фильтруем их с помощью предиката, который проверяет длину цепочки. После фильтрации смотрим, как много цепочек осталось в результирующем списке.

ПРИМЕЧАНИЕ. Эта функция имеет тип numLongChains :: Int, потому что length возвращает значение типа Int вместо экземпляра класса Num – так уж сложилось исторически. Если мы хотим вернуть более общий тип, имеющий экземпляр класса Num, нам надо применить функцию fromIntegral к результату, возвращённому функцией length.

Функция map для функций нескольких переменных

Используя функцию map, можно проделывать, например, такие штуки: map (*) [0..] – если не для какой-либо практической цели, то хотя бы для того, чтобы продемонстрировать, как работает каррирование, и показать, что функции (частично применённые) – это настоящие значения, которые можно передавать в другие функции или помещать в списки (но нельзя представлять в виде строк). До сих пор мы применяли к спискам только функции с одним параметром, вроде map (*2) [0..], чтобы получить список типа (Num a) => [a], но с тем же успехом можем использовать (*) [0..] безо всяких проблем. При этом числа в списке будут применены к функции *, тип которой (Num a) => a –> a –> a. Применение только одного параметра к функции двух параметров возвращает функцию одного параметра. Применив оператор * к списку [0..], мы получаем список функций, которые принимают только один параметр, а именно (Num a) => [a –> a]. Список, возвращаемый выражением map (*) [0..], также можно получить, записав [(0*),(1*),(2*),(3*),(4*),(5*)…

ghci> let listOfFuns = map (*) [0..]

ghci> (listOfFuns !! 4) 5

20

Элемент с номером четыре из списка содержит функцию, которая выполняет умножение на четыре – (4*). Затем мы применяем значение 5 к этой функции. Это то же самое, что записать (4*) 5 или просто 4 * 5.

Лямбда-выражения

Лямбда-выражения – это анонимные функции, которые используются, если некоторая функция нужна нам только однажды. Как правило, мы создаём анонимные функции с единственной целью: передать их функции высшего порядка в качестве параметра. Чтобы записать лямбда-выражение, пишем символ \ (напоминающий, если хорошенько напрячь воображение, греческую букву лямбда – λ), затем записываем параметры, разделяя их пробелами. Далее пишем знак –> и тело функции. Обычно мы заключаем лямбду в круглые скобки, иначе она продолжится до конца строки вправо.

Если вы обратитесь к примеру, приведённому в предыдущем разделе, то увидите, что мы создали функцию isLong в секции where функции numLongChains только для того, чтобы передать её в фильтр. Вместо этого можно использовать анонимную функцию:

numLongChains :: Int

numLongChains = length (filter (\xs –> length xs > 15) (map chain [1..100]))

Анонимные функции являются выражениями, поэтому мы можем использовать их таким способом, как в примере. Выражение (\xs –> length xs > 15) возвращает функцию, которая говорит нам, больше ли 15 длина переданного списка.

Те, кто не очень хорошо понимает, как работает каррирование и частичное применение функций, часто используют анонимные функции там, где не следует. Например, выражения map (+3) [1,6,3,2] и map (\x –> x + 3) [1,6,3,2] эквивалентны, так как (+3) и (\x –> x + 3) – это функции, которые добавляют тройку к аргументу. Излишне говорить, что использование анонимной функции в этом случае неоправданно, так как частичное применение значительно легче читается.

Как и обычные функции, лямбда-выражения могут принимать произвольное количество параметров:

ghci> zipWith (\a b –> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]

[153.0,61.5,31.0,15.75,6.6]

По аналогии с обычными функциями, можно выполнять сопоставление с образцом в лямбда-выражениях. Единственное отличие в том, что нельзя определить несколько образцов для одного параметра – например, записать для одного параметра образцы [] и (x: xs) и рассчитывать, что выполнение перейдёт к образцу (x:xs) в случае неудачи с []. Если сопоставление с образцом в анонимной функции заканчивается неудачей, происходит ошибка времени выполнения, так что поосторожнее с этим!

ghci> map (\(a,b) –> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]

[3,8,9,8,7]

Обычно анонимные функции заключаются в круглые скобки, если только мы не хотим, чтобы лямбда-выражение заняло всю строку. Интересная деталь: поскольку все функции каррированы по умолчанию, допустимы две эквивалентные записи.

addThree :: Int -> Int -> Int -> Int