на соответствующие по типу функции:
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)
Теперь нам осталось применить к этой функции наше второе значение:
(x -> Succ (Succ x)) three
=>
Succ (Succ three)
=>
Succ (Succ (Succ (Succ (Succ x))))
Так мы получили, что и ожидалось от сложения. За каждый конструктор Succ в первом аргументе мы
добавляем применение Succ к результату, а вместо Zero протаскиваем через id второй аргумент.
Аналогия с числами
С помощью функции композиции мы можем нанизывать друг на друга списки функций. Попробуем в
интерпретаторе:
Prelude> let f = foldr (. ) id [sin, cos, sin, cos, exp, (+1), tan]
Prelude> f 2
0.6330525927559899
Prelude> f 15
0.7978497904127007
Функция foldr заменит в списке каждый конструктор (:) на функцию композиции, а пустой список на
функцию id. В результате получается композиция из всех функций в списке.
Это очень похоже на сложение или умножение чисел в списке. При этом в качестве нуля (для сложения)
или единицы (для умножения) мы используем функцию id. Мы пользуемся тем, что по определению для
любой функции f выполнены тождества:
f
. id
==
f
id . f
==
f
Поэтому мы можем использовать id в качестве накопителя результата композиции, как в случае:
Prelude> foldr (*) 1 [1,2,3,4]
24
Если сравнить (. ) с умножением, то id похоже на единицу, а (const a) на ноль. В самом деле для любой
функции f и любого значения a выполнено тождество:
const a
.
f
== const a
Мы словно умножаем функцию на ноль, делая её вычисление бессмысленным.
74 | Глава 5: Функции высшего порядка
Функция перестановки
Функция перестановки flip принимает функцию двух аргументов и меняет аргументы местами:
flip
:: (a -> b -> c) -> b -> a -> c
flip f x y = f y x
К примеру:
Prelude> foldr (—) 0 [1,2,3,4]
—2
Prelude> foldr (flip (—)) 0 [1,2,3,4]
—10
Иногда это бывает полезно.
Функция on
Функция on (от англ. на) перед применением бинарной функции пропускает аргументы через унарную
функцию:
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
(.*. ) ‘on‘ f = x y -> f x .*. f y
Она часто используется в сочетании с функцией sortBy из модуля Data.List. Эта функция имеет тип:
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
Она сортирует элементы списка согласно некоторой функции упорядочивания f :: (a -> a -> Ordering).
С помощью функции on мы можем легко составить такую функцию на лету:
let xs = [(3, ”John”), (2, ”Jack”), (34, ”Jim”), (100, ”Jenny”), (—3, ”Josh”)]
Prelude> :m +Data.List Data.Function
Prelude Data.List Data.Function>
Prelude Data.List Data.Function> sortBy (compare ‘on‘ fst) xs
[(—3,”Josh”),(2,”Jack”),(3,”John”),(34,”Jim”),(100,”Jenny”)]
Prelude Data.List Data.Function> map fst (sortBy (compare ‘on‘ fst) xs)
[—3,2,3,34,100]
Prelude Data.List Data.Function> map snd (sortBy (compare ‘on‘ fst) xs)
[”Josh”,”Jack”,”John”,”Jim”,”Jenny”]
Мы импортировали в интерпретатор модуль Data.List для функции sortBy а также модуль
Data.Function для функции on. Они не импортируются модулем Prelude.
Выражением (compare ‘on‘ fst) мы составили функцию
a b -> compare (fst a) (fst b)
fst = (a, b) -> a
Тем самым ввели функцию упорядочивания на парах, которая будет сравнивать пары по первому элемен-
ту. Отметим, что аналогичного эффекта можно добиться с помощью функции comparing из модуля Data.Ord.
Функция применения
Ещё одной очень полезной функцией является функция применения ($). Посмотрим на её определение:
($) :: (a -> b) -> a -> b
f $ x
=
f x
На первый взгляд её определение может показаться бессмысленным. Зачем нам специальный знак для
применения, если у нас уже есть пробел? Для ответа на этот вопрос нам придётся познакомиться с приори-
тетом инфиксных операций.
Обобщённые функции | 75
5.2 Приоритет инфиксных операций
В Haskell очень часто используются бинарные операции для составления функций “на лету”. В этом по-
могает и частичное применение, мы можем в одном выражении применить к функции часть аргументов,
построить из неё новую функцию с помощью какой-нибудь такой бинарной операции и всё это передать в
другую функцию!
Для сокращения числа скобок нам понадобится разобраться в понятии приоритета операции. Так напри-
мер в выражении
> 2 + 3 * 10
32
Мы полагаем, что умножение имеет больший приоритет чем сложение и со скобками это выражение
будет выглядеть так:
> 2 + (3 * 10)
32
Фраза “больший приоритет” означает: сначала умножение потом сложение. Мы всегда можем изменить
поведение по умолчанию с помощью скобок:
> (2 + 3) * 10
50
В Haskell приоритет функций складывается из двух понятий: старшинство и ассоциативность. Старшин-
ство определяется числами, они могут быть от 0 до 9. Чем больше это число, тем выше приоритет функций.
Старшинство используется вычислителем для группировки разных операций, например (+) имеет стар-
шинство 6, а (*) имеет старшинство 7. Поэтому интерпретатор сначала ставит скобки вокруг выражения с
(*), а затем вокруг (+). Считается, что обычное префиксное применение имеет высший приоритет 10. Нельзя
задать приоритет выше применения, это значит, что операция “пробел” будет всегда выполняться первой.
Ассоциативность используется для группировки одинаковых операций, например мы видим:
1+2+3+4
Как нам быть? Мы можем группировать скобки слева направо:
((1+2)+3)+4
Или справа налево:
1+(2+(3+4))
Ответ на этот вопрос даёт ассоциативность, она бывает левая и правая. Например операции (+) (—) и (*)
являются лево-ассоциативными, а операция возведения в степень (^) является право-ассоциативной.
1 + 2 + 3 == (1 + 2) + 3
1 ^ 2 ^ 3 ==
1 ^ (2 ^ 3)
Приоритет функции можно узнать в интерпретаторе с помощью команды :i:
*FunNat> :m Prelude
Prelude> :i (+)
class (Eq a, Show a) => Num a where
(+) :: a -> a -> a
…
— Defined in GHC.Num
infixl 6 +
Prelude> :i (*)
class (Eq a, Show a) => Num a where
…
(*) :: a -> a -> a
…
— Defined in GHC.Num
infixl 7 *
Prelude> :i (^)
(^) :: (Num a, Integral b) => a -> b -> a
— Defined in GHC.Real
infixr 8 ^
76 | Глава 5: Функции высшего порядка
