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

addStuff :: Int –> Int

addStuff x = let a = (*2) x

                 b = (+10) x

             in a+b

Вы видите, что монада-читатель позволяет нам обрабатывать функции как значения с контекстом. Мы можем действовать так, как будто уже знаем, что вернут функции. Суть в том, что монада-читатель «склеивает» функции в одну, а затем передаёт параметр этой функции всем тем, которые её составляют. Поэтому если у нас есть множество функций, каждой из которых недостаёт всего лишь одного параметра, и в конечном счёте они будут применены к одному и тому же, то мы можем использовать монаду-читатель, чтобы как бы извлечь их будущие результаты. А реализация операции >>= позаботится о том, чтобы всё это сработало.

Вкусные вычисления с состоянием

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

Тем не менее некоторые задачи по своей природе обладают состоянием, поскольку зависят от какого-то состояния, изменяющегося с течением времени. Хотя это не проблема для Haskell, такие вычисления могут быть немного утомительными для моделирования. Вот почему в языке Haskell есть монада State, благодаря которой решение задач с внутренним состоянием становится сущим пустяком – и в то же время остаётся красивым и чистым.

Когда мы разбирались со случайными числами в главе 9, то имели дело с функциями, которые в качестве параметра принимали генератор случайных чисел и возвращали случайное число и новый генератор случайных чисел. Если мы хотели сгенерировать несколько случайных чисел, нам всегда приходилось использовать генератор случайных чисел, который возвращала предыдущая функция вместе со своим результатом. Например, чтобы создать функцию, которая принимает значение типа StdGen и трижды «подбрасывает монету» на основе этого генератора, мы делали следующее:

threeCoins :: StdGen –> (Bool, Bool, Bool)

threeCoins gen =

   let (firstCoin, newGen) = random gen

       (secondCoin, newGen') = random newGen

       (thirdCoin, newGen'') = random newGen'

   in (firstCoin, secondCoin, thirdCoin)

Эта функция принимает генератор gen, а затем вызов random gen возвращает значение типа Bool наряду с новым генератором. Для подбрасывания второй монеты мы используем новый генератор, и т. д.

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

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

Вычисления с состоянием

Чтобы лучше продемонстрировать вычисления с внутренним состоянием, давайте просто возьмём и дадим им тип. Мы скажем, что вычисление с состоянием – это функция, которая принимает некое состояние и возвращает значение вместе с неким новым состоянием. Данная функция имеет следующий тип:

s –> (a, s)

Идентификатор s обозначает тип состояния; a – это результат вычислений с состоянием.

ПРИМЕЧАНИЕ. В большинстве других языков присваивание значения может рассматриваться как вычисление с состоянием. Например, когда мы выполняем выражение x = 5 в императивном языке, как правило, это присваивает переменной x значение 5, и в нём также в качестве выражения будет фигурировать значение 5. Если рассмотреть это действие с функциональной точки зрения, получается нечто вроде функции, принимающей состояние (то есть все переменные, которым ранее были присвоены значения) и возвращающей результат (в данном случае 5) и новое состояние, которое представляло бы собой все предшествующие соответствия переменных значениям плюс переменную с недавно присвоенным значением.

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

Стеки и чебуреки

Предположим, мы хотим смоделировать стек. Стек – это структура данных, которая содержит набор элементов и поддерживает ровно две операции:

• проталкивание элемента в стек (добавляет элемент на верхушку стека);

• выталкивание элемента из стека (удаляет самый верхний элемент из стека).

Для представления нашего стека будем использовать список, «голова» которого действует как вершина стека. Чтобы решить эту задачу, создадим две функции:

• функция pop будет принимать стек, выталкивать один элемент и возвращать его в качестве результата. Кроме того, она возвращает новый стек без вытолкнутого эле мента;

• функция push будет принимать элемент и стек, а затем проталкивать этот элемент в стек. В качестве результата она будет возвращать значение () вместе с новым стеком.

Вот используемые функции:

type Stack = [Int]

pop :: Stack –> (Int, Stack)

pop (x:xs) = (x, xs)

push :: Int –> Stack –> ((), Stack)

push a xs = ((), a:xs)

При проталкивании в стек в качестве результата мы использовали значение (), поскольку проталкивание элемента на вершину стека не несёт какого-либо существенного результирующего значения – его основная задача заключается в изменении стека. Если мы применим только первый параметр функции push, мы получим вычисление с состоянием. Функция pop уже является вычислением с состоянием вследствие своего типа.

Давайте напишем небольшой кусок кода для симуляции стека, используя эти функции. Мы возьмём стек, протолкнём в него значение 3, а затем вытолкнем два элемента просто ради забавы. Вот оно:

stackManip :: Stack –> (Int, Stack)

stackManip stack = let

   ((), newStack1) = push 3 stack

   (a , newStack2) = pop newStack1

   in pop newStack2

Мы принимаем стек, а затем выполняем выражение push 3 stack, что даёт в результате кортеж. Первой частью кортежа является значение (), а второй частью является новый стек, который мы называем newStack1. Затем мы выталкиваем число из newStack1, что даёт в результате число a (равно 3), которое мы протолкнули, и новый стек, названный нами newStack2. Затем мы выталкиваем число из newStack2 и получаем число и новый стек. Мы возвращаем кортеж с этим числом и новым стеком. Давайте попробуем:

ghci> stackManip [5,8,2,1]

(5,[8,2,1])

Результат равен 5, а новый стек – [8,2,1]. Обратите внимание, как функция stackManip сама является вычислением с состоянием. Мы взяли несколько вычислений с состоянием и как бы «склеили» их вместе. Хм-м, звучит знакомо.

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

stackManip = do

   push 3

   a <– pop

   pop

Ла-адно, монада State позволит нам делать именно это!.. С её помощью мы сможем брать вычисления с состоянием, подобные этим, и использовать их без необходимости управлять состоянием вручную.

Монада State

Модуль Control.Monad.State предоставляет тип newtype, который оборачивает вычисления с состоянием. Вот его определение:

newtype State s a = State { runState :: s –> (a, s) }

Тип State s a – это тип вычисления с состоянием, которое манипулирует состоянием типа s и имеет результат типа a.