Учебник по Haskell

Функции высшего порядка

Функцией высшего порядка называют функцию, которая может принимать на вход функции или возвращать

функции в качестве результата. За счёт частичного применения в Haskell все функции, которые принимают

более одного аргумента, являются функциями высшего порядка.

В этой главе мы подробно обсудим способы составления функций, недаром Haskell – функциональный

язык. В Haskell функции являются очень гибким объектом, они позволяют выделять сложные способы ком-

бинирования значений. Часто за счёт развитых средств составления новых функций в Haskell пользователь

определяет лишь базовые функции, получая остальные “на лету” применением двух-трёх операций, это вы-

глядит примерно как (2+3)*5, где вместо чисел стоят базовые функции, а операции + и * составляют новые

функции из простейших.

5.1 Обобщённые функции

В этом разделе мы познакомимся с несколькими функциями, которые принимают одни функции и состав-

ляют по ним другие. Эти функции используются в Haskell очень часто. Все они живут в модуле Data.Function.

Модуль Prelude экспортирует их из этого модуля.

Функция тождества

Начнём с самой простой функции. Это функция id. Она ничего не делает с аргументом, просто возвращает

его:

id :: a -> a

id x = x

Зачем нам может понадобиться такая функция? Сама по себе она бесполезна. Она приобретает ценность

при совместном использовании с другими функциями, поэтому пока мы не будем приводить примеров.

Константная функция

Следующая функция const принимает значение и возвращает постоянную функцию. Эта функция будет

возвращать константу для любого переданного в неё значения:

const :: a -> b -> a

const a _ = a

Функция const является конструктором постоянных функций, так например мы получаем пятёрки на

любой аргумент:

Prelude> let onlyFive = const 5

Prelude> :t onlyFive

onlyFive :: b -> Integer

Prelude> onlyFive ”Hi”

5

Prelude> onlyFive (1,2,3)

5

Prelude> map onlyFive ”abracadabra”

[5,5,5,5,5,5,5,5,5,5,5]

72 | Глава 5: Функции высшего порядка

С её помощью мы можем легко построить и постоянную функцию двух аргументов:

const2 a = const (const a)

Вспомним определение для && :

(&& ) :: Bool -> Bool -> Bool

(&& ) True

x

= x

(&& ) False

_

= False

С помощью функций id и const мы можем сократить число аргументов и уравнений:

(&& ) :: Bool -> Bool -> Bool

(&& ) a = if a then id else (const False)

Также мы можем определить и логическое “или”:

(||) :: Bool -> Bool -> Bool

(||) a = if a then (const True) else id

Функция композиции

Функция композиции принимает две функции и составляет из них последовательное применение функ-

ций:

(. ) :: (b -> c) -> (a -> b) -> a -> c

(. ) f g = \x -> f (g x)

Это очень полезная функция. Она позволяет нанизывать функции друг на друга. Мы перехватываем выход

второй функции, сразу подставляем его в первую и возвращаем её выход в качестве результата. Например

перевернём список символов и затем сделаем все буквы заглавными:

Prelude> :m +Data.Char

Prelude Data.Char> (map toUpper . reverse) ”abracadabra”

”ARBADACARBA”

Приведём пример посложнее:

add :: Nat -> Nat -> Nat

add

a

Zero

= a

add

a

(Succ b) = Succ (add a b)

Если мы определим функцию свёртки для Nat, которая будет заменять в значении типа Nat конструкторы

на соответствующие по типу функции:

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))))