Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
1
1 Д.з.
2
isosc – типичные замечания… 1. Считаем длину: sqrt ((x1-x2)^2 + (y1-y2)^2) sqrt не надо! 2. if (x1-x2)^2 + (y1-y2)^2 == (x1-x3)^2 + (y1-y3)^2 || (x2-x3)^2 + (y2-y3)^2 == (x1-x3)^2 + (y1-y3)^2 … Copy-paste Ввести функцию для x1-x2)^2 + (y1-y2)^2! 3. isosc (x1, y1) (x2, y2) (x3,y3) = if sqrdist (x1, y1) (x2, y2) … Как устроены точки, нам уже не важно! isosc a b c = sqrdist a b ==… Инкапсуляция (encapsulation) 4. isosc a b c = if sqrdist a b == sqrdist b c || sqrdist b c == sqrdist c a || sqrdist c a == sqrdist a b Эффективность Не считать по 2 раза isosc a b c = let ab = sqrdist a b bc = sqrdist b c ac = sqrtdist a c 2
3
isosc – и еще типичные замечания… 5. if ab == ac || ab == bc || ac == bc then True else False "Так пишут индийские программисты" Лучше заменить на ab == ac || ab == bc || ac == bc … then True else False писать никогда не надо 6. … if точки лежат на одной прямой then False … OK Но мне было бы лень проверять) 3
4
isosc - решение sqrdist (x1,y1) (x2,y2) = (x1-x2)^2 + (y1-y2)^2 isosc a b c = let let ab = sqrdist a b bc = sqrdist b c ac = sqrtdist a c in ab == ac || ab == bc || ac == bc 4
5
cubeList cubeList 3 [(1,1), (2,8), (3,27)] cubeList n = map (\i->(i,i^3)) [1..n] или cobeList n = zip [1..n] (map (^3) [1..n]) 5
![cubeList cubeList 3 [(1,1), (2,8), (3,27)] cubeList n = map (\i->(i,i^3)) [1..n] или cobeList n = zip [1..n] (map (^3) [1..n]) 5](http://images.myshared.ru/6/698850/slide_5.jpg "cubeList cubeList 3 [(1,1), (2,8), (3,27)] cubeList n = map (\i->(i,i^3)) [1..n] или cobeList n = zip [1..n] (map (^3) [1..n]) 5")
6
minSum [5, 2, 3, 8] | zip [5,2,3,8] [2,3,8] | zip [5,2,3] [2,3,8] | zip xs (tail xs) v [(5,2), (2,3), (3,8)] | map (\(x,y)->x+y) v [7, 5, 11] | minimum v 5 minSum xs = let pairs = zip xs (tail xs) sums = map (\(x,y)->x+y) pairs in minimum sums или, короче, minSum = minimum map (\(x,y)->x+y) (zip xs (tail xs)) 6
![minSum [5, 2, 3, 8] | zip [5,2,3,8] [2,3,8] | zip [5,2,3] [2,3,8] | zip xs (tail xs) v [(5,2), (2,3), (3,8)] | map (\(x,y)->x+y) v [7, 5, 11] | minimum v 5 minSum xs = let pairs = zip xs (tail xs) sums = map (\(x,y)->x+y) pairs in minimum sums или, к](http://images.myshared.ru/6/698850/slide_6.jpg "minSum [5, 2, 3, 8] | zip [5,2,3,8] [2,3,8] | zip [5,2,3] [2,3,8] | zip xs (tail xs) v [(5,2), (2,3), (3,8)] | map (\(x,y)->x+y) v [7, 5, 11] | minimum v 5 minSum xs = let pairs = zip xs (tail xs) sums = map (\(x,y)->x+y) pairs in minimum sums или, к")
7
height Рекурсивный случай height (Node _ l r) = let hl = height l hr = height r in max hl hr + 1 или height (Node _ l r) = max (height l) (heigth r) + 1 Нерекурсивный случай height Empty = -1 7
8
Разные небольшие темы 8
9 trace, show import Debug.Trace … trace строка значение … Возвращает значение Печатает строку Пример: height Empty = show "!!!" (-1) show show 66 "66" Не требует import, есть почти для всех обьектов show [1,2,3] "[1,2,3]" Пример trace + show: fact i = trace (show i) i * fact (i-1) 9
10
Списки списков [[1,2,3],[4,5]] [[]] length [[]] ? 1 – один элемент [] Пример: Сумма всех элементов списка списков sum2 xss = sum (map sum xss) Или sum2 = sum. map sum См. tacit programming, point-free programming 10
![Списки списков [[1,2,3],[4,5]] [[]] length [[]] ? 1 – один элемент [] Пример: Сумма всех элементов списка списков sum2 xss = sum (map sum xss) Или sum2 = sum. map sum См. tacit programming, point-free programming 10](http://images.myshared.ru/6/698850/slide_10.jpg "Списки списков [[1,2,3],[4,5]] [[]] length [[]] ? 1 – один элемент [] Пример: Сумма всех элементов списка списков sum2 xss = sum (map sum xss) Или sum2 = sum. map sum См. tacit programming, point-free programming 10")
11
map, как цикл 11
12
Еще пример с map f n [1,0,1,0,1,…] (n раз) Вариант 1 – рекурсия f n = f n 1 f n x, где x – очередной элемент f' 0 _ = [] f n 1 = 1 : f (n-1) 0 f n 0 = 0 : f (n-1) 1 или одно правило f n x = x : f (n-1) (1-x) Но нас сейчас больше интересует вариант 2 – c использованием map f n = map (\i -> что-то ) [1..n] что-то – то, что надо сгенерировать для i-того элемента … map (\i -> i `mod` 2) [1..n] 12
![Еще пример с map f n [1,0,1,0,1,…] (n раз) Вариант 1 – рекурсия f n = f n 1 f n x, где x – очередной элемент f' 0 _ = [] f n 1 = 1 : f (n-1) 0 f n 0 = 0 : f (n-1) 1 или одно правило f n x = x : f (n-1) (1-x) Но нас сейчас больше интересует вариант 2](http://images.myshared.ru/6/698850/slide_12.jpg "Еще пример с map f n [1,0,1,0,1,…] (n раз) Вариант 1 – рекурсия f n = f n 1 f n x, где x – очередной элемент f' 0 _ = [] f n 1 = 1 : f (n-1) 0 f n 0 = 0 : f (n-1) 1 или одно правило f n x = x : f (n-1) (1-x) Но нас сейчас больше интересует вариант 2")
что-то ) s У У р р a a ? ! f s = map (\c -> if c == '?' then '!' else " title="map, как что-то вроде конструкции цикла map – это примерно как for (int i = 0; i < n; i++) { что-то } Еще пример: В строке s заменить все '?' на '!' "Ура?" "Ура!" f s = map (\c -> что-то ) s У У р р a a ? ! f s = map (\c -> if c == '?' then '!' else " class="link_thumb">
13
map, как что-то вроде конструкции цикла map – это примерно как for (int i = 0; i < n; i++) { что-то } Еще пример: В строке s заменить все '?' на '!' "Ура?" "Ура!" f s = map (\c -> что-то ) s У У р р a a ? ! f s = map (\c -> if c == '?' then '!' else c) s 13
что-то ) s У У р р a a ? ! f s = map (\c -> if c == '?' then '!' else ">
что-то ) s У У р р a a ? ! f s = map (\c -> if c == '?' then '!' else c) s 13">
что-то ) s У У р р a a ? ! f s = map (\c -> if c == '?' then '!' else " title="map, как что-то вроде конструкции цикла map – это примерно как for (int i = 0; i < n; i++) { что-то } Еще пример: В строке s заменить все '?' на '!' "Ура?" "Ура!" f s = map (\c -> что-то ) s У У р р a a ? ! f s = map (\c -> if c == '?' then '!' else ">
14
Карринг 14
15
В рассказе про частичную параметризацию была странность… Программист A: f x y = x + y map (f 2) xs -- Увеличить все элементы на 2 ff = f 5 -- ff – функция увеличения -- на 5 k = f k = 12 Программист Б: g x = \y -> x + y map (g 2) xs -- Увеличить все элементы на 2 gg = f 5 -- Сгенерируется и присвоится -- функция увеличения на 5 k = (g 5) 7 -- k = 12 k = g Так тоже можно! -- (Скобки групируются влево) В чем разница??? 15
16
Карринг (currying) Разницы нет) f и g – в точности одна и та же функция! f x y = x + y – сокращенная запись для f x = \y -> x + y У всех функций 1 аргумент Частичная параметризация – это просто вызов функции с параметром Такое представление функции от нескольких переменных - currying Как проверить? xs = [f, g] -- Должно -- компилироваться Пример посложнее: f x y z = x + y*z - сокращение для f x = \y -> \z -> x + y*z Функция, которая возвращает функцию, которая возвращает функцию 16
17
История Моисей Шейнфинкель доклад в Геттигене, 1920 Haskell Curry 17
18
Основнные стандартные функции высшего порядка. foldr и foldl 18
19
Основные стандартные функции высшего порядка map map (^2) [1, 2, 3] [1, 4, 9] filter filter условие список filter (>0) [2, -3, 6, -1, 8] [2, 6, 8] foldr и foldl 19
![Основные стандартные функции высшего порядка map map (^2) [1, 2, 3] [1, 4, 9] filter filter условие список filter (>0) [2, -3, 6, -1, 8] [2, 6, 8] foldr и foldl 19](http://images.myshared.ru/6/698850/slide_19.jpg "Основные стандартные функции высшего порядка map map (^2) [1, 2, 3] [1, 4, 9] filter filter условие список filter (>0) [2, -3, 6, -1, 8] [2, 6, 8] foldr и foldl 19")
20
foldr Сложить все элементы sum [] = 0 sum (x:xs) = x + sum xs Перемножить все элементы product [] = 1 product (x:xs) = x * product xs Можем обобщить? Соединить числа с помощью бинарной операции f foldr f e [] = e foldr f e (x:xs) = f e (foldr f e xs) или foldr f e (x:xs) = e `f` (foldr f e xs) sum xs = foldr (+) 0 xs product xs = foldr (*) 1 xs (бинарный оператор) – пишем, если хотим передавать оператор, как фунцкию В каком-то смысле операция, обратная `f` 20
![foldr Сложить все элементы sum [] = 0 sum (x:xs) = x + sum xs Перемножить все элементы product [] = 1 product (x:xs) = x * product xs Можем обобщить? Соединить числа с помощью бинарной операции f foldr f e [] = e foldr f e (x:xs) = f e (foldr f e xs)](http://images.myshared.ru/6/698850/slide_20.jpg "foldr Сложить все элементы sum [] = 0 sum (x:xs) = x + sum xs Перемножить все элементы product [] = 1 product (x:xs) = x * product xs Можем обобщить? Соединить числа с помощью бинарной операции f foldr f e [] = e foldr f e (x:xs) = f e (foldr f e xs)")
21
Как можно понимать foldr foldr (+) 0 [1,2,3] Способ 1 Выписываем элементы списка Справа приписываем e Пишем оператор f между элементами списка Вычисляем справа налево (1 + (2 + (3 + 0))) Пример: and and xs = foldr (&&) True xs Он же reduce (Python, Lisp, MapReduce), accumulate (C++), Aggregate (C#) Перевод слова fold – сложить лист бумаги 21
![Как можно понимать foldr foldr (+) 0 [1,2,3] Способ 1 Выписываем элементы списка 1 2 3 Справа приписываем e 1 2 3 0 Пишем оператор f между элементами списка 1 + 2 + 3 + 0 Вычисляем справа налево (1 + (2 + (3 + 0))) Пример: and and xs = foldr (&&) Tru](http://images.myshared.ru/6/698850/slide_21.jpg "Как можно понимать foldr foldr (+) 0 [1,2,3] Способ 1 Выписываем элементы списка 1 2 3 Справа приписываем e 1 2 3 0 Пишем оператор f между элементами списка 1 + 2 + 3 + 0 Вычисляем справа налево (1 + (2 + (3 + 0))) Пример: and and xs = foldr (&&) Tru")
22
Как еще можно понимать foldr Способ 2 – то же с деревьями Заменяем [] на e Заменяем : на f Вычисляем то, что получится Способ 3 – как цикл foldr f e xs Как бы: res = e для каждого x - элемента цикла (справа налево) { res = f x res } Например, сумма элементов, больших 0 foldr (\x res -> if x>0 then x+res else res) 0 xs 22
![Как еще можно понимать foldr Способ 2 – то же с деревьями Заменяем [] на e Заменяем : на f Вычисляем то, что получится Способ 3 – как цикл foldr f e xs Как бы: res = e для каждого x - элемента цикла (справа налево) { res = f x res } Например, сумма э](http://images.myshared.ru/6/698850/slide_22.jpg "Как еще можно понимать foldr Способ 2 – то же с деревьями Заменяем [] на e Заменяем : на f Вычисляем то, что получится Способ 3 – как цикл foldr f e xs Как бы: res = e для каждого x - элемента цикла (справа налево) { res = f x res } Например, сумма э")
23
foldl То же, но слева направо foldl (+) 0 [1,2,3] (((0+1)+2)+3) 23
![foldl То же, но слева направо foldl (+) 0 [1,2,3] (((0+1)+2)+3) 23](http://images.myshared.ru/6/698850/slide_23.jpg "foldl То же, но слева направо foldl (+) 0 [1,2,3] (((0+1)+2)+3) 23")
24
Про некоторые доп.задачи 24
25
Доп.задача: g prime n = primeFrom n 2 primeFrom n i = if i*i > n then True else if mod n i == 0 then False else primeFrom n (i+1) Проверять до квадратного корня g n = if mod g 2 == 1 then prime (n-2) else any (\i -> prime i && prime (n-i) ) [2.. div n 2] С нечетными числами все просто Проверять до половины 25
26
Просто картинка) Гольдбах пишет письмо Эйлеру, 1742 г. 26
27
Д.з. 27
28
Д.з. См. систему тестирования 28
Еще похожие презентации в нашем архиве:
![1 Д.з. 2 maxlist Не совсем правильное решение maxlist [x] = x maxlist (x:xs) = if x > maxlist xs then x else maxlist xs maxlist [1..100] – очень долго.](/thumbs/9/927556/big_thumb.jpg "1 Д.з. 2 maxlist Не совсем правильное решение maxlist [x] = x maxlist (x:xs) = if x > maxlist xs then x else maxlist xs maxlist [1..100] – очень долго.")
![1 Д.з.. coins Решение 1 coins n = [[i, k, j] | i<-[0..n], j<-[0..n], k<-[0..n], i*2+j*3+k*5 == n] Решение 2 coins n = [[i, k, j] | i<-[0.. n `div` 2],](/thumbs/6/698856/big_thumb.jpg "1 Д.з.. coins Решение 1 coins n = [[i, k, j] | i<-[0..n], j<-[0..n], k<-[0..n], i*2+j*3+k*5 == n] Решение 2 coins n = [[i, k, j] | i<-[0.. n `div` 2],")
![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.](/thumbs/6/698869/big_thumb.jpg "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.")
