Приведём в более человеческий вид:
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.