1 Д.з. 2 maxlist Не совсем правильное решение maxlist [x] = x maxlist (x:xs) = if x > maxlist xs then x else maxlist xs maxlist [1..100] – очень долго. - презентация

1 1 Д.з.

2 2 maxlist Не совсем правильное решение maxlist [x] = x maxlist (x:xs) = if x > maxlist xs then x else maxlist xs maxlist [1..100] – очень долго Правильное решение 2 maxlist [x] = x maxlist (x:xs) = let m = maxlist xs in if x > m then x else m Правильное решение 3 Используем max maxlist [x] = x maxlist (x:xs) = max x (maxlist xs) 2

3 maxlist – c чего начать? С чего начать? maxlist [x] = x или maxlist [] = очень маленькое число maxlist [] = -1/0 Вам что больше нравится? За maxlist [] = -1/0 В более сложных случаях (например, максимум четных чисел) За maxlist [x] = x Работает не только для чисел maxlist [klm", "abc, "pqr] "pqr" 3

4 sumprod sumprod [_] = 0 sumprod (x:y:xs) = x*y + sumprod (y:xs) 4

5 reverse Вариант 1, используя ++ [x] reverse [] = [] reverse (x:xs) = reverse xs ++ [x] Медленно… Вариант 3, быстрый (O(n)) reverse xs = reverse xs [] reverse [] ys = ys reverse (x:xs) ys = reverse xs (x:ys) Прием: Накапливающий параметр 5

6 Еще про списки length – длина списка length [] = 0 length (_:xs) = 1 + length xs Строки – списки символов "abc" – сокращенная запись для [a, b, c] "abc" ++ "klm" "abcklm" head "abc" 'a' length "abc" 3 6

7 case Просто для тех, кому интересно f xs = 1 + case xs of [x] -> x*x [x, y] -> x+y [] -> 0 x:xs -> -1 7

8 Кортежи 8

9 Кортежи (tuples) (1,2) - пары (3,7,11) – тройки (3, 4, 88, 9) и т.д. Для пар есть встроенные функции fst и snd fst (x, _) = x sdn (_, y) = y Обычно обрабатываем с помощью сопоставления с образцом abs (x, y) = sqrt (x*x+y*y) В чем разница со списками? Значения могут быть разных типов ("Сидоров, 1990, 178, 4.7, True) Нельзя организовать цикл по всем элементам набора 9

10 zip zip – соединить два списка в список пар zip [1,2,3] [33,55,22] [(1,33), (2,55), (3,22)] Разной длины укорачиваем zip (x:xs) (y:ys) = (x,y) : zip xs ys zip [] _ = [] zip _ [] = [] Или zip _ _ = [] 10

11 Pattern binding Пусть функция возвращает пару: areaPerim r = (3.14*r^2, 2*3.14*r) areaPerim 10 (314, 62.8) Как получить результат? fst и snd: let res = areaPerim 10 in fst res / snd res Слева от = м.б. шаблон: let (s, p) = areaPerim 10 in s / p И в лямбда-выражениях: слева от -> могут быть шаблоны map (\(x, y) -> x+y)) xs [(1,2), (3,4)] [3, 7] Похожая вещь в С++: tie tie(s, p) = areaPerim(10); 11

12 Алгебраические типы данных 12

13 Как называются стандартные типы? Integer, Char, Bool, Double Списки [Integer] Строка String – сокращение для [Char] Кортежи (Integer, String) 13

14 data – простой случай. Конструкторы data Point = Pt Integer Integer Pt Похоже на структуры в обычных языках Для доступа к полям – pattern matching abs (Pt x y) = sqrt (x^2+y^2) Можно определить и именованные поля Pt – конструктор Совсем не то, что конструктор в обычных языках Задается в data Может использоваться в pattern matching Начинается с заглавной буквы Имя может совпадать с именем data: data Point = Point Integer Integer 14

15 data c вариантами data Person = Student String Integer Integer | Professor String String Student "Сидоров" Professor "Чижиков" "алгебра" [Student "Сидоров" 5 541, Professor "Чижиков" "алгебра, Student Орлова" 5 545] Пример функции: hello Person -> строка-привествие hello (Student name _ _) = "Привет, " ++ name hello (Professor name _ ) = "Здравстуйте, профессор " ++ name Еще пример: вместо enum: data Suit = Spade | Heart | Club | Diamond 15 строка-привествие hello (Student name _ _) = "Привет, " ++ name hello (Professor name _ ) = "Здравстуйте, профессор " ++ name Еще пример: вместо enum: data Suit = Spade | Heart | Club | Diamond 15">

16 data c рекурсивным определением data Tree = Empty | Node Integer Tree Tree Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty) 1 / \ 2 3 Пример: сумма sumTree Empty = 0 sumTree (Node val l r) = val + sumTree l + sumTree r Кстати: deriving Show data Tree = Empty | Node Integer Tree Tree deriving Show data Point = Pt Integer Integer deriving Show чтобы можно было печатать 16

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

18 check check cond [] = False check cond (x:xs) = if cond x then True else check cond xs Примеры вызова: check (\x -> x > 100) xs mycond x = x >100 check mycond xs check mycond xs where mycond x = x > 100 Еще вариант check cond [] = False check cond (x:xs) = cond x || check cond xs 18

19 Стандартные функции all и any any - проверить, что хотя бы один элемент удовлетворяет условию any (\x->x>0) [5,-1,8] True all – проверить, что все элементы удовлетворяют условию all (\x->x>0) [5,-1,8] False 19

20 checkSum checkSum [] = False checkSum (x:xs) = if в xs есть элемент y: y+x==10 then True else checkSum xs в xs есть элемент y: y+x==10 check (\y-> x+y == 10) xs Или any(\y->x+y==10) checkSum(x:xs) = if any(\y->x+y==10) xs then True else checkSum xs Стиль Haskell!! (использовать функции высшего порядка) Еще вариант, без if checkSum (x:xs) = any (\y->x+y==10) xs || checkSum xs Более эффективное решение? N Log N отсортировать и… 20

21 Частичная параметризация и секции 21

22 Частичная параметризация Задача 1: Написать функцию для вычисления квадратного трехчлена f a b с x = a*x^2 + b*x + c Задача 2: Ко всем элементам списка применить функцию x^2+2*x+4 Простой способ: map (\x -> f x) xs Частичная параметрзация map (f 1 2 4) xs Можно задавать часть параметров (только несколько первых) Получается функция от оставшихся параметров f – функция от x f 1 2 – функция от с и x f 1 – функция от b, c и x Можно использовать при определении функции f1 = f

23 section Частичная параметризация для бинарных операторов (+2) – сокращение для \x -> x+2 (>0) - сокращение для \x -> x>0 Можно задавать любой параметр (2^) - сокращение для \x -> 2^x Можно использовать переменные и выражения: (+a) (+sin y) Может быть `имя_функции` (`div`10) Еще вариант checkSum checkSum(x:xs) = not any(== 10-x) xs && checkSum xs 23

24 Функция, как результат 24

25 Функция, как результат Пусть нам нужны функции вида f x = a*x+b Опишем функцию, которая генерирует такие функции linFunc a b = f where f x = a*x+b или linFunc a b = \x -> a*x+b Пример вызова: map (linFunc 3 2) xs Применяет функцию \x ->3*x+2 ко всем элементам 25

26 Еще немного про типы данных 26

27 Полиморфные алгебраические типы данных Point: точки могут быть целые, вещественные и т.д. Pt Pt data Point a = Pt a a В дереве могут храниться целые, вещественные, символы и т.д. data Tree a = Empty | Node a (Tree a) (Tree a) Node 1 (Node 2 Empty Empty) Empty Node a (Node b Empty Empty) Empty а – имя переменной В принципе, может быть любым 27