Контрольная работа 11 ноября 4 пара, 02 Не надо писать тем, кто наберет >= 50 баллов до 7 ноября включительно Примерно 10 простых задач Накапливающие параметры Работа со списками Списки списков Пары data map foldr Деревья List comprehension 1-2 задачи посложнее Похоже на 20 задач (см. следующий слайд ) Как будет проходить: Приносите студ.билет / пропуск Можно пользоваться любыми материалами (компьютерами, распечатками, книгами и т.д.) Нельзя пользоваться интернетом, телефонами и чьей-либо помощью в любой форме Сдавать можно будет на листке или на любом носителе (флешки и т.д.) По почте посылать будет нельзя Могут быть мелкие синтаксические ошибки 1

Задачи для тех, кто не делает задачи с занятий На сайте выложено 20 задач: Это только для тех, кто набрал меньше 10 баллов Остальные могут посмотреть для подготовки к контрольной Подробнее на сайте 2

3 Д.з.

Еще раз про ленивые функции, возвращающие списки Фактически значения возвращаются по одному, по требованию. Пример: список делителей Задание 1: для данного числа найти список делителей dividers n = [i | i

bigSin Условие переводится в программу почти 1 в 1: «… первый элемент в последовательности sin 1, sin 2, sin 3, sin 4, …, который больше или равен x.» «В последовательности sin 1, sin 2, sin 3, sin 4, …» map sin [1..n] «больше или равен x» filter (>x) «последовательности sin 1, sin 2, sin 3, sin 4, …, который больше или равен x» filter (>x) (map sin [1..n]) «первый элемент» head Все вместе: bigSin x = head (filter (>x) (map sin [1..n])) 5

weekendExpences Отделять выходные дни от будних [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, …] Имя? мне кажется, самое понятное - weekendMask weekendMask = 0:0:0:0:0:1:1:weekendMask или weekendMask = [0,0,0,0,0,1,1] ++weekendMask Все вместе: weekendExpences xs = sum (zipWith (*) xs weekendMask) 6

facts facts = [1!, 2!, 3!, 4!, …] [1!, 2!, 3!, 4!, …] [2, 3, 4, 5, …] |попарно v перемножаем … получится почти исходная последовательность … Составные части: [2..] zipWith (*) Все вместе: facts = 1: zipWith (*) facts [2..] 7

fib Решение из A Gentle introduction to Haskell (откуда взята картинка) fib = 1 : 1 : [ a+b | (a,b)

fib - иллюстрация Почему кролики? См. "числа Фибоначчи" 9

sumPos foldTree f e (Node val l r) = let resl = foldTree f e l resr = foldTree f e r in f val resl resr Или можно короче foldTree f e (Node val l r) = f val (foldTree f e l) (foldTree f e r) foldTree f e Empty = e sumPos = foldTree (\v l r -> if v > 0 then v + l + r else l + r) или sumPos = foldTree (\v l r -> l + r + if v > 0 then v else 0) Типичная ошибка: if l > 0 … if r > 0 … - неправильно (l и r проверять не надо) 10

Еще про ленивые вычисления 11

Сети процессов geom = 1 : map (/2) geom map(/2) можно рассматривать как автомат (вроде того, что на рис.), который принимает не монетки, а числа, и выдает не газировку, а тоже числа. [4, 10, 25, …] map (/2) [4, 10, 25, …] А потом мы числа из этого автомата даем ему самому на вход (и еще число 1 в самом начале) map (/2) 1 12

Еще пример Решето Эратосфена Решето: filter (\t -> t `mod` x == 0) Все вместе: sieve (x:xs) = x: sieve (filter (\t -> t `mod` x != 0) xs) primes = sieve [2..] 13

Что есть в обычном программировании похожее на ленивые вычисления? 14

Программа вычисляет значения, когда ей удобнее буферизация outfile

Идиома Copy-on-write string x = "abc"; string y = x; Вариант 1: Создавать копию строки Вариант 2: Пусть у указывает на ту же строку. +: экономия памяти -: проблемы, если меняем данные y[1] = !'; // x тоже поменяется Вариант 3: Создавать копию сроки при изменении x или y Идиома Copy-on-write Т.е. копируем лениво 16

Частично вычисленные данные – что есть похожее? В C#: IEnumerable + блоки итераторов Генераторы И вообще итераторы (?) public static IEnumerable Sinuses() { for (int i = 0; ; i++) { yield return Math.Sin(i); } } public static IEnumerable PlusMinus() { for (; ;) { yield return 1; yield return -1; } } 17

Еще примеры блоков итераторов public static IEnumerable Roots(double a, double b, double c) { double d = Math.Sqrt(b*b – 4*a*c); yield return (–b - d) / 2 /a; yield return (–b + d) / 2 /a; } Можно и завязывать в узел public static IEnumerable Geom() { yield return 1; foreach(int x in Geom()) { yield return x/2; } } В чем разница по сравнению с Haskell? В Haskell результаты запоминаются 18

Типы 19

Тип функции В Хаскеле у всего есть типы Типы объектов: Integer, Double, Bool, String, (Int, Double), [Int], … Типы функций: тип аргумента -> тип результата sqrt Double -> Double Типы "функций с несколькими параметрами» (а на самом деле в Хаскелле не бывает функций снесколькими параметрами): тип1 -> тип2 -> тип3 -> тип результата mod Integer -> Integer -> Integer 20

Типы полифорфных функций Тип length? [a] -> Integer a – означает 'любой тип' Обычно a, b, c … Еще примеры (++) [a] -> [a] -> [a] (!!) [a] -> Integer -> [a] head [a] -> a fst (a, b) -> a 21

Полиморфные функции высшего порядка filter [a] -> (a->Bool) -> [a] zip [a] -> [b] -> [(a,b)] map [a] -> (a->b) -> [b] 22

Вывод типов 23

Алгоритм Хиндли-Милнера J.R.Hindley Robin Milner Футболка с алгоритмом Хиндли-Милнера: you-understand_tshirt you-understand_tshirt 24

Алгоритм Хиндли-Милнера на примере map f (x:xs) = f x : map f xs map f [] = [] Достаточно правила 1 x1 -> x2 -> x3 Этап 1: Выясняем, что некоторые x на самом деле – сложные типы x1 = (x4->x5) Потому что у f тип x1 и f – это функция (видно из f x) x2 = [x6] Потому что у (x:xs) тип x2 x3 = [x7] Потому что видно, что результат – список (у f x : map f xs тип x3) Т.е. получили: (x4->x5) -> [x6] -> [x7] Этап 2: Выясняем, что некоторые x, на самом деле, совпадают x4 == x6 Потому что у x тип x4 (так как это аргумаент в f x) и тип x6 (видно из того, что у (x:xs) тип [x6]) x5 == x7 Потому что у f x тип x5 (так как это результат f) и тип x7 (видно из того что у f x : map f xs тип [x7]) На что похоже? Унификация в Прологе 25

Про некоторые доп.задачи 26

allLists allLists n k - список из всех списков длины k, которые можно составить из чисел 1..n allLists n 2 = [[x,y] | x

Д.з. 28

Д.з. В системе тестирования 29