Функции высших порядков (функционалы). Лекция 4

1. Функции высших порядков (функционалы).

Лектор:
доцент каф. АОИ
Салмина Нина
Юрьевна

2. Функции высших порядков

Аргумент, значением которого является
функция, называют функциональным
аргументом , а функцию, имеющую
функциональный аргумент - функционалом.
Различие между понятиями "данные" и " функция",
определяются не на основе их структуры, а в
зависимости от использования.
Если аргумент используется в функции, как объект
участвующий в вычислениях, то это данные.
Если аргумент используется как средство,
определяющее вычисления, то это функция.

3. Способы определения функций

Явное использование аргумента
f x = x*x + 3
Анонимные функции: лямбда-выражения
(лямбда-абстракции)
\x y z -> x * y * z

4. Анонимные функции (лямбда-абстракция)

Тело функции (без имени) может быть записано в любом
месте кода, где ожидается применение функции.
Синтаксис:
\аргумент1 аргумент2 … -> тело
Важно! У функции нет имени, поэтому в ней невозможно
использовать рекурсию!

5. Применение функций

Функция, суммирующая два аргумента:
add :: Integer -> Integer -> Integer
add x y = x + y
Применение функции
add 3 5
эквивалентно (add 3) 5 - функциональная аппликация
левоассоциативна
применение add к одному аргументу возвращает новую
функцию, которая затем применяется ко второму аргументу
P.S. Функция add может быть заменена на эквивалентное
лямбда-выражение: \x y -> x+y

6. Функция map

map :: (a -> b) -> [a] -> [b]
(a -> b) – функциональный аргумент
Функция map применяет функцию (a -> b) к каждому
элементу списка [a], в результате чего возвращается
список [b]
Например:
> map head [ [1, 2, 3], [4, 5, 6], [6, 7, 8] ]
[1, 4, 6]
> map (\x -> x * 2) [4, 7, 2, 9]
[8, 14, 4, 18]

7. Примеры использования map

Написать функцию, которая из списка строк формирует список их
длин. Например: f [“qw”,”asd”,”w”,”zzzz”] [2,3,1,4]
f :: [String] -> [Int]
f x = map length x
Написать функцию, на вход которой подается число N, список
одноместных функций типа Integer -> Integer и список целых чисел S.
Функция должна возвращать список, полученный после применения
N-й функции ко всем элементам списка S
f_map :: Integer -> [(Integer -> Integer)] -> [Integer] -> [Integer]
f_map 1 (x:_) s = map x s
f_map n (x:xs) s = f_map (n-1) xs s
> f_map 2 [(\x -> x-5),succ,fibon] [2,3,12,4]
[3,4,13,5]

8. Примеры использования map

Задание функции преобразования возможно в блоке where, причем
функция может иметь несколько уравнений и даже определение типа:
f :: [Int] -> [Int]
f x = map fact x
where
fact :: Int -> Int
fact 0 = 1
fact n | n > 0 = n * fact (n-1)
> f1_map [2, 5, 3, 1, 0]
[2,120,6,1,1]

9. Пример. Определение собственной функции высшего порядка

Определим функцию, которая применяет другую функцию
следующим образом: 3*f(x+2)
Функция f должна иметь тип Integer -> Integer
newf3f2 :: (Integer -> Integer) -> Integer -> Integer
newf3f2 f x = 3 * f (x + 2)
fff x = x * x + 10
> newf3f2 fff 7
newf3f2 fff 7 => 3*fff(7+2) => 3*(9*9+10) => 273
273
> newf3f2 succ 7
newf3f2 succ 7 => 3*succ(7+2) => 3*(9+1) => 30
30

10. Пример. Собственная функция map2

-- функционал аналогично map, но работающий с двумя
списками. Функциональный аргумент должен работать с
двумя аргументами
map2 :: (a -> a -> a) -> [a] -> [a] -> [a]
map2 _ [ ] _ = [ ]
map2 _ _ [ ] = [ ]
map2 f (x:xs) (y:ys) = (f x y) : (map2 f xs ys)
-- сложение двух списков
ff2 x y = map2 (\a b -> a + b) x y
-- вариант без применения функционала (рекурсия)
s_s :: [Int] -> [Int] -> [Int]
s_s (x:xs) (y:ys) = x+y : s_s xs ys
s_s _ _ = [ ]

11. Абстракции для возвращающихся функциональных значений

Определить функцию, на вход которой подается число n.
Функция должна возвращать другую функцию, которая
производит умножение на n:
multiplyByN :: Integer -> (Integer -> Integer)
multiplyByN n = \x -> n * x
Функцию можно использовать в тех местах, где используются
функции с одним параметром.
Например:
> map (multiplyByN 5) [1, 2, 3]
[5, 10, 15]

12. Абстракции для возвращающихся функциональных значений

Функция, которая возвращает список одноместных функций,
которые прибавляют 1, 2 или 3 к своему аргументу:
add x n = x + n
flist :: [Int -> Int]
flist = map add [1,2,3]
Функция с одним аргументом n, которая создает список
[n+1, n+2, n+3] :
addN :: Int -> [Int]
addN n = map (\f -> f n) flist
> addN 5
[6,7,8]

13. Упрощение функций

вместо двух рассмотренных выше функций (умножить каждый
элемент списка на n) можно записать:
ff n x = map (\y -> y*n) x
Когда имя функции представлено оператором (+, *) мы можем
просто указать спецификацию выполняемой операции,
заключенную в круглые скобки:
ff_u n x = map (*n) x
Если данные конкретизированы, мы можем вообще опустить
описание аргументов (бесточечный стиль):
double = map (*2)
-- удвоить все элементы списка
> double [1,2,3]
[2,4,6]

14. Функция filter

filter :: (a -> Bool) -> [a] -> [a]
(a -> Bool) – функциональный аргумент
Функция filter применяет функцию (a -> Bool) к каждому
элементу списка [a], в результате чего возвращаются
только те элементы, которые отвечают условию.
Например:
> filter even [1, 2, 3, 4, 5]
-- выбор четных элементов
[2, 4]
> filter (\x -> x > 5) [5, 12, 8, 2, 4, 65]
-- выбор элементов > 5
[12, 8, 65]

15. Пример с использованием filter

-- функция выбирает и удваивает нечетные
элементы списка
duplOdd list = map (*2) $ filter odd list map (*2) (filter odd list)
При использовании бесточечного стиля (без
указания аргументов) для указания
последовательности применения функций
используется символ точки (.)
duplOddNew = map (*2) . filter odd
f . g = \x -> f (g x)

16. Пример: Разбиение списка на два, в зависимости от заданного условия

bothFilters :: (a -> Bool) -> [a] -> ([a],[a])
bothFilters p list = (filter p list, filter (not . p) list)
> bothFilters (> 0) [1,2,-3,4,-5]
([1,2,4], [-3,-5])
Есть встроенная функция partition
(преимущество – формирование результата за один
проход):
> import Data.List
> partition (> 0) [1,2,-3,4,-5]
([1,2,4], [-3,-5])

17. Функионалы foldl, foldr (свертка списка)

На вход подаются: функция двух аргументов;
аргумент типа возвращаемой величины функции
(начальное значение);
список:
-- применяет заданную бинарную операцию к элементам списка
-- от начала к концу
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ s [ ] = s
foldl f s (x : xt) = foldl f (f s x) xt
-- от конца к началу
foldr :: (b -> a -> b) -> b -> [a] -> b
foldr _ s [ ] = s
foldr f s (x : xt) = f x (foldr f s xt)

18. Функионалы foldl, foldr (примеры и разница в работе)

-- от начала к концу
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ s [ ] = s
foldl f s (x : xt) = foldl f (f s x) xt
-- от конца к началу
foldr :: (b -> a -> b) -> b -> [a] -> b
foldr _ s [ ] = s
foldr f s (x : xt) = f x (foldr f s xt)
> foldl (+) 0 [1,2,3,4,5]
15
> foldr (+) 0 [1,2,3,4,5]
15

19. Функионалы foldl, foldr (примеры и разница в работе)

-- от начала к концу
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ s [ ] = s
foldl f s (x : xt) = foldl f (f s x) xt
-- от конца к началу
foldr :: (b -> a -> b) -> b -> [a] -> b
foldr _ s [ ] = s
foldr f s (x : xt) = f x (foldr f s xt)
> foldl (-) 20 [1,2,3]
14
> foldr (-) 20 [1,2,3]
-18

20. Функионалы foldl, foldr (примеры и разница в работе)

-- от начала к концу
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ s [ ] = s
foldl f s (x : xt) = foldl f (f s x) xt
-- от конца к началу
foldr :: (b -> a -> b) -> b -> [a] -> b
foldr _ s [ ] = s
foldr f s (x : xt) = f x (foldr f s xt)
> foldl (-) 20 [1,2,3]
14
> foldr (-) 20 [1,2,3]
-18
= 1 – (foldr (-) 20 [2,3])
= 2 – (foldr (-) 20 [3])
= 3 – (foldr (-) 20 [ ])
1 – 19 = -18
2 – (-17) = 19
3 – 20 = -17

21. Функионалы foldl, foldr (примеры и разница в работе)

-- реверсирование списка (foldr работать не будет)
addElem :: [a] -> a -> [a]
addElem list x = x : list
rev1 :: [a] -> [a]
rev1 list = foldl addElem [ ] list
> rev1 [1,2,3]
[3,2,1]
-- вычисление факториала (можно использовать и foldl)
fact :: Integer -> Integer
fact n = foldr (*) 1 [1 .. n]
> fact 5
120

22. Функция zipWith

Последовательно выполняет операцию, заданную первым
функциональным аргументом над элементами двух списков,
формируя третий список (в отличие от нашей функции map2
типы аргументов могут различаться!)
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ _ [ ] = [ ]
zipWith _ [ ] _ = [ ]
zipWith f (x1 : t1) (x2 : t2) = (f x1 x2) : zipWith f t1 t2
Например, формирование последовательности Фибоначи:
fib = 1 : zipWith (+) fib (0 : fib)

23. Пример использования функции zipWith

Написать функцию, на вход которой подается список строк,
которая бы пронумеровывала строки и формировала список
пар: номер – строка
form :: [String] -> [(Integer,String)]
form list = zipWith (\n line -> (n, line) ) [1 ..] list
> form ["petrov", "sidorov", "ivanov"]
[(1,"petrov"),(2,"sidorov"),(3,"ivanov")]

24. Некоторые дополнительные функции работы со списками

> import Data.List
Функция сортировки sort – сортирует элементы
списка. Элементы могут быть любого типа!
*Main Data.List > sort [1,34,7,2]
[1,2,7,34]
*Main Data.List > sort [“qwe”,”asd”,”zxd”,”acr”]
[“acr”,”asd”,”qwe”,”zxd”]
-- сортировка списка кортежей
*Main Data.List> sort [(1,'q'),(3,'a'),(1,'a')]
[(1,'a'),(1,'q'),(3,'a')]

25. Некоторые дополнительные функции работы со списками

> import Data.List
-- работа со множествами
*Main Data.List> union [1,2,3,4] [2,3,5] --объединение
[1,2,3,4,5]
*Main Data.List> intersect [1,2,3,4] [2,3,5] --пересечение
[2,3]
*Main Data.List> [1,2,3,4] \\ [2,3,5] --вычитание
[1,4]

26. Некоторые дополнительные функции работы со списками

> import Data.List
Функция вставки элемента в список insert – вставляет
элемент Х в список ПЕРЕД элементом больше Х. Элементы
могут быть любого типа!
*Main Data.List> insert 4 [1,2,3,5]
[1,2,3,4,5]
*Main Data.List> insert 1 [2,1,3]
[1,2,1,3]
Prelude Data.List> insert "ser" ["asd","zxc"]
["asd","ser","zxc"]
Prelude Data.List> insert (2,'z') [(1,'q'),(3,'a'),(1,'a')]
[(1,'q'),(2,'z'),(3,'a'),(1,'a')]

27. Встроенные функционалы. Разбиение списка по условию

dropWhile – возвращает список с того места, в котором некий
предикат становится ложным
takeWhile – возвращает элементы списка до тех пор, пока предикат
не станет ложным
span – возвращает кортеж из списков, сформированных функциями
takeWhile и dropWhile
Prelude Data.List> takeWhile (<5) [1,2,3,4,5,6,7]
[1,2,3,4]
Prelude Data.List> dropWhile (<5) [1,2,3,4,5,6,7]
[5,6,7]
Prelude Data.List> span (<5) [1,2,3,4,5,6,7]
([1,2,3,4],[5,6,7])
Prelude Data.List> span (<5) [1,6,8,2,3]
([1],[6,8,2,3])

28. Встроенные функционалы. Существование элемента списка

any - существует ли элемент списка,
удовлетворяющий заданному условию
all – все ли элементы списка удовлетворяют
заданному условию
Prelude > any (<5) [1,6,8,2,3]
True
Prelude > all (<5) [1,6,8,2,3]
False