Презентация Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 29 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:29 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:813.00 kB
- Просмотров:53
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№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<-[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!
№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
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
№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)
№16 слайд
Содержание слайда: 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
№18 слайд
Содержание слайда: В каких случаях используют монады?
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
Ничего не возвращает, только печатает
Смысл очень понятен
Но непонятно как это сочетается отсуствием побочных эффектов и т.д.
Об этом в следующий раз
№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 ->
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 – т.е. с помощью операций над функциями
Скачать все slide презентации Домашнее задание. Findmajor, alldifflists, findinlists. Continuations (продолжения). Continuation-passing style (cps) одним архивом:
