False
С помощью функции fix можно выразить любую рекурсивную функцию. Посмотрим как на примере
функции foldNat, у нас есть рекурсивное определение:
foldNat :: a -> (a -> a) -> Nat -> a
foldNat z
s
Zero
= z
foldNat z
s
(Succ n)
= s (foldNat z s n)
Необходимо привести его к виду:
x = f x
Слева и справа мы видим повторяются выражения foldNat z s, обозначим их за x:
x :: Nat -> a
x Zero
= z
x (Succ n)
= s (x n)
Теперь перенесём первый аргумент в правую часть, сопоставление с образцом превратится в case—
выражение:
x :: Nat -> a
x = nat -> case nat of
Zero
-> z
Succ n
-> s (x n)
В правой части вынесем x из выражения с помощью лямбда функции:
x :: Nat -> a
x = (t -> nat -> case nat of
Zero
-> z
Succ n
-> s (t n)) x
Смотрите мы обозначили вхождение x в выражении справа за t и создали лямбда-функцию с таким ар-
гументом. Так мы вынесли x из выражения.
Получилось, мы пришли к виду комбинатора неподвижной точки:
x :: Nat -> a
x = f x
where f = t -> nat -> case nat of
Zero
-> z
Succ n
-> s (t n)
Приведём в более человеческий вид:
foldNat :: a -> (a -> a) -> (Nat -> a)
foldNat z s = fix f
where f t = nat -> case nat of
Zero
-> z
Succ n
-> s (t n)
Комбинатор неподвижной точки | 83
5.6 Краткое содержание
Основные функции высшего порядка
Мы познакомились с функциями из модуля Data.Function. Их можно разбить на несколько типов:
• Примитивные функции (генераторы функций).
id
= x -> x
const a = _ -> a
• Функции, которые комбинируют функции или функции и значения:
f . g
= x -> f (g x)
f $ x
= f x
(.*. ) ‘on‘ f = x y -> f x .*. f y
• Преобразователи функций, принимают функцию и возвращают функцию:
flip f = x y -> f y x
• Комбинатор неподвижной точки:
fix f = let x = f x
in
x
Приоритет инфиксных операций
Мы узнали о специальном синтаксисе для задания приоритета применения функций в инфиксной форме:
infixl 3 #
infixr 6 ‘op‘
Приоритет складывается из двух частей: старшинства (от 1 до 9) и ассоциативности (бывает левая и
правая). Старшинство определяет распределение скобок между разными функциями:
infixl 6 +
infixl 7 *
1 + 2 * 3 == 1 + (2 * 3)
А ассоциативность – между одинаковыми:
infixl 6 +
infixr 8 ^
1 + 2 + 3 == (1 + 2) + 3
1 ^ 2 ^ 3 ==
1 ^ (2 ^ 3)
Мы узнали, что функции ($) и (. ) стоят на разных концах шкалы приоритетов функций и как этим
пользоваться.
5.7 Упражнения
• Просмотрите написанные вами функции, или функции из примеров. Можно ли их переписать с по-
мощью основных функций высшего порядка? Если да, то перепишите. Попробуйте определить их в
бесточечном стиле.
• В прошлой главе у нас было упражнение о потоках. Сделайте поток экземпляром класса Num. Для этого
поток должен содержать значения из класса Num. Методы из класса Num применяются поэлементно. Так
сложение двух потоков будет выглядеть так:
(a1 :& a2 :& a3 :& … ) + (b1 :& b2 :& b3) ==
==
(a1 + b1 :& a2 + b2 :& a3 + b3 :& … )
84 | Глава 5: Функции высшего порядка
• Определите приоритет инфиксной операции (:& )
так чтобы вам было удобно использовать её в сочетании с арифметическими операциями.
• Рассмотрим такой тип:
data St a b = St (a -> (b, St a b))
Этот тип хранит функцию, которая позволяет преобразовывать потоки значений. Определите функцию
применения:
ap :: St a b -> [a] -> [b]
Она принимает ленту входящих значений и возвращает ленту выходов. Определите для этого
типа несоколько основных функций высшего порядка. Чтобы не возникало конфликта имён с
модулем Data.Function мы не будем его импортировать. Вместо него мы импортируем модуль
Control.Category. Он содержит класс:
class Category cat where
id
:: cat a a
(. ) :: cat b c -> cat a b -> cat a c
Если присмотреться к типам функций, можно понять, что тип-экземпляр cat принимает два параметра.
Совсем как тип функции (a -> b). Формально его можно записать в префиксной форме так (-> ) a b.
Получается, что тип cat это что-то вроде функции. Это некоторые сущности, у которых есть понятия
тождества и композиции.
Для обычных функций экземпляр класса Category уже определён. Но в этом модуле у нас есть ещё и
необычные функции, функции которые преобразуют ленты значений. Функции id и (. ) мы определим,
сделав наш тип St экземпляром класса Category. Также определите постоянный преобразователь. Он
на любой вход возвращает одно и то же число, и преобразователь, который будет накапливать сумму
поступающих на вход значений, по-другому такой преобразователь называют интегратором:
const
:: a -> St b a
integral :: Num a => St a a
• Перепишите с помощью fix несколько стандартных функций для списков. Например map, foldr, foldl,
zip, repeat, cycle, iterate.
Старайтесь найти наиболее краткое выражение, пользуйтесь функциями высшего порядка и частичным
применением. Например рассмотрим функцию repeat:
repeat :: a -> [a]
repeat a = a : repeat a
Запишем с fix:
repeat a = fix $ xs -> a : xs
Заметим, что мы можем избавиться от аргумента xs с помощью сечения:
repeat a = fix (a:)
Но мы можем пойти ещё дальше, если вспомним, что функция двух аргументов (:) является функцией
от одного аргумента (:) :: a -> ([a] -> [a]), которая возвращает функцию одного аргумента:
repeat = fix . (:)
Смотрите в этом выражении мы составили композицию двух функций. Функция (:) примет первый
аргумент и вернёт функцию, как раз то, что и нужно для fix.
Упражнения | 85
Глава 6
Функторы и монады: теория
Мы научились комбинировать функции наиболее общего типа a -> b. В этой главе мы посмотрим на
специальные функции и способы их комбинирования. Cпециальными функциями мы будем называть такие
функции, результат которых имеет некоторую известную нам структуру. Среди них функции, которые могут
вычислить значение или упасть, или функции, которые возвращают сразу несколько вариантов значений.
Для составления таких функций из простейших в Haskell предусмотрено несколько классов типов. Это функ-
торы и монады. Их мы и рассмотрим в этой главе.
6.1 Композиция функций
Центральной функцией этой главы будет функция композиции. Вспомним её определение для функций
общего типа:
(. ) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = x -> f (g x)
Композиция двух функций f и g это такая функция, в которой мы сначала применяем g, а затем f. Для того
чтобы тип функции стал более наглядным, мы определим эту функцию немного по-другому. Мы поменяем
аргументы местами.
(>> ) :: (a -> b) -> (b -> c) -> (a -> c)
f >> g = x -> g (f x)
Мы будем изображать функции кружками, а значения – стрелками (рис. 6.1). Значения словно текут от
узла к узлу по стрелкам. Поскольку тип стрелки выходящей из f совпадает с типом стрелки входящей в g мы
можем соединить их и получить составную функцию (f>> g).
a
f
b
b
g
c
b
a
g
f
c
a
f>>g
c
Рис. 6.1: Композиция функций
86 | Глава 6: Функторы и монады: теория
Класс Category
С помощью операции композиции можно обобщить понятие функции. Для этого существует класс
Category:
class Category cat where
id
:: cat a a
(>> ) :: cat a b -> cat b c -> cat a c
Функция cat это тип с двумя параметрами, в котором выделено специальное значение id, которое остав-
ляет аргумент без изменений. Также мы можем составлять из простых функций сложные с помощью компо-
