Main>parseExpr "1+x"

Add (Const 1) (Var "x")

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

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

Пусть задан список чисел. Необходимо написать две функции, первая из которых возвращает список квадратных корней этих чисел, а вторая — список их логарифмов. Эти функции можно определить так:

sqrtList [] = []

sqrtList (x:xs) = sqrt x : sqrtList xs

logList [] = []

logList (x:xs) = log x : logList xs

В стандартной библиотеке языка определена функция высшего порядка map. Она имеет следующий тип:

map:: (a ->b) -> [a] -> [b]

Ее первым аргументом является функция типа a->b, а вторым аргументом - список значений типа a. Результатом функции будет список значений типа b.

Определим аналогичную функцию map1 и с ее помощью опишем функции sqrtList и logList.

map1 f [] = []

map1 f (x:xs) = f x : map1 f xs

sqrtList lst = map1 sqrt lst

logList lst = map1 log lst

Или, с учетом карринга:

sqrtList = map1 sqrt

logList = map1 log

Другая функция filter по заданному предикату и списку возвращает список тех элементов, которые удовлетворяют предикату:

filter :: (a -> Bool) -> [a] -> [a]

filter p [] = []

filter p (x:xs) | p x = x : filter xs

| otherwise = filter xs

Например, функция, получающая из списка чисел его положительные элементы, определяется так:

getPositive = filter isPositive

isPositive x = x > 0

Более сложным примером являются функции foldr и foldl. Рассмотрим функции, возвращающие сумму и произведение элементов списка:

sumList [] = 0

sumList (x:xs) = x + sumList xs

multList [] = 1

multList (x:xs) = x * multList xs

Функция foldr является их очевидным обобщением:

foldr ::(a->b->b)->b->[a]->b

foldr f z [] =z

foldr f z (x:xs) = f x (foldr f z xs)

Функция foldr принимает в качестве первого аргумента функцию. Ее аргументы могут быть разных типов, но тип результата должен совпадать с типом второго аргумента, в котором задается начальное значение. Третьим аргументом передается список. Функция осуществляет «свертку» списка.

Запишем ее определение с использованием инфиксной нотации:

foldr f z [] =z

foldr f z (x:xs) = x ‘f‘ (foldr f z xs)

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

sumList = foldr (+) 0

multList = foldr (*) 1

Буква r в названии функции foldr показывает правую ассоциативность применяемой функции. Определение функции foldl для лево ассоциативной функции, приведено ниже:

foldl ::(a->b->a)->a->[b]->a

foldlfz[] =z

foldl f z (x:xs) = foldl f (f z x) xs

Для ассоциативных операций, таких как сложение и умножение, функции foldr и foldl эквивалентны, однако если операция не ассоциативна, их результаты будут отличаться:

Main>foldr (-) 0 [1,2,3]

Main>foldl (-) 0 [1,2,3]

-6

В первом случае вычисляется величина 1−(2−(3−0)) = 2, а во втором — ((0 − 1) − 2) − 3= −6.

В стандартной библиотеке определена функция zip. Она преобразует два списка в список пар:

zip :: [a] -> [b] -> [(a,b)]

zip (a:as) (b:bs) = (a,b):zip as bs

zip _ _ = []

Пример применения:

Prelude>zip [1,2,3] [’a’,’b’,’c’]

[(1,’a’),(2,’b’),(3,’c’)]

Prelude>zip [1,2,3] [’a’,’b’,’c’,’d’]

[(1,’a’),(2,’b’),(3,’c’)]

Длина результирующего списка равна длине самого короткого исходного списка.

Обобщением этой функции является функция высшего порядка zipWith, «соединяющая» два списка с помощью указанной функции:

zipWith :: (a->b->c) -> [a]->[b]->[c]

zipWith z (a:as) (b:bs) = z a b : zipWith z as bs

zipWith _ _ _ =[]

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

sumList x y = zipWith (+) x y

или,с учетом карринга:

sumList = zipWith (+)

4.5.1. λ–абстракции

В языке HASKELL, как и в лежащем в его основе лямбда-исчислении, можно определять безымянные функции с помощью конструкции λ–абстракции.

Например, безымянные функции, возводящая свой аргумент в квадрат, прибавляющая единицу и умножающая на два, записывается следующим образом:

\x -> x * x

\x -> x + 1

\x -> 2 * x

Их теперь можно использовать в аргументах функций высших порядков. Например, функции для возведения элементов списка в квадрат и умножения на 2 можно записать так:

squareList lst = map (\x -> x * x) lst

doubleList lst = map (\x -> 2 * x) lst

или,с учетом карринга:

squareList = map (\x -> x * x)

doubleList = map (\x -> 2 * x)

Функция getPositive может быть определена следующим образом:

getPositive = filter (\x -> x > 0)

Можно определять λ–абстракции для нескольких переменных:

\x y -> 2 * x + y

λ–абстракции можно использовать наравне с обычными функциями, например, применять к аргументам:

Main>(\x -> x + 1) 2

Main>(\x -> x * x) 5

Main>(\x-> 2 * x+ y) 1 2

С помощью λ–абстракций можно определять функции. Например, следующие записи полностью эквивалентны

square =\x -> x * x

square x= x* x

4.6. Определение операторов

Бинарные операторы, такие как +, - и т. п. в языке HASKELL являются такими же функциями, как и все остальные, за тем исключением, что для их вызова можно использовать инфиксную нотацию. Если взять бинарный оператор в скобки, то для его вызова можно использовать префиксную нотацию и обращаться с ним, как с обычной функцией. Так, следующие пары записей эквивалентны:

2+2 (+) 2 2

x<y (<) x y

x/= y (/=) x y

Наоборот, любую функцию, принимающую два аргумента, можно использовать в инфиксном стиле. Для этого ее имя нужно окружить обратными кавычками (символ ‘). Например, если определить функцию:

func x y = (x +y)/(x -y)

то ее можно вызывать в следующих видах:

func 5 2 5 ‘func‘ 2

Далее, если в имени функции встречаются только «символы» (не буквы и не цифры), то она автоматически считается инфиксным оператором. При определении ее имя нужно заключать в скобки. Например, определим оператор «приближенно равно», проверяющий, что числа отличаются не более, чем на 0.001:

(~=)x y = abs (x - y)<0.001

Теперь этот оператор можно использовать так же, как и все остальные:

testApproxEq x y = if x ~= y then "equal" else "not equal"

4.6.1. Секции

Функции можно применять частично, т. е. не задавать значение всех аргументов. Например, если функция add определена как

add x y = x + y,

то можно определить функцию inc, увеличивающую свой аргумент на 1 следующим образом:

inc= add 1

Бинарные операторы, как встроенные в язык, так и определенные пользователям, также можно применять лишь к части своих аргументов. Бинарная операция, примененная к одному аргументу, называется секцией. Пример, следующие пары записей эквивалентны:

(x+) \y -> x+y

(+y) \x -> x+y

(+) \xy->x+y

Скобки здесь обязательны. Таким образом, функции add и inc можно определить так:

add = (+)

inc = (+1)

Секции особенно полезны при использовании их в качестве аргументов функций высшего порядка. Функции для получения положительных элементов списка и умножения элементов списка на 2с использованием секций записывается более компактно:

getPositive = filter (>0)

doubleList = map (*2)

4.7. Модули

Программы на языке HASKELL состоят из модулей. Модули служат двум целям — управлению пространствами имен и созданию абстрактных типов данных.

Модули имеют имена, начинающиеся с заглавной буквы. С практической точки зрения модуль представляет собой набор объявлений, начинающийся с ключевого слова module. Приведем пример модуля с именем Tree.