мента потока и возвращает поток:
iterate f a = a :& f a :& f (f a) :& f (f (f a)) :& …
Так с помощью этой функции можно создать поток всех чисел Пеано от нуля или постоянный поток:
nats
= iterate Succ Zero
constStream a
= iterate (x -> x) a
Возможно вас удивляет тот факт, что в этом упражнении мы оперируем бесконечными значениями, но
пока мы не будем вдаваться в детали того как это работает, просто попробуйте определить этот модуль и
посмотрите в интерпретаторе, что получится.
Упражнения | 71
Глава 5
Функции высшего порядка
Функцией высшего порядка называют функцию, которая может принимать на вход функции или возвращать
функции в качестве результата. За счёт частичного применения в Haskell все функции, которые принимают
более одного аргумента, являются функциями высшего порядка.
В этой главе мы подробно обсудим способы составления функций, недаром Haskell – функциональный
язык. В Haskell функции являются очень гибким объектом, они позволяют выделять сложные способы ком-
бинирования значений. Часто за счёт развитых средств составления новых функций в Haskell пользователь
определяет лишь базовые функции, получая остальные “на лету” применением двух-трёх операций, это вы-
глядит примерно как (2+3)*5, где вместо чисел стоят базовые функции, а операции + и * составляют новые
функции из простейших.
5.1 Обобщённые функции
В этом разделе мы познакомимся с несколькими функциями, которые принимают одни функции и состав-
ляют по ним другие. Эти функции используются в Haskell очень часто. Все они живут в модуле Data.Function.
Модуль Prelude экспортирует их из этого модуля.
Функция тождества
Начнём с самой простой функции. Это функция id. Она ничего не делает с аргументом, просто возвращает
его:
id :: a -> a
id x = x
Зачем нам может понадобиться такая функция? Сама по себе она бесполезна. Она приобретает ценность
при совместном использовании с другими функциями, поэтому пока мы не будем приводить примеров.
Константная функция
Следующая функция const принимает значение и возвращает постоянную функцию. Эта функция будет
возвращать константу для любого переданного в неё значения:
const :: a -> b -> a
const a _ = a
Функция const является конструктором постоянных функций, так например мы получаем пятёрки на
любой аргумент:
Prelude> let onlyFive = const 5
Prelude> :t onlyFive
onlyFive :: b -> Integer
Prelude> onlyFive ”Hi”
5
Prelude> onlyFive (1,2,3)
5
Prelude> map onlyFive ”abracadabra”
[5,5,5,5,5,5,5,5,5,5,5]
72 | Глава 5: Функции высшего порядка
С её помощью мы можем легко построить и постоянную функцию двух аргументов:
const2 a = const (const a)
Вспомним определение для && :
(&& ) :: Bool -> Bool -> Bool
(&& ) True
x
= x
(&& ) False
_
= False
С помощью функций id и const мы можем сократить число аргументов и уравнений:
(&& ) :: Bool -> Bool -> Bool
(&& ) a = if a then id else (const False)
Также мы можем определить и логическое “или”:
(||) :: Bool -> Bool -> Bool
(||) a = if a then (const True) else id
Функция композиции
Функция композиции принимает две функции и составляет из них последовательное применение функ-
ций:
(. ) :: (b -> c) -> (a -> b) -> a -> c
(. ) f g = x -> f (g x)
Это очень полезная функция. Она позволяет нанизывать функции друг на друга. Мы перехватываем выход
второй функции, сразу подставляем его в первую и возвращаем её выход в качестве результата. Например
перевернём список символов и затем сделаем все буквы заглавными:
Prelude> :m +Data.Char
Prelude Data.Char> (map toUpper . reverse) ”abracadabra”
”ARBADACARBA”
Приведём пример посложнее:
add :: Nat -> Nat -> Nat
add
a
Zero
= a
add
a
(Succ b) = Succ (add a b)
Если мы определим функцию свёртки для Nat, которая будет заменять в значении типа Nat конструкторы
на соответствующие по типу функции:
foldNat :: a -> (a -> a) -> Nat -> a
foldNat zero succ Zero
= zero
foldNat zero succ (Succ b) = succ (foldNat zero succ b)
То мы можем переписать с помощью функции композиции эту функцию так:
add :: Nat -> Nat -> Nat
add = foldNat
id
(Succ . )
Куда делись аргументы? Они выражаются через функции id и (. ). Поведение этой функции лучше про-
иллюстрировать на примере. Пусть у нас есть два числа типа Nat:
two
= Succ (Succ Zero)
three
= Succ (Succ (Succ Zero))
Вычислим
add two three
Вспомним о частичном применении:
Обобщённые функции | 73
add two three
=>
(add two) three
=>
(foldNat id (Succ . ) (Succ (Succ Zero))) three
Теперь функция свёртки заменит все конструкторы Succ на (Succ . ), а конструкторы Zero на id:
=>
((Succ . ) ((Succ . ) id)) three
Что это за монстр?
((Succ . ) ((Succ . ) id))
Функция (Succ . ) это левое сечение операции (. ). Эта функция, которая принимает функции и возвра-
щает функции. Она принимает функцию и навешивает на её выход конструктор Succ. Давайте упростим это
большое выражение с помощью определений функций (. ) и id:
((Succ . ) ((Succ . ) id))
=>
(Succ . ) (x -> Succ (id x))
=>
(Succ . ) (x -> Succ x)
=>
x -> Succ (Succ x)
Теперь нам осталось применить к этой функции наше второе значение: