Изучай Haskell во имя добра!

Когда мы разбирались со случайными числами в главе 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 будет принимать элемент и стек, а затем проталкивать этот элемент в стек. В качестве результата она будет возвращать значение () вместе с новым стеком.

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