1 Д.з.

coins Решение 1 coins n = [[i, k, j] | i

coins, продолжение Решение 3 coins n = [(i, k, j)| i

coins, продолжение Решение 4 k

Электрические схемы data Scheme = P Scheme Scheme | -- последовательное S Scheme Scheme | -- параллельное R Double -- одиночное сопротивление totalResistance (R x) = x totalResistance (S a b) = totalResistance a + totalResistance b totalResistance (P a b) = 1/ (1/totalResistance a + 1/totalResistance b) Еще вариант: totalResistance (P a b) = totalResistance a * totalResistance b / (totalResistance a + totalResistance b) Вызываем по 2 раза + рекурсия очень неэффективно 5

mymap map f xs = foldr (\x res -> f x: res) [] xs Для каждого элемента списка добавляем f x в результат Или короче map f = foldr (\x res -> f x: res) [] Или еще короче (карринг) map f = foldr (\x -> (f x:)) [] Или совсем уж коротко map f = foldr ((:).f) [] Почему так можно писать: 1. (:) a – это функция список a: список Т.е. если рассматривать (:), как функцию от одной переменной: (:) на вход берет значение и возвращает функцию приписать значение. x f x (f x:) f (:) Т.е. \x -> (f x :) это (:).f 6

transpose – вариант 1 [[1,2,3], [4,5,6], [7,8,9]] v [[2,3], [5,6], [8,9]] v [[2,5,8], [3,6,9]] v [[1,4,7], [2,5,8], [3,6,9]] [1,4,7] Получаем с помощью map head xss [[2,3], [5,6], [8,9]] Получаем с помощью map tail xss Итого: transpose xss = map head xs : traspose (map tail xss) 7

transpose, вариант 1 - продолжение Нерекурсивное правило – для матрицы из одной строки: [[1,2,3]] [[1], [2], [3]] transpose [xs] = [[x] | x

zipWith zipWith – как zip, но соединяет с помощью функции zipWith f [x1,x2,x3] [y1,y2,y3] [f x1 y1, f x2 y2, f x3 y3] 9

transpose – вариант 2 [[1,2,3], (xs:xss) [4,5,6], [7,8,9]] | v xss1 = transpose xss [[4,7], [5,8], [6,9]] | Приписать по одному v элементу [[1,4,7], [2,5,8], [3,6,9]] приписывание первых элементов zipWith (:) xs xss Или можно и без zipWith map (\(x,y)->x:y) (zip xs xss1) 10

transpose, вариант 2, продолжение Итого получается: transpose (xs:xss) = zipWith (:) xs (transpose xss) Нерекурсивное правило то же transpose [xs] = [[x] | x

List comprehension - продолжение 12

Что можно писать в list comprehension? [ выражение | конструкция1, конструкция2, …] Конструкции: генератор (generator) выражение

Еще пример – quicksort qsort [] = [] qsort (x:xs) = qsort [t | x x] Точнее, конечно: qsort (x:xs) = qsort [t | x x] ++ не очень эффективно Tony Hoare Москва, 1960 Если никогда не видели, советую посмотреть – сортировки в танцах 14

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

Замыкание Снова 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) 16

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

Почему это важно - продолжение A: 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); } A победил Мораль: Без замыканий использовать функции высшего порядка не очень удобно 18

Замечания Разные определения: Замыкание – это функция, в которой есть нелокальные переменные Замыкание – это функция + ее запомненные нелокальные переменные Структура, где все это хранится В С++ это capture list any_of(v.begin(), v.end(), [d] { return i % 10 == d; }); 19

Ленивые вычисления 20

Простые примеры x = trace "calculate sin" (sin 5) x calculate sin length [x] 1 (никакой отладочной печати!) x+x*x calculate sin (отладочная печать – 1 раз!) Как так может быть? x sin 5 значения переменных хранятся в виде формул, не вычисленные, пока это не потребуется Когда переменные наконец вычисляются, их значение запоминается (т.е. вычисляются они не больше одного раза) 21

Ленивые вычисления в двух словах Если совсем коротко: если можем не вычислять – откладываем все, что вычислили – запоминаем и больше не вычисляем (В следующий раз – более точно) 22

Частично вычисленные данные xs !! n Получить n-ный элемент xs xs = [trace "calc 1" (sin 1), trace "calc 2" (sin 2), trace "calc 3" (sin 3)] length xs никакой отладочной печати xs !! 1 calc 2 xs !! 2 + (xs !! 2)*(xs !!2) calc 3 Картинка после xs!!1 xs = [,, ] sin sin 3 23

Частично вычисленные данные + рекурсия list n = n: list (n+1) list 10 = [] xs = list 1 Что получится? xs [1,2,3,4,5,6,7,8,9] Но список генерируется постепенно length [xs] xslist 1 head xs xs1 : list 2 xs !! 1 xs 1 : 2: list 3 xs !! 4 xs1 : 2 : 3 : 4 : 5 : list 6 length xs xs1:2:3:4:5:6:7:8:9:[] Или sum xs и т.д. 24

Бесконечные списки Уберем правило list 10 = [] ! list n = n:list (n+1) С точки зрения обычных языков – точно ошибка Все, кроме length xs – работает! xs = list 1 Бесконечный список! Разворачивается по мере необходимости Некоторые операции, конечно, применять нельзя sum length ++ [x] Но многие можно: head tail !! Есть такая стандартная запись xs = [1..] 25

Еще пример Список синусов lsin i = sin i : lsin (i+1) xs = lsin 0 xs !! 2 : : : listSin 3 sin 0 sin Таблица синусов, синусы вычисляются и таблица расширяется по необходимости 26

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

minTree minTree (Node val Empty _) = val minTree (Node _ l r) = minTree l 28

minPosTree minPosTree t = minPosTree t 0 minPosTree (Node val l r) m = if val > 0 then minPosTree l val else minPosTree r m minPosTree Empty m = m 6 / \ -2 8 / \ -3 4 / 29

C# int [] a = new [] { 5, 7, 2, 9 }; a.Any(x => x == 7); 30

Д.з. 31

Д.з. Задачи в системе тестирования Для тестирования задач про бесконечные списки полезно использовать функцию take. take n xs – вернуть первые n элементов списка xs Фотографии и ссылки к доп.задаче, которая будет в четверг: petersburg/id/potajnaia_memorialnaia_doska_(_memorialnaia_doska_v_chest_geor ga_kantora) petersburg/id/potajnaia_memorialnaia_doska_(_memorialnaia_doska_v_chest_geor ga_kantora) 32