(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
Как нам быть? Мы можем группировать скобки слева направо: