Про сложные задачи с коротким решением В д.з. иногда встречаются задачки, у которых есть короткое решение, додуматься до которого не так и просто. А решений, - презентация

1 Про сложные задачи с коротким решением В д.з. иногда встречаются задачки, у которых есть короткое решение, додуматься до которого не так и просто. А решений, бывает, присылают много. В таких случаях мнительные преподаватели начинают подозревать участников курса в том, что они списали решение (ну или по крайней мере, что они позаимствовали идею решения). Особенно подозрения усиливаются, если у задачи есть несколько коротких решений, и почти все присылают одно их них. Вот, такие подозрения иногда закрадываются по поводу задач 9.5 (про repeatFunc) и 10.2 (про myReverse). Хотя да, м.б. это просто мнительность. Поэтому, наверное, было бы правильно ввести следующее правило: Людей, которые решили задачи 9.5 или 10.2, я, может быть, попрошу на зачете воспроизвести и/или обьяснить их решения. Не точно, но очень может быть, что попрошу. Будьте, пожалуйста, морально готовы. Замечания: Может случиться, что и еще про какие-то задачи будет введено это правило. Мораль, которую хотелось бы донести: «Мне кажется, нет смысла списывать сложные задачи». Потому что, если вы будете решать только простые задачи, вы наберете вполне достаточно баллов, чтобы получить зачет без проблем. А если вы списываете задачу у вас в плюсе 1 балл, и в минусе – возможность сложного доп.вопроса. Наверное, нет смысла. Еще одна мораль: Подумать и что-то придумать – это же интересно (мне кажется)! Попробуйте! Если есть желание решить задачу, но нет идей, напишите, я могу подсказать. 1

2 2 Д.з.

3 identity [[1,0,0],[0,1,0],[0,0,1]] Тоже прием с map: map (\i -> … список в зависимости от i…) [1..n] список в зависимости от i = 1 [1,0,0] 2 [0,1,0] 3 [0,0,1] Т.е. нам надо написать: список в зависимости от i = список, в которой на i-том месте 1, а на остальных 0 Еще раз прием с map! список в зависимости от i = map (\j -> … элемент в зависимости от j…) [1..n] Остается придумать формулу: элемент в зависимости от j = if j == i then 1 else 0 И, все вместе: map (\i -> map (\j -> if j == i then 1 else 0 ) [1..n] 3

4 identity - продолжение Похоже на обычный язык? for (int i = 0; i < n; i++) if (i == j) добавить 1 else добавить 0 Еще пример: треугольная матрица из 1 [[1,0,0], [1,1,0], [1,1,1]] Схема та же, просто подбираем другую формулу map (\i -> map (\j -> if j

5 Еще пример – матрица из всех 1 Еще пример: все 1 [[1,1,1], [1,1,1], [1,1,1]] Решение 1: та же схема map (\i -> map (\j -> 1) [1..n] ) [1..n] const c – функция, которая всегда возвращает c const c = \ _ -> c Можно сократить, используя const: map (\i -> map (const 1) [1..n] ) [1..n] А как еще сократить? map (const 1) [1..n] – тоже константа! map (const (map (const 1) [1..n]) ) [1..n] Тоже стиль ФП – коротко и непонятно) Карри бы понравилось Кстати, одна их трех функций Карри – K – это const 5

6 countOdd count xs = foldr (\i res -> if mod i 2 == 1 then i+1 else i) 0 xs Еще варианты: count xs = foldr (\i res -> res + mod i 2) 0 xs count = foldr (\i res -> res + mod i 2) 0 Можно применить карринг count = foldr (\i -> (+ mod i 2)) 0 Можно еще применть карринг и section 6

7 countOdd1 count1 xs = length ( filter (\i -> mod i 2 == 1) xs) count1 xs = length ( filter odd xs ) odd – стандартная функция count1 xs = sum (map (`mod` 2) xs) Еще варианты (карринг, point-free programming): count1 = length. filter odd count1 = sum. map (`mod` 2) 7

8 myFoldl foldl f e [x1,x2,x3] = (((e `f` x1) `f` x2) `f` x3) (((e `f` x1) `f` x2) `f` x3) | e1 = e `f` x1 v (( e1 `f` x2) `f` x3) | V foldl f e1 [x2,x3] Т.е.выразили foldl через foldl от хвоста списка foldl f e (x:xs) = let e1 = e `f` x in foldl f e1 xs или, короче, foldl f e (x:xs) = foldl f (e `f` x) xs Замечания: Аргументы f в другом порядке, чем в foldr Что можно сказать про foldl? Хвостовая рекурсия e – накапливающий параметр 8

9 repeatFunc repeatFunc f n = f.f.f ….f - n раз полезно 'забыть' про смысл оператора (.) repeatFunc f n = f. repeatFunc f (n-1) Нерекурсивный случай repeatFunc f 1 = f repeatFunc f 0 = ? \x -> x id – тождественное отображение id x = x Все вместе: repeatFunc f 0 = id repeatFunc f n = f. repeatFunc f (n-1) 9

10 repeatFunc через стандартные функции [1..n] |map (\_ -> f) | или map (const f) V [f,f, …,f] – n раз | | foldr (.) id | f.f. ….f.id V f.f. ….f - n раз И тут удобно использовать const Все вместе: repeatFunc n = foldr (.) id (map (const f) [1..n]) Вы понимаете китайскую грамоту! 10

11 minHeight. / \.. / / \... / \ \... Доп. параметр: lim – глубже не заходить minHeight t = minHeight' t (1/0) minHeight (Node _ Empty Empty) _ = 0 minHeight (Node _ l r) lim = if lim == 0 then 0 -- Отсекаем! else let hl = minHeight' l (lim-1) hr = minHeight' r hl -- передаем lim!! in hr+1 minHeight Empty lim = lim 11

12 Разное 12

13 Замечание про карринг в обычных языках Карринг – это примерно то, что в обычных языках делают с многомерными массивами a. Можно задать массив с 2 индексами int [,] a = new int [3,3] {{1,2,3}, {4,5,6},{7,8,9}}; b. А можно массив массивов int [][] a = new int[] [] {new [] {1,2,3}, new [] {4}, new [] {5,6}}; Переход от a к b - что-то вроде карринга (Массив – в каком-то смысле функция от int, а двумерный массив – функция от двух int) 13

14 Самая выразительная функция? map filter foldr и foldl Все можно выразить через… foldr ! 14

15 Статичесткое/ динамическое связывание 15

16 Что тут получится? a = 5 -- Определяем a res = let f x = x * a res1 = f 10 in let a = 7 -- Переопределяем a in f 10 Что получится? a. 10 * 5 b. 10 * 7 c. Так нельзя писать res = 10*5 значение a запоминается при определении функции статическое связывание res = 10*7 значение a берется при вызове функции динамическое связывание Haskell – статическое связывание ср. referential transparency f 10 всегда должен возвращать одно и то же 16

17 Замыкание (closure) 17

18 Замыкание Снова checkDifferent из д.з. 2 checkDifferent (x:xs) = let f t = t == x in if any f xs then False else checkDifferent xs f – не совсем обычная функция Мы не можем определить ее вне let Содержит переменную x, не локальную в f, но локальную в внешней функции Другими словами: x – глобальная для f, но локальная для checkDifferent Это называется замыкание (closure) 18

19 Почему это важно? Рассмортим воображаемый диалог: Программист В: любитель языка С Программист П: любитель Haskell (или C# и т.д.) П: Мы можем определять функции, у которых параметры – другие функции! Например, any. В: Ну и что, я тоже могу написать что-то типа: bool any(int arr[], bool (*f)(int)) { … } П: Идея! Давай напишем функцию checkDigit: «Проверить, есть ли в списке / массиве число, оканчивающиеся на d и вернуть True или False» 19

20 Почему это важно - продолжение П: OK, вот программа на Haskell: checkDigit d xs = let f x = mod x 10 == d in any f xs В: bool any(int a[], bool (*f)) { … как-то написал … } … У В есть проблемы…: bool checkDigit(int a[], int d) { ??? Как определить f ? ??? Похоже, никак any(a, f); } П победил Мораль: Без замыканий использовать функции высшего порядка не очень удобно 20

21 Замечания Разные определения: Замыкание – это функция, в которой есть нелокальные переменные Замыкание – это функция + ее запомненные нелокальные переменные Структура, где все это хранится В С++ это capture list any_of(v.begin(), v.end(), [d] { return i % 10 == d; }); см. также FUNARG problem / проблема фунарга Peter Landin Придумал: closure синтаксис с отступами (off-side rule) выражение "syntactic sugar" 21

22 List comprehension 22

23 List comprehension (генераторы списков?) примерно как в математике описываются множества S = { x: x R, x > 5 } Примеры: Удобная запись для map [sin x | x

24 List comprehension – еще возможности Декартово произведение [x*y | x

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

26 parts Разбиваем на возрастающие последовательности Все, что нам надо знать – это длины! * * * * * * * * * - Считаем длины возрастающих последовательностей Считаем НОД HOD(3,6,9) == 3 - Получим длину куска

27 parts Разбиваем на куски по лемме Считаем длины (3,1) (2,4) (5,1) Надо взять из каждой пары по числу, чтобы получилась половина = Итого Пункт 3 сводится к задаче о ранце Динамическое программирование Наблюдение: Если следующее число больше предыдущего, это многое определяет меньше предыдущего Лемма: Точно можно сказать, что 4 7 в одной последовательности, а – в другой 27

28 parts2 – сведение к графам А.Кладов Можно обобщить: задача о графах! Вершина графа элемент последовательности Дуга графа числа не могут быть в одной последовательности Задача Можно ли раскрасить граф в 2 цвета, чтобы: дуги не соединяли вершины одного цвета Т.е. должен получиться двудольный граф вершин каждого цвета было одинаковое количество Лемма Компоненту связности можно раскрасить только двумя способами! 28

29 Integral static double Integral(Func f, double a, double b) { double sum = 0; var h = (b - a)/100; for (var x = a + h/2; x < b; x += h) sum += f(x)*h; return sum; } Пример вызова: var result = Integral(x => x*x, 0, 2); Замечание: sum += (f(x)+f(x+h))/2 Два вызова f в цикле – неэффективно… 29

30 Д.з. 30

31 Монетки 5 коп 3 коп 2 коп 31

32 Д.з. Задачи в системе тестирования. 32