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

ghci> mapM_ putStrLn . fromDiffList . snd . runWriter $ gcdReverse 110 34

Закончили: 2

8 mod 2 = 0

34 mod 8 = 2

110 mod 34 = 8

Мы выполняем вызов выражения gcdReverse 110 34, затем используем функцию runWriter, чтобы развернуть его результат из newtype, потом применяем к нему функцию snd, чтобы просто получить журнал, далее – функцию fromDiffList, чтобы преобразовать его в обычный список, и в заключение выводим его записи на экран.

Чтобы почувствовать, насколько разностные списки могут улучшить вашу производительность, рассмотрите следующую функцию. Она просто в обратном направлении считает от некоторого числа до нуля, но производит записи в журнал в обратном порядке, как функция gcdReverse, чтобы числа в журнале на самом деле считались в прямом направлении.

finalCountDown :: Int –> Writer (DiffList String) ()

finalCountDown 0 = tell (toDiffList ["0"])

finalCountDown x = do

finalCountDown (x-1)

tell (toDiffList [show x])

Если мы передаём ей значение 0, она просто записывает это значение в журнал. Для любого другого числа она сначала вычисляет предшествующее ему число в обратном направлении до 0, а затем добавляет это число в конец журнала. Поэтому если мы применим функцию finalCountDownк значению 100, строка "100"будет идти в журнале последней.

Если вы загрузите эту функцию в интерпретатор GHCi и примените её к большому числу, например к значению 500 000, то увидите, что она быстро начинает счёт от 0и далее:

ghci> mapM_ putStrLn . fromDiffList .snd . runWriter $ finalCountDown 500000

0

1

2

...

Однако если вы измените её, чтобы она использовала обычные списки вместо разностных, например, так:

finalCountDown :: Int –> Writer [String] ()

finalCountDown 0 = tell ["0"]

finalCountDown x = do

finalCountDown (x-1)

tell [show x]

а затем скажете интерпретатору GHCi, чтобы он начал отсчёт:

ghci> mapM_ putStrLn . snd . runWriter $ finalCountDown 500000

вы увидите, что вычисления идут очень медленно.

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

Ну, теперь в вашей голове наверняка засела песня «Final Countdown» группы Europe. Балдейте!

В главе 11 вы видели, что тип функции (–>) rявляется экземпляром класса Functor. Отображение функции gс помощью функции fсоздаёт функцию, которая принимает то же, что и g, применяет к этому g, а затем применяет к результату f. В общем, мы создаём новую функцию, которая похожа на g, только перед возвращением своего результата также применяет к этому результату f. Вот пример:

ghci> let f = (*5)

ghci> let g = (+3)

ghci> (fmap f g) 8

55

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

ghci> let f = (+) <$> (*2) <*> (+10)

ghci> f 3

19

Выражение (+) <$> (*2) <*> (+10)создаёт функцию, которая принимает число, передаёт это число функциям (*2)и (+10), а затем складывает результаты. К примеру, если мы применим эту функцию к 3, она применит к 3и (*2), и (+10), возвращая 6и 13. Затем она вызовет операцию (+)со значениями 6и 13, и результатом станет 19.

Тип функции (–>) rявляется не только функтором и аппликативным функтором, но также и монадой. Как и другие монадические значения, которые вы встречали до сих пор, функцию можно рассматривать как значение с контекстом. Контекстом для функции является то, что это значение ещё не представлено и нам необходимо применить эту функцию к чему-либо, чтобы получить её результат.

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