Функциональное программирование. Основы (Файлы для подготовки к экзамену), страница 9

Она вызывается в томслучае, если при сопоставлении с образцом в do-нотации произошла48ошибка. По умолчанию эта функция печатает сообщение и завершаетпрограмму, однако в некоторых монадах ее имеет смысл переопределить.Например, для монады Maybe ее определяют следующим образом:fail _ = NothingАналогично для списка:fail _ = []Важным видом монад являются монады состояния.

В начале нашихлекций мы определяли императивные программы как ряд последовательных изменений состояния программы. В императивных языках это состояние присутствует неявно; в функциональных языках его необходимоявно передавать в качестве аргумента функции.Рассмотрим проблему генерации псевдослучайных последовательностей. В компьютере псевдослучайные последовательности генерируютсяс помощью рекуррентных соотношений вида xk = f (xk−1 ), где xk — k-йэлемент последовательности. Примером такого датчика (не очень хорошего), генерирующего вещественные числа в диапазоне от 0 до 1, можетслужить соотношениеxk = {11 · xk−1 + π},где {} — оператор взятия дробной части.В языке Си можно реализовать функцию без аргументов, при каждом вызове возвращающей новое псевдослучайное число.

При этом состояние датчика, представляющее в данное случае предыдущее значение последовательности, можно хранить в глобальной либо в локальнойстатической переменной. В языке Haskell значение функции полностьюопределяется ее аргументами и состояние (предыдущее значение последовательности) необходимо передавать явно. Таким образом, функция,вычисляющая площадь куба со случайными сторонами, запишется следующим образом:random x = frac (pi * x + 11)cube x0 = let x1 = random x0x2 = random x1x3 = random x2 inx1 * x2 * x349Здесь в качестве параметра функции cube выступает начальное значение для генератора, а состояние передается из одного вызова функцииrandom в другой явно.

Здесь легко допустить ошибку, например, как вследующем коде:cube x0 = let x1 = random x0x2 = random x1x3 = random x1 inx1 * x2 * x3В этой программе значения переменных x2 и x3 равны! К счастью,монады могут помочь и в этом случае.Прежде всего, сделаем ряд обобщений. В нашем случае состояниедатчика и его возвращаемого значения совпадают. Однако это не обязательно. Во-первых, датчик может учитывать при вычислении очередного элемента последовательности не только предыдущий элемент, но ипредшествующий ему и т. д. Во-вторых, вообще полезно разделить состояние, передаваемое от одного вызова к другому и возвращаемое значение, поскольку это позволит рассматривать состояние без привязки квозвращаемому значению.

С учетом этих замечаний сделаем следующиеопределения:data State = ... -- Здесь следует определение типа состоянияtype StateT a = State -> (a,State)random :: StateT FloatТип StateT определяет значения, являющиеся преобразователямисостояния, т. е. функциями, которые преобразуют заданное состояниев другое состояние, возвращая при этом некоторое значение. Таким образом, функция random фактически имеет тип State -> (Float,State),т. е. по заданному состоянию она возвращает два значения: очередноепсевдослучайное число и новое состояние.

Функция cube запишетсятаким образом:cube s0 = let (x1,s1) = random s0(x2,s2) = random s1(x3,s3) = random s2 inx1 * x2 * x3Тип StateT можно сделать монадой, если сделать следующие определения:50instance Monad StateT wherest >>= f = \s -> let (x,s1) = st s inf x s1return a = \s -> (a,s)Здесь оператор >>= связывает состояния, передавая их из одного вычисления в другое, а функция return возвращает тривиальный преобразователь состояния: функцию, которая оставляет состояние неизменным ивозвращает указанное значение.

Теперь можно применить do-нотацию:cube :: StateT Floatcube = do x1 <- randomx2 <- randomx3 <- randomreturn (x1 * x2 * x3)Монады состояния важны, поскольку они являются основой для определения операций ввода-вывода в языке Haskell. Ввод-вывод долго был«камнем преткновения» для функциональных языков. Действительно, вних постулируется, что результат функции зависит только от ее аргументов. Однако в этом случае функции не могут производить операцийввода-вывода. Действительно, пусть у нас есть функция getChar, которая по заданному дескриптору файла типа FileHandle возвращаеточередной прочитанный из него символ:getChar :: FileHandle -> CharЭта функция не возвращает одно и то же значения, будучи вызвана с одним и тем же аргументом. Ее результат зависит не только от аргумента,но и от состояния файла, которое меняется каждый раз, как вызываетсяэта функция.Одним из решений этой проблемы будет явная передача этого состояния в функции, осуществляющие ввод-вывод.

Таким образом, каждая изфункций ввода-вывода будет принимать дополнительный параметр типаWorld, описывающим состояние всего внешнего мира, и возвращать, помимо результата, измененное состояние мира. (Разумеется, в реальностинам нет необходимости запоминать все состояние внешнего мира, эта переменная будет фиктивной.) Теперь результат функции зависит толькоот ее параметров. Однако необходимо быть уверенным, что состояниямира используются только один раз: возможность повторно использовать это состояние означало бы, что программа должна запоминать всепредыдущие состояния внешнего окружения, а это совершенно недопустимо, да и не всегда возможно: ведь во внешнее окружение входит втом числе и человек, вводящий символы с клавиатуры!51В некоторых языках (например, Clean) для решения этой проблемы модифицировали систему типов таким образом, что однократностьиспользования переменных типа World проверяется компилятором.

Вязыке Haskell эта проблема решена с использованием монад. Определяется тип IO a, аналогичный нашему типу StateT, только вместотипа State используется World. Определение оператора связывания>>= гарантирует, что это значение не будет использоваться более одного раза. Далее, определяется ряд базовых операций, определенных нанизком уровне, осуществляющих основные операции ввода-вывода: открыть файл, считать символ из файла и т. п.

Важным свойством этихопераций является то, что они возвращают значение типа IO. Например,функция для считывания символа из файла имеет типgetChar :: FileHandle -> IO CharНаконец, вся программа на языке Haskell представляет собой функцию main :: IO (), содержащую последовательность операций вводавывода (их называют действиями). Эта функция неявно передает состояние мира в последовательность действий.Необходимо отметить два важных свойства типа IO. Прежде всего,это абстрактный тип данных: пользователю недоступны конструкторыданных этого типа, невозможно извлечь значение из него без использования монадических конструкций и т.

д. Далее, не существует способа избавиться от этого типа. Любая функция, использующая значение, помеченное конструктором IO, должна возвращать значение, такжепомеченное этим конструктором. Если функция не содержит в своейсигнатуре типа IO, значит, она не выполняет никаких операций вводавывода: это гарантируется системой проверки типов. Таким образом, течасти программы, которые выполняют ввод-вывод, явно отделены от чисто функционального ядра.Использование монад позволяет определить небольшой под-язык врамках языка Haskell и программировать на нем практически в императивном стиле.

Предполагается, что опытный программист способен сохранять «императивную» часть программы небольшой и четко отделятьее от функциональной части.52.