Функции высших порядков (функционалы).
Функции высших порядков
Способы определения функций
Анонимные функции (лямбда-абстракция)
Применение функций
Функция map
Примеры использования map
Примеры использования map
Пример. Определение собственной функции высшего порядка
Пример. Собственная функция map2
Абстракции для возвращающихся функциональных значений
Абстракции для возвращающихся функциональных значений
Упрощение функций
Функция filter
Пример с использованием filter
Пример: Разбиение списка на два, в зависимости от заданного условия
Функионалы foldl, foldr (свертка списка)
Функионалы foldl, foldr (примеры и разница в работе)
Функионалы foldl, foldr (примеры и разница в работе)
Функионалы foldl, foldr (примеры и разница в работе)
Функионалы foldl, foldr (примеры и разница в работе)
Функция zipWith
Пример использования функции zipWith
Некоторые дополнительные функции работы со списками
Некоторые дополнительные функции работы со списками
Некоторые дополнительные функции работы со списками
Встроенные функционалы. Разбиение списка по условию
Встроенные функционалы. Существование элемента списка
184.50K
Category: programmingprogramming

Функции высших порядков (функционалы). Лекция 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
English     Русский Rules