Рекурсивные типы | 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 являются функциями одного