Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps)

Нажмите для полного просмотра!

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №2

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №3

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №4

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №5

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №6

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №7

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №8

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №9

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №10

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №11

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №12

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №13

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №14

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №15

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №16

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №17

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №18

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №19

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №20

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №21

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №22

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №23

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №24

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №25

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №26

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №27

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №28

Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №29

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps). Доклад-сообщение содержит 29 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Д.з.

Слайд 2

Описание слайда:

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)

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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 res = f (res *n)

Слайд 10

Описание слайда:

Как это работает? Обычный fact fact 4  fact 3  fact 2  fact 1  fact 0  1 * 1 * 2 * 3 * 4

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

Некоторые применения Можно реализовывать сложную передачу управления Peter Landin: как программу с goto перевести в функциональную программу? Вариант при разработке компилятора: автоматически переводить в CPS стиль Тогда не нужен будет стек Например, Scheme Асинхронные вычисления Выполнить действие A, а потом, когда оно завершиться, выполнить с результатом действие B Например, .NET Task Parallel Library

Слайд 13

Описание слайда:

Еще про >>=. >>= для других типов

Слайд 14

Описание слайда:

Три поиска Найти в списке: первое число, меньшее 5 первое число, большее 10 первое число, не равное 7 Вернуть сумму этих чисел, или [], если что-то не нашли find cond [] = [] find cond (x:xs) = if cond x then [x] else find cond xs

Слайд 15

$«Выполнять до первой неудачи» f xs = do x = \x -> find (>10) xs >>= \y -> find (/=7) xs >>= \z -> return (x+y+z)$

Описание слайда:

«Выполнять до первой неудачи» f xs = do x = \x -> find (>10) xs >>= \y -> find (/=7) xs >>= \z -> return (x+y+z)

Слайд 16

Описание слайда:

do для Maybe >> и return (и, следовательно, do) определены и для Maybe Смысл такой же – «выполнять до первой неудачи» Например: Найти число, которые больше всех остальных вместе в xs, число которое больше всех остальных в yx и вернуть их произведение. Если не получится, вернуть Nothing. do x

Слайд 17

Описание слайда:

Что такое монады, формально Монада – это тип, для которого определены операции >>= return Строго говоря операции еще должны удовлетворять некоторым правилам (Monadic laws) return a >>= f ≡ f a m >>= return ≡ m (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g) Уже знаем два примера монад: List Maybe

Слайд 18

Описание слайда:

В каких случаях используют монады? f xs = do x

Слайд 19

Описание слайда:

Функция print print выражение print 56 56 Ничего не возвращает, только печатает Смысл очень понятен Но непонятно как это сочетается отсуствием побочных эффектов и т.д. Об этом в следующий раз

Слайд 20

Описание слайда:

Пример: вывод + рекурсия pr 0 = print 0 pr n = do print n pr (n-1) pr 5 5 4 3 2 1 0

Слайд 21

Описание слайда:

Задача про >>> и ее продолжение

Слайд 22

$>>> Что-то вроде композиции, но специально для функций вида список -> (значение, список) Пример вызова: f = find (>3) >>> find (>5) f >>> g = \xs ->...$

Описание слайда:

>>> Что-то вроде композиции, но специально для функций вида список -> (значение, список) Пример вызова: f = find (>3) >>> find (>5) f >>> g = \xs -> let (_, xs1) = f xs in g xs1

Слайд 23

Описание слайда:

Недостатки >>> Нужно ли еще что-то, чтобы гибко комбинировать функции такого вида? Пример 1: Найти число большее 3, потом число, больше 5 и вернуть их сумму Пример 2: Найти число t, большее 3, а потом найти число, большее t C помощью >>> не написать… Д.з.: обобщить >>>, чтобы устранить этот недостаток Подсказка: я бы предложил ввести функцию >>>=

Слайд 24

Описание слайда:

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

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

diff data Expr = Num Integer | X | Add Expr Expr | Mult Expr Expr deriving Show В 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 (diff x) y) (Mult (diff y) x)

Слайд 27

Описание слайда:

Если хотим использовать несколько переменных? 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)]

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

fromStr toStr Empty = 'e‘ toStr (Node v l r) = 'n':toStr l ++ toStr r создать строку  дописать строку! fromStr’ t s – дописать представление t к строке s toStr’ Empty s = 'e':s toStr’ (Node v l r) s = let s1 = toStr’ r s s2 = tpStr’ l s1 in 'n':s2 Задача на занятии на листке: записать эти правила не используя прямо строки s, s1, s2 – т.е. с помощью операций над функциями