Учебник по Haskell - [37]
на соответствующие по типу функции:
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 очень часто используются бинарные операции для составления функций “на лету”. В этом по-
могает и частичное применение, мы можем в одном выражении применить к функции часть аргументов,
построить из неё новую функцию с помощью какой-нибудь такой бинарной операции и всё это передать в
