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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps), слайд №1Домашнее задание. 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)
Описание слайда:
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
Описание слайда:
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<-[1..n], not (elem x s), allDiffLists' n k (x:s)] То же с приемом "представление множества с помощью функции" allDiffLists n k = allDiffLists' n k (\t -> False) allDiffLists' n k cond (cond – условие, которое мы проверяем) allDiffLists' n 0 _ = [[]] allDiffLists' n k cond = [x:xs | x<-[1..n], not (cond x), xs <- allDiffLists' n (k-1) (\t -> cond t || t == x)]
Описание слайда:
allDiffLists allDiffLists n k = allDiffLists' n k [] allDiffLists' n k s (s – те элементы, которые мы уже включили) allDiffLists' n 0 _ = [[]] allDiffLists' n k s = [x:xs | x<-[1..n], not (elem x s), allDiffLists' n k (x:s)] То же с приемом "представление множества с помощью функции" allDiffLists n k = allDiffLists' n k (\t -> False) allDiffLists' n k cond (cond – условие, которое мы проверяем) allDiffLists' n 0 _ = [[]] allDiffLists' n k cond = [x:xs | x<-[1..n], not (cond x), xs <- allDiffLists' n (k-1) (\t -> cond t || t == 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!
Описание слайда:
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)
Описание слайда:
Continuations (продолжения). Continuation-passing style (CPS)

Слайд 7


Continuation-passing style Continuation: параметр–функция. Задает, что делать после окончания работы функции failure continuation – вызываем, если функция завершилась не успешно Continuation-passing style (CPS) - вызываем всегда!
Описание слайда:
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
Описание слайда:
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)
Описание слайда:
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
Описание слайда:
Как это работает? Обычный 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. Там храниться то, что нам еще надо сделать
Описание слайда:
Чего так можно добиться? Оказывается, к такому виду можно привести любую программу fact_cps n f = fact_cps (n-1) … Что можно сказать fact_cps? Хвостовая рекурсия Для хвостовой рекурсии не нужен стек Значит CPS программам вообще не нужен стек! Чудес не бывает! Куда делся стек? Стек – это и есть параметр f. Там храниться то, что нам еще надо сделать

Слайд 12


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

Слайд 13


Еще про >>=. >>= для других типов
Описание слайда:
Еще про >>=. >>= для других типов

Слайд 14


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

Слайд 15


«Выполнять до первой неудачи» f xs = do x <- find (<5) xs y <- find (>10) xs z <- find (/=7) xs return (x+y+z) Если пустой список обозначает неудачу поиска то do – «выполнять до первой неудачи» Или можно то же через >>= f xs = find (<5) xs >>= \x -> find (>10) xs >>= \y -> find (/=7) xs >>= \z -> return (x+y+z)
Описание слайда:
«Выполнять до первой неудачи» f xs = do x <- find (<5) xs y <- find (>10) xs z <- find (/=7) xs return (x+y+z) Если пустой список обозначает неудачу поиска то do – «выполнять до первой неудачи» Или можно то же через >>= f xs = find (<5) xs >>= \x -> find (>10) xs >>= \y -> find (/=7) xs >>= \z -> return (x+y+z)

Слайд 16


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

Слайд 17


Что такое монады, формально Монада – это тип, для которого определены операции >>= return Строго говоря операции еще должны удовлетворять некоторым правилам (Monadic laws) return a >>= f ≡ f a m >>= return ≡ m (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g) Уже знаем два примера монад: List Maybe
Описание слайда:
Что такое монады, формально Монада – это тип, для которого определены операции >>= 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 <- find (<5) xs y <- find (>10) xs z <- find (/=7) xs return (x+y+z) Т.е. мы описываем некоторые действия Которые должны выполняться одно за другим И при этом должно автоматически происходить что-то дополнительное Примерно как если бы в обычном языке мы могли бы переопределить точку с запятой
Описание слайда:
В каких случаях используют монады? f xs = do x <- find (<5) xs y <- find (>10) xs z <- find (/=7) xs return (x+y+z) Т.е. мы описываем некоторые действия Которые должны выполняться одно за другим И при этом должно автоматически происходить что-то дополнительное Примерно как если бы в обычном языке мы могли бы переопределить точку с запятой

Слайд 19


Функция print print выражение print 56 56 Ничего не возвращает, только печатает Смысл очень понятен Но непонятно как это сочетается отсуствием побочных эффектов и т.д. Об этом в следующий раз
Описание слайда:
Функция 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
Описание слайда:
Пример: вывод + рекурсия 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 -> let (_, xs1) = f xs in g xs1
Описание слайда:
>>> Что-то вроде композиции, но специально для функций вида список -> (значение, список) Пример вызова: f = find (>3) >>> find (>5)  f >>> g = \xs -> let (_, xs1) = f xs in g xs1

Слайд 23


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию