1 Д.з. minlist - 1 Большинство решало так: minlist (x:xs) = minlist xs x minlist [] m = m minlist (x:xs) m = if x < m then minlist xs x else minlist xs. - презентация

1 1 Д.з.

2 minlist - 1 Большинство решало так: minlist (x:xs) = minlist xs x minlist [] m = m minlist (x:xs) m = if x < m then minlist xs x else minlist xs m Немного короче minlist (x:xs) m = minlist xs (if x < m then x else m) Еще немного короче min minlist (x:xs) m = minlist xs (min x m) 2

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

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

5 minsum minsum [_] = 1/0 minsum (x:y:xs) = min (x+y) (minsum (y:xs)) 5

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

7 nseq nseq n = nseqFrom 1 n nseqFrom k n = if k*2 >= n then 1 else nseqFrom (k+1) (n-k) + nseqFrom (k+1) n Тест map [1..100] nseq nseqFrom k n – количество последовательностей, в которых все числа >= n nseqFrom 2 16 / \ Содержит 2 Не содержит … nseqFrom nseqFrom

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

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

10 Кортежи 10

11 Кортежи (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) Нельзя организовать цикл по всем элементам набора 11

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

13 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); 13

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

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

16 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 16

17 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 (Lecturer name _ ) = "Здравстуйте, профессор " ++ name Еще пример: вместо enum: data Suit = Spade | Heart | Club | Diamond 17 строка-привествие hello (Student name _ _) = "Привет, " ++ name hello (Lecturer name _ ) = "Здравстуйте, профессор " ++ name Еще пример: вместо enum: data Suit = Spade | Heart | Club | Diamond 17">

18 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 чтобы можно было печатать 18

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

20 check check cond [] = False check cond (x:xs) = if cond x then True else check cond xs Примеры вызова: check (\x -> x * x

21 checkDifferent checkDifferent [] = True checkDifferent (x:xs) = if x содержится в xs then False else checkDifferent xs x содержится в xs: check (\t -> t == x) xs Или any(\t->t==x) checkDifferent (x:xs) = if any(\t -> t == x) xs then False else checkDifferent xs Стиль Haskell!! (использовать функции высшего порядка) Еще вариант, без if checkDifferent (x:xs) = not any (\t -> t == x) xs && checkDifferent xs Более эффективное рещение? N Log N Например, сначала отсортировать 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) Может быть `имя_функции` (`mod`10) Еще вариант checkDifferent checkDifferent (x:xs) = not any(== x) xs && checkDifferent xs 23

24 Функция, как результат Пусть нам нужны функции вида 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 ко всем элементам 24

25 . Полезная функция, которая возвращает функцию композиция f. g sin. cos \x -> sin (cos x) f. g = h where h x = f (g x) или f. g = \x -> f (g x) 25

26 Приложение 1: обозначения цветом Имена стандартных функций, когда они первый раз упоминаются Разная информация просто для тех, кому это интересно, ее точно не будет на зачете 26

27 Приложение 2: Некоторые стандартные функции, которые мы ужe прошли Вычисления для списков length sum product maximum, minimum any Другие операции над списками head tail ++ zip Функции высшего порядка для списков map Разное max min fst snd div, mod sin, cos Вроде ничего не забыл.. Но вы можете, если хотите, использовать и другие функции, если вы про них знаете 27

28 Д.з. 28

29 Д.з Опишите функцию isosc (от слова isosceles - равнобедренный), у которой три параметра - пары целых чисел, и которая возвращает True, если соответствующие точки на плоскости задают равнобедренный треугольник. 2. Используя стандартные функции, описать функцию cubeTable, которая для данного n возвращает список пар чисел (i, i в кубе) для всех i от 1 до n. cubeTable 3 [(1,1), (2,8), (3,27)] 3. Используя стандартные функции, решить задачу про minsum из прошлого д.з. 4. Описать функцию height, которая ищет высоту данного дерева. 29

30 Д.з Пусть в нашей программе мы хотим хранить информацию о товарах в кондитерском магазине. Товары могут быть: - или тортами, и тогда мы храним их название, вес и цену, - или конфетами, и тогда мы храним их название и цену за килограмм. a) Опишите тип данных, позволяющий хранить такую информацию. b) Опишите функцию, которая для данного списка товаров возвращает название самого дорогого торта. 30

31 Про доп.задачи Доп.задача про пары (будет в четверг) У функции два параметра - целые числа a и b. Точно известно, что они взаимно простые. Функция должна вернуть такую пару целых чисел x и y, что a*x + b*y == 1. (Таких пар, конечно, бесконечно много, можно вернуть любую). алгоритм примерно 300 г. д.н.э! Евклид 31