1 Д.з.

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

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

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

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

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

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

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

Списки списков [[1,2,3],[4,5]] [[]] length [[]] ? 1 – один элемент [] Пример: Сумма всех элементов списка списков sum2 xss = sum (map sum xss) Или sum2 = sum. map sum См. tacit programming, point-free programming 10

map, как цикл 11

Еще пример с 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, как что-то вроде конструкции цикла 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

Карринг 14

В рассказе про частичную параметризацию была странность… Программист 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

Карринг (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

История Моисей Шейнфинкель доклад в Геттигене, 1920 Haskell Curry 17

Основнные стандартные функции высшего порядка. foldr и foldl 18

Основные стандартные функции высшего порядка map map (^2) [1, 2, 3] [1, 4, 9] filter filter условие список filter (>0) [2, -3, 6, -1, 8] [2, 6, 8] foldr и foldl 19

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 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 Способ 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

foldl То же, но слева направо foldl (+) 0 [1,2,3] (((0+1)+2)+3) 23

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

Доп.задача: 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

Просто картинка) Гольдбах пишет письмо Эйлеру, 1742 г. 26

Д.з. 27

Д.з. См. систему тестирования 28