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

Мы можем определить функцию, вычисляющую такую последовательность:iterate f x = x : iterate f (f x)Тогда список приближений можно вычислить так:iterate (next z) a0Здесь iterate — пример функции с «бесконечным» выводом — ноэто не проблема, потому что фактически будет вычислено не больше приближений, чем требуется остальным частям программы. Бесконечность- только потенциальная: это означает, что любое число приближенийможно вычислить, если потребуется, iterate сама по себе не содержит никаких ограничений.Остаток программы — функция within, которая берет допуск и список приближений и, просматривая список, ищет два последовательныхприближения, отличающихся не более чем на данный допуск.within eps (a:b:rest) =if abs(a-b) <= epsthen belse within eps (b : rest)Собирая части, получаем:sqrt a0 eps z = within eps (iterate (next z) a0)36Теперь, когда мы имеем части программы поиска квадратного корня,мы можем попробовать объединить их различными способами.

Одна измодификаций, которую мы могли бы пожелать, заключается в использовании относительной погрешности вместо абсолютной. Она большеподходит как для очень малых чисел (когда различие между последовательными приближениями маленькое), так и для очень больших (приокруглении ошибки могут быть намного большими, чем допуск). Необходимо определить только замену для within:relative eps (a:b:rest) =if abs(a-b) <= eps*abs(b)then belse relative eps (b:rest)Теперь можно определить новую версию sqrtrelativesqrt a0 eps z = relative eps (iterate (next z) a0)Нет необходимости переписывать часть, которая генерирует приближения.Мы повторно использовали iterate при генерации последовательности приближений в вычислениях квадратного корня. Конечно же, можно многократно использовать within и relative в любых численныхалгоритмах, которые генерирует последовательность приближений.Например, запишем алгоритм определения корня функции f методомкасательных.

Если начальное приближение равно x0 , то следующее приближение вычисляется по формуле x1 = x − f (x)/f 0 (x). На языке Haskellэтот алгоритм можно записать следующим образом:root f diff x0 eps = within eps (iterate (next f diff) x0)where next f diff x = x - f x / diff xДля работы этого алгоритма необходимо указать две функции: f, вычисляющая значение функции f и diff, вычисляющую значение f 0 .Например, чтобы найти положительный корень функции f (x) = x2 − 1 сначальным приближением 2, запишем следующее выражение:root f diff 2 0.001 where f x = x^2 - 1diff x = 2*xРезультатом вычисления этого выражения будет число 1.00000004646115.В качестве более сложного примера приведем вычисление корня уравнения cos x = x:root f diff 2 0.001 where f x = cos x - xdiff x = -sin x - 1Результатом будет число 0.739085133219815.378Классы типовКлассы типов предоставляют возможность контроля над перегрузкойтипов.

Класс типов представляет собой некоторое множество типов языка, обладающих общими свойствами.Рассмотрим простой пример: равенство. Существует много типов, длякоторых определено отношение равенства, однако для других типов ононе определено. Например, определение равенства двух функций невозможно с вычислительной точки зрения, однако было бы неплохо проверять на равенство два списка. Рассмотрим определение функции elem,проверяющей, что элемент входит в список:x ‘elem‘ [] = Falsex ‘elem‘ (y:ys) = x == y || (x ‘elem‘ ys)Каков тип этой функции. Интуитивно, он должен иметь вид a -> [a] -> Bool.Однако это подразумевает, что оператор == имеет тип a -> a -> Bool,хотя мы говорили, что он определен не для всех типов. Более того, дажеесли бы он был определен для всех типов, сравнение двух списков сильно отличается от сравнения двух чисел.

В этом смысле, мы ожидаем,что оператор == будет перегружен, чтобы выполнять эти (различные)задачи.Классы типов решают обе эти проблемы. Они позволяют определять,какие типы являются экземплярами каких классов, и предоставлятьопределения ассоциированных с классом операций, перегруженных длякаждого типа. Например, определим класс, содержащий оператор равенства:class Eq a where(==) :: a -> a -> BoolЗдесь Eq — имя определяемого класса, а == — единственная операция,определенная в классе. Это определение можно прочесть следующимобразом: «тип a является экземпляром класса Eq, если для него существует перегруженный оператор ==».Ограничение, гласящее, что тип a должен принадлежать классу Eqзаписывается как Eq a. Таким образом, Eq a выражает ограничение натип и называется контекстом.

Контексты располагаются перед описаниями типов:(==) :: (Eq a) => a -> a -> Bool38Это означает: «для каждого типа a, принадлежащего классу Eq, оператор == имеет тип a -> a -> Bool». Для функции elem ограничениязапишутся аналогично:elem :: (Eq a) => a -> [a] -> BoolЭта запись выражает тот факт, что функция elem определена не длявсех типов, а только для тех, для которых определен оператор равенства.Как указать, какие типы принадлежат классу Eq и определить функции сравнения для этих типов? Это делается с помощью определенияпринадлежности:instance Eq Integer wherex == y = x ‘integerEq‘ yОпределение оператора == называется методом. Функция integerEqсравнивает на равенство два целых числа.

В общем случае в правой части определения допустимо любое выражение, как и при обычном определении функции.При определении принадлежности также можно использовать контекст. Пусть у нас определен рекурсивный тип дерева:data Tree a = Leaf a | Branch (Tree a) (Tree a)Тогда можно определить оператор поэлементного сравнения деревьев:instance (Eq a) => Eq (Tree a) whereLeaf a == Leaf b = a == b(Branch l1 r1) == (Branch l2 r2) = (l1 == l2) && (r1 == r2)_ = _ = FalseВ стандартных библиотеках языка определено много классов типов.В действительности класс Eq несколько больше:class Eq a where(==), (/=) :: a -> a -> Boolx /= y = not (x == y)В классе определены две операции, для равенства и для неравенства.Также здесь демонстрируется использование методов по умолчанию, вданном случае для операции неравенства.

Если метод для какого-либоэкземпляра класса пропущен в определении принадлежности, используется метод, определенный в классе, если он существует.Haskell также поддерживает нотацию расширения класса. Например,мы определяем класс Ord, который наследует все операции класса Eq, икроме того, определяет новые операторы сравнения и функции минимумаи максимума:39class (Eq a) => Ord a where(<), (<=), (>=), (>) :: a -> a -> Boolmax, min :: a -> a -> aБудем говорить, что Eq является суперклассом класса Ord (соответственно, Ord является подклассом Eq).9МонадыПонятие монад является одним из важнейших в языке Haskell. Понимание этой концепции начнем с ряда примеров.Одной из простейших монад является тип Maybe.

Напомним егоопределение:data Maybe a = Nothing | Just aОн используется для возврата результата из функций в случае, еслиэтого результата может и не быть. Например, функция f с сигнатуройf :: a -> Maybe bпринимает значение типа a и возвращает результат типа b (обернутыйв конструктор Just), либо может не вычислить значения и тогда, каксигнал об ошибке, вернет значение Nothing.Типичным примером такого рода функций служат функции для осуществления запроса к базе данных. В случае, если данные, удовлетворяющие критериям запроса, существуют, их следует вернуть; в противномслучае возвращается Nothing.Рассмотрим базу данных, содержащую информацию об адресах людей.

Она устанавливает соответствие между полным именем человекаи его адресом. Для простоты предположим, что имя и адрес задаютсястроками. Тогда базу данных можно описать следующим образом:type AddressDB = [(String,String)]Таким образом, база данных представляет собой список пар, первымкомпонентом которых будет имя, а вторым — адрес. Тогда функцияgetAddress, по заданному имени возвращающая адрес, определяетсятак:getAddress :: AddressDB -> String -> Maybe StringgetAddress [] _ = NothinggetAddress ((name,address):rest) n | n == name = Just address| otherwise = getAddress rest n40Для имен, присутствующих в базе, функция возвращает соответствующий адрес. Если такого имени в базе нет, возвращается Nothing.Пока все выглядит безобидно; проблемы начинаются, когда необходимо осуществлять последовательность запросов.

Предположим, у насесть еще одна база данных, содержащая соответствие между адресамии номерами телефонов:type PhoneDB = [(String,Integer)]Далее, пусть имеется функция getPhone, по адресу возвращающая телефон, реализованная также с помощью типа Maybe. Реализация этойфункции полностью аналогична функции getAddress. Как теперь определить функцию, возвращающую телефон по имени человека?Каков будет тип возвращаемого значения этой функции? Очевидно,что у человека может не оказаться телефона, следовательно, функциядолжна возвращать значение типа Maybe Integer.

Далее, значениеNothing эта функция может вернуть в следующих случаях:1. Указанное имя не содержится в базе адресов.2. Адрес, соответствующий указанному имени, существует, однако онне содержится в базе телефонов.Исходя из этих соображений, функцию getPhoneByName можноопределить так:getPhoneByName :: AddressDB -> PhoneDB -> String -> IntegergetPhoneByName a p n = case (getAddress a n) ofNothing -> NothingJust address -> case (getPhone p address) ofNothing -> NothingJust phone -> Just phoneРазумеется, такой стиль программирования не слишком изящен, кроме того, он провоцирует ошибки.

В случае, когда уровень вложенностизапросов возрастает, растет и объем повторяющегося кода. Как быть?Мудрый программист, всегда стремящийся к повторному использованиюкода, определит вспомогательную функцию, которая отражает использующийся в функции getPhoneByName шаблон связывания функций,возвращающих значение типа Maybe. Назовем эту функцию thenMB (отангл. then maybe — тогда, возможно):thenMB :: Maybe a -> (a -> Maybe b) -> Maybe bthenMB mB f = case mB of41Nothing -> NothingJust a -> f aРассмотрим эту функцию подробнее. Она принимает два аргумента: значение типа Maybe a и функцию, отображающую значение типаa в значение типа Maybe b.

Если первый аргумент содержит значениеNothing, второй аргумент игнорируется. Если же первый аргумент содержит реальное значение, обернутое в конструктор Just, оно извлекается из него и передается в функцию, являющуюся вторым аргументом.Вспоминая, что в языке Haskell лямбда-абстракция записывается в виде\x -> expr, функцию getPhoneByName можно записать так:getPhoneByName a p n =(getAddress a n ‘thenMB‘(\address -> getPhone p address)) ‘thenMB‘ (\phone -> Just phИли, опуская скобки и записывая с более наглядным расположениемкода:getPhoneByName a p n = getAddress a n‘thenMB‘ \address ->getPhone p address ‘thenMB‘ \phone->Just phoneЭту запись следует читать так, будто результат левого аргумента оператора ‘thenMB‘ «присваивается» имени переменной из лямбда-абстракции правого аргумента.Чего мы добились? Мы определили функцию thenMB, комбинирующую вычисления, которые могут либо вернуть результат, либо отказаться его вычислять.