сток, который содержит значение неокоторого типа a. Значение заканчивается пустым списком [].
Мы можем предположить, что функции для списков также будут рекурсивными. Это и правда так. Помот-
рим на три основные функции для списков. Все они определены в Prelude. Начнём с функции преобразования
всех элементов списка:
map :: (a -> b) -> [a] -> [b]
Посмотрим как она работает:
Prelude> map (+100) [1,2,3]
[101,102,103]
Prelude> map not [True, True, False, False, False]
[False, False, True, True, True]
Prelude> :m +Data.Char
Prelude Data.Char> map toUpper ”Hello World”
”HELLO WORLD”
Теперь опишем эту функцию. Базой рекурсии будет случай для пустого списка. В нём мы говорим, что
если элементы закончились, нам нечего больше преобразовывать, и возвращаем пустой список. Во втором
уравнении нам встретится узел дерева, который содержит конструктор :, а в дочерних узлах сидят элемент
списка a и оставшаяся часть списка as. В этом случае мы составляем новый список, элемент которого со-
держит преобразованный элемент (f a) исходного списка и оставшуюся часть списка, которую мы также
преобразуем с помощью функции map:
map :: (a -> b) -> [a] -> [b]
map f []
= []
map f (a:as) = f a : map f as
Какое длинное объяснение для такой короткой функции! Надеюсь, что мне не удалось сбить вас с толку.
Обратите внимание на то, что поскольку конструктор символьный (начинается с двоеточия) мы пишем его
между дочерними поддеревьями, а не сначала. Немного отвлекитесь и поэкспериментируйте с этой функци-
ей в интерпретаторе, она очень важная. Составляйте самые разные списки. Чтобы не перенабирать каждый
раз списки водите синонимы с помощью let.
Перейдём к следующей функции. Это функция фильтрации:
filter :: (a -> Bool) -> [a] -> [a]
Она принимает предикат и список, угдайте что она делает:
Prelude Data.Char> filter isUpper ”Hello World”
”HW”
Prelude Data.Char> filter even [1,2,3,4,5]
[2,4]
Prelude Data.Char> filter (> 10) [1,2,3,4,5]
[]
Да, она оставляет лишь те элементы, на которых предикат вернёт истину. Потренируйтесь и с этой функ-
цией.
Теперь определение:
filter :: (a -> Bool) -> [a] -> [a]
filter p []
= []
filter p (x:xs) = if p x then x : filter p xs else filter p xs
Попробуйте разобраться с ним самостоятельно, по аналогии с map. Оно может показаться немного гро-
моздким, но это ничего, совсем скоро мы узнаем как записать его гораздо проще.
Рассмотрим ещё одну функцию для списков, она называется функцией свёртки:
Рекурсивные типы | 55
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []
= z
foldr f z (a:as) = f a (foldr f z as)
Визуально её действие можно представить как замену всех конструкторов в дереве значения на подхо-
дящие по типу функции. В этой маленькой функции кроется невероятная сила. Посмотрим на несколько
примеров:
Prelude Data.Char> :m -Data.Char
Prelude> let xs = [1,2,3,4,5]
Prelude> foldr (:) [] xs
[1,2,3,4,5]
Мы заменили конструкторы на самих себя и получили исходный список, теперь давайте сделаем что-
нибудь более конструктивное. Например вычислим сумму всех элементов или произведение:
Prelude> foldr (+) 0 xs
15
Prelude> foldr (*) 1 xs
120
Prelude> foldr max (head xs) xs
5
3.6 Краткое содержание
В этой главе мы присмотрелись к типам и узнали как ограничения, общие для всех типов, сказываются
на структуре значений. Мы узнали, что константы в Haskell очень похожи на деревья, а запись констант
– на строчную запись дерева. Также мы присмотрелись к функциям и узнали, что операция определения
синонима состоит из композиции и декомпозиции значений.
name
декомпозиция
=
композиция
Существует несколько правил для построения композиций:
• Одно для функций в префиксной форме записи:
f :: a -> b,
x :: a
——————————-
(f x) :: b
• И два для функций в инфиксной форме записи:
Это левое сечение:
(*) :: a -> (b -> c),
x :: a
———————————
(x *) :: b -> c
И правое сечение:
(*) :: a -> (b -> c),
x :: b
———————————
(* x) :: a -> c
Декомпозиция происходит в аргументах функции. С её помощью мы можем извлечь из составной
константы-дерева какую-нибудь часть или указать на какие константы мы реагируем в данном уравнении.
Ещё мы узнали о частичном применении. О том, что все функции в Haskell являются функциями одного
аргумента, которые возвращают константы или другие функции одного аргумента.
Мы потренировались в составлении неправильных выражений и посмотрели как компилятор на основе
правил применения узнаёт что они неправильные. Мы узнали, что такое ограничение мономорфизма и как
оно появляется. Также мы присмотрелись к рекурсивным функциям.
56 | Глава 3: Типы
Succ
not
Рис. 3.7: Конструкторы и синонимы
3.7 Упражнения
• Составьте в интерпретаторе как можно больше неправильных выражений и посмотрите на сообще-
ния об ошибках. Разберитесь почему выражение оказалось неправильным. Для этого проверьте типы с
помощью правил применения. Составьте несколько выражений, ведущих к ошибке из-за ограничения
мономорфизма.
• Потренируйтесь в интерпретаторе с функциями map, filter и foldr. Попробуйте их с самыми разными