1 Глава 2. Средства функционального программирования Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования Функции высших порядков sqr :: Integer -> Integer sqr x = x * x source = [1, 2, 5, 7, 11] dest = [1, 4, 25, 49, 121] sqr dest = map sqr source map :: (Integer -> Integer) -> [Integer] -> [Integer] map _ [] = [] map f (x:ls) = (f x) : (map f ls) map :: (a -> b) -> [a] -> [b]

2 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Определение функций с помощью λ-выражений λ-исчисление Черча – исчисление безымянных функций sqr : λx.* x x sqr = \x -> (x * x)

3 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Более сложная функция, заданная с помощью λ-выражения factorial :: Integer -> Integer factorial = \n -> case n of 0 -> 1 n -> n * factorial (n-1) Конструкция case – общая форма задания выбора по образцу case expr of patt 1 | cond 11 -> expr 11 | cond 12 -> expr patt 2 | cond 21 -> expr 21 | cond 22 -> expr

4 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Еще один пример функции высшего порядка source = [ ] ,func =seed = (+)0, +, +, += func = (:)seed = [] 1 : (2 : (5 : (7 : (11 : [])))) = [1, 2, 5, 7, 11] foldr :: (a -> b -> b) -> b -> [a] -> b foldr func seed [] = seed foldr func seed (x:ls) = func x (foldr func seed ls)

5 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. С помощью функций высшего порядка можно программировать. factorial :: Integer -> Integer factorial n = foldr (*) 1 [1..n] search :: (Eq a) => a -> [a] -> Bool search e list = foldr (||) False (map (\x -> x == e) list) search 5 [1, 2, 5, 7, 11] foldr (||) False (map (\x -> x == 5) [1, 2, 5, 7, 11]) foldr (||) False [False, False, True, False, False] False || (False || (True || (False || (False || False)))) join1 :: [a] -> [a] -> [a] join1 [] list = list join1 (x:ls) list = x : (join1 ls list) join2 :: [a] -> [a] -> [a] join2 lis1 lis2 = foldr (:) lis2 lis1 True

6 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Еще несколько полезных функций высших порядков. -- "левая вставка" – еще один способ свертки списка foldl :: (b -> a -> b) -> b -> [a] -> b foldl _ seed [] = seed foldl f seed (x:ls) = foldl f (f seed x) ls reverse :: [a] -> [a] reverse list = foldl app [] list where app l x = x:l flip :: (a -> b -> c) -> (b -> a -> c) flip f = flip' where flip' x y = f y x reverse :: [a] -> [a] reverse list = foldl (flip (:)) [] list :: (b -> c) -> (a -> b) -> (a -> c) = fg where fg x = f (g x) sqr :: (Num a) => a -> a sqr a = a * a power4 :: (Num a) => a -> a power4 = comp sqr sqrsqr. sqr comp comp f g (.) f. g

7 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Свертки сложных структур данных. data Tree a = Empty | Node (Tree a) a (Tree a) A BC DEF Правосторонний обход этого дерева: F, C, E, A, B, D Функция, осуществляющая свертку в порядке правостороннего обхода: foldTree :: (a -> b -> b) -> b -> Tree a -> b foldTree _ seed Empty = seed foldTree f seed (Node t1 n t2) = foldTree f (f n (foldTree f seed t2)) t1 t1 = foldTree (++) seed t1 => D ++ (B ++ (A ++ (E ++ (C ++ (F ++ seed))))) «Разглаживание» дерева с помощью foldTree: flatten :: Tree a -> [a] flatten t = foldTree (:) [] t

8 Кубенский А.А. Функциональное программирование. Глава 2. Средства функционального программирования. Сортировка с помощью дерева: используем функции высших порядков. build [] = Empty build (e:ls) = insert e (build ls) flatten Empty = [] flatten (Node t1 n t2) = (flatten t1) ++ (n : (flatten t2)) data Tree a = Empty | Node (Tree a) a (Tree a) sort :: (Ord a) => [a] -> [a] build :: (Ord a) => [a] -> Tree a insert :: (Ord a) => a -> Tree a -> Tree a flatten :: Tree a -> [a] sort ls = flatten (build ls) insert e Empty = Node Empty e Empty insert e (Node t1 n t2) | e < n = Node (insert e t1) n t2 | e >= n = Node t1 n (insert e t2) build list = foldr insert Empty list flatten tree = foldTree (:) [] tree foldTree :: (a -> b -> b) -> b -> Tree a -> b foldTree _ seed Empty = seed foldTree f seed (Node t1 n t2) = foldTree f (f n (foldTree f seed t2)) t1