Про контрольную 1

Задача 5 (про data) Пусть в нашей программе мы хотим хранить информацию о телевизионных фильмах. Телевизионная передача может быть либо просто фильмом, либо серией из сериала. Для каждого фильма мы хотим хранить его название и жанр (комедия, триллер и т.д.). Для серии мы хотим хранить название сериала и номер серии. а. Опишите тип данных, позволяющий хранить такую информацию. б. Опишите функцию, которая для данного списка телепередач, определяет, есть ли в нем первая серия какого-нибудь сериала, и возвращает True или False. 2

Задача про data Serial название, номер серии Film название, жанр data TV = Film String Integer | Serial String String [Film "Fantomas" "comedy", Serial "The Big Bang Theory" 1, Serial "Black Books" 20, Film "The Magnificent Seven" "western"] 3

Задача про data - продолжение Вариант 1 containsEpisode1 (Serial _ episode : xs) = if episode == 1 then True else containsEpisode1 xs containsEpisode1 (Film _ _:xs) = containsEpisode1 xs containsEpisode1 [] = False Совет: Два конструктора скорее всего, два правила 4

Задача про data – еще варианты Вариант 2 containsEpisode1 (Serial _ 1 : xs) = True containsEpisode1 (_:xs) = containsEpisode1 xs containsEpisode1 [] = False Вариант 3 – инкапсулируем работу с типом isEpisode – верно ли, что параметр – серия с данным номером? isEpisode n (Serial _ episode) = episode == n isEpisode _ (Film _ _) = False Теперь используем any ! containsEpisode1 xs = any (isEpisode 1) xs 5

Задача 12 – дерево строка Один вариантов формата – префиксная запись Empty "e" Node a Empty Empty "naee" Node a (Node b Empty (Node a Empty Empty)) (Node b Empty Empty) "nabenaeenbee" (В принципе, "n" можно было бы и не писать) Будет как доп.задача 6

Переписывание 2 декабря, 4 пара, 02 Как готовиться? Полезно, мне кажется, решить задач и с контрольной, которые у вас еще остались Желательно самостоятельно) Решения можно взять с собой, может пригодятся) 7

8 Д.з.

allNondivisible прием "представление множества с помощью логической функции" Что тут все-таки требовалось? Вместо списка, в который добавляем элементы – логическая функция, в которую добавляем новые условия [6,10,8,25,3] 1. Сначала проверяем, что не делится для 6 2. Потом проверяем, что не делится для 6 и Потом проверяем, что не делится для 6, 10 и 8 4. Потом проверяем, что не делится для 6, 10, 8 и 25 9

allNondivisible - код allNondivisible xs = allNondivisible' xs (cons True) allNondivisible' [] _ = True allNondivisible' (x:xs) cond = if not (cond x) then False else allNondivisible' xs (\t -> cond t && mod x t /=0 && mod t x /= 0) или можно короче … = cond x && allNondivisible' xs (\t -> cond t && mod x t /=0 && mod t x /= 0) 10

findMajor Найти число больше суммы всех остальных Простая идея: можно сначала сосчитать сумму s всех чисел Тогда условие: x > s – x C помощью maximum findMajor xs = let s = sum xs x = maximum xs in if x > s - x then Just x else Nothing Это, правда не работает для пустого списка С помощью filter findMajor xs = let s = sum xs xs1 = filter (\x -> x > s - x) xs in if xs1 == [] then Nothing else Just (head xs1) 11

findMajor - продожение Написать специальный find find cond [] = Nothing find cond (x:xs) = if cond x then Just x else find cond xs (На самом деле именно это и делает стандартный find в библиотеке Haskell, т.е. его и писать не надо..) findMajor xs = let s = sum xs in find (\x -> x > s - x) xs 12

findInLists Без failure continuation как-то так: искать в первом подсписке if нашли then вернуть то, что нашли else искать в хвосте С использованием failure continuation findInLists cond (xs:xss) err = find cond xs (find cond xs err) findInLists cond [] err = err Обошлись без if! См. также на эту тему: statement.aspx Если не нашли, то…

Continuations (продолжения). Continuation-passing style (CPS) 14

Continuation-passing style Continuation: параметр–функция. Задает, что делать после окончания работы функции failure continuation – вызываем, если функция завершилась не успешно Continuation-passing style (CPS) - вызываем всегда! 15

Continuation-passing style – простой пример Обычная функция: sqr x = x*x CPS sqr_cps x f = f (x*x) Примеры вызова: Сосчитать sin(5*5) sqr_cps 5 sin Сосчитать 5*5 + 1 sqr_cps 5 (+1) Сосчитать 5*5 sqr_cps 5 id Зачем??? Такой фокус… 16

CPS и рекурсия. Пример: факториал Обычная программа fact 0 = 1 fact n = fact (n-1) * n CPS стиль fact_cps 0 f = f 1 fact_cps n f = fact_cps (n-1) f1 where f1 i = f (i *n) Или то же: fact_cps n f = fact_cps (n-1) (\t -> f(t*n)) Или, короче: fact_cps n f = fact_cps (n-1) (f.(*n)) tf = fact_cps 5 id Пример вызова: fact_cps 5 sin sin 120 f – то, что нам надо сделать с n! После вычисления (n-1)! нам надо будет еще умножить на n и вызвать f 17

Как это работает? fact 4 fact 3 fact 2 fact 1 fact 0 1 * 1 * 2 * 3 * 4 fact_cps 4 id fact_cps 3 id.(*4) fact_cps 2 id.(*4).(*3) fact_cps 1 id.(*4).(*3).(*2) fact_cps 0 id.(*4).(*3).(*2).(*1) (id.(*4).(*3).(*2).(*1))

Чего так можно добиться? Оказывается, к такому виду можно привести любую программу Но зачем? fact_cps n f = fact_cps (n-1) (f.(*n)) Что можно сказать хорошего про эту фунцкию? tail recursive! Для хвостовой рекурсии не нужен стек Значит CPS программам вообще не нужен стек! Чудес не бывает! Куда делся стек? Стек – это и есть параметр f. Там храниться то, что нам еще надо сделать 19

Некоторые применения Можно реализовывать сложную передачу управления Например, как программу с goto перевести в функциональную программу? Вариант при разработке компилятора: автоматически переводить в CPS стиль Тогда не нужен будет стек Например, Scheme Асинхронные вычисления Выполнить действие A, а потом, когда оно завершиться, выполнить с результатом действие B Например,.NET Task Parallel Library us/library/ee372288(v=vs.110).aspx 20

Еще про >>=. do нотация 21

doubleEven doubleEven xs = xs >>= \x -> if x `mod` 2 == 0 then [x,x] else [x] -- для всех элементов x из xs … 22

cartesian cartesian [1, 2] [30, 40] [(1,30), (1, 40), (2, 30), (2, 40)] caretsian xs ys = xs >>= \x -> приписать x, ко всем элементам ys 1 [(1,30),(1,40)] 2->[(2,30),(2,40)] Как приписать x ко всем элементам ys? Можно map Красивее еще раз >>= ys >>= \y-> [(x, y)] Итого cartesian xs ys = xs >>= \x -> ys >>= \y -> [(x, y)] 23

Замечания xs >>= \x -> ys >>= \y -> … Программирование с использованием таких цепочек - monadic programming style (Позже будет более строго) Есть стандартная функция return return x= [x] cartesian xs ys = xs >>= \x -> ys >>= \y -> return (x, y) Зачем? Тогда можно определить >>= и return и для других типов и писать в таком стиле не только для списков 24

Почему называется bind? do нотация cartesian xs ys = xs >>= \x -> ys >>= \y -> return (x, y) xs >>= \x -> можно понимать как "Для каждого x из списка xs …" Поэтому >>= читается bind (связать) (x по очереди связывается со всеми элементами) Есть сокращенная запись: do x Двумерный синтаксис, как в let 25

Символьные вычисления 26

eval data Expr = Num Integer | X | Add Expr Expr | Mult Expr Expr eval выражение значение_для_X eval (Num i) _ = i eval X n = n eval (Add x y) n = eval x n + eval y n eval (Mult x y) n = eval x n * eval y n 27

diff В Expr обязательно deriving Show diff (Num _) = Num 0 diff X = Num 1 diff (Add x y) = Add (diff x) (diff y) diff (Mult x y) = Add (Mult (dif x) y) (Mult (dif y) x) 28

Если хотим использовать несколько переменных? X Var "a", Var "sum" и т.д. Add (Mult (Num 10) (Var "a")) (Var "b) 10*a + b Какой должен быть параметр у eval? Список пар (строка, значение) Например: eval (Add (Mult (Num 10) (Var "a")) (Var "b)) [("a", 5), ("b", 7)] Называется обычно env (environment) 29

Комбинируем функции 30

flatten flatten (Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty)) [1,2,3] flatten Empty = [] flatten (Node val l r) = val : flatten l ++ flatten r Медленно.. flatten' – приписать все числа дерева к данном списку flatten t = flatten' t [] flatten' Empty xs = xs flatten' (Node x l r) xs = let xs1 = flatten l xs xs2 = flatten r xs1 in x:xs2 31

flatten – как написать короче? Как можно записать коротко? Идея: работать с функциями, а не с данными Рассмотрим flatten' tree, как функцию с 1 параметром (карринг) Ее тип [Integer] -> Integer Она приписывает все вершины к данному списку flatten' Empty = id flatten' (Node x l r) = (x:). flatten' l. flatten' r Т.е. мораль: некоторые задачи записываются коротко и довольно понятно, если использовать композицию функций (описывать программу не в терминах операций над списками, а в терминах операций над функциями.) Просто кстати: есть другой способ записать очень коротко: flatten = foldTree (:) [] 32

Как вернуть позицию в списке? Когда мы ищем что-то в списке, хотелось бы вернуть не просто значение, а еще как-то и то место, на коотором мы его нашли. Например, хотелось бы написать find, чтобы с его помощью можно было решать такие задачи: Найти третий элемент в списке, удовлетворяющий данному условию Найти сумму всех элементов в спске, удовлетворяющих данному условию и т.д. Распостраненный вариант: возвращать пару (значение, еще не просмотренный хвост списка) find cond (x:xs) = if cond x then (x, xs) else find cond xs В этой теме давайте для простоты временно считать, что мы всегда точно найдем элемент, удовленторяющий условию. 33

>>> Пусть мы хотим как-то сочетать функции? которые берут список и возвращают пару (значение, список), примерно так же, как мы делали в flatten. Но только (.) тут не подходит Даайте определим «(.) для чтения из списка». Назовем его >>> Т.е. задача (для д.з.): Определить такой оператор, назовем его >>>, чтобы можно было писать так: f = find (>3) >>> find (>3) -- f - функция, которая ищет в списке второй элемент, больший 3. f [1, 3, 5, 2, 20, 25, 2] -- Должно получиться (20, [25, 2]) 34

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

allDiffLists allDiffLists n k = allDiffLists' n k [] allDiffLists' n k s (s – те элементы, которые мы уже включили) allDiffLists' n 0 _ = [[]] allDiffLists' n k s = [x:xs | x cond t && t /= x)] 36

digits на C# double x = 1.0 / n; После такой строчки вы точно не найдете бесконечно много знаков double – точность знаков, вот их вы и найдете… 37

Д.з. 38

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