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.