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

Сентябрь 7, 2022

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

Содержание

2. findMajor Найти число больше суммы всех остальных Идея: можно сначала сосчитать сумму s всех чисел Тогда
3. findMajor - продожение Написать специальный find find cond [] = Nothing find cond (x:xs) = if
4. allDiffLists allDiffLists n k = allDiffLists' n k [] allDiffLists' n k s (s – те
5. findInLists Без failure continuation как-то так: искать в первом подсписке if нашли then вернуть то, что
6. Continuations (продолжения). Continuation-passing style (CPS)
7. Continuation-passing style Continuation: параметр–функция. Задает, что делать после окончания работы функции failure continuation – вызываем, если
8. Continuation-passing style – простой пример Обычная функция: sqr x = x*x CPS sqr_cps x f =
9. CPS и рекурсия. Пример: факториал Обычная программа fact 0 = 1 fact n = fact (n-1)
10. Как это работает? Обычный fact fact 4 ? fact 3 ? fact 2 ? fact 1
11. Чего так можно добиться? Оказывается, к такому виду можно привести любую программу fact_cps n f =
12. Некоторые применения Можно реализовывать сложную передачу управления Peter Landin: как программу с goto перевести в функциональную
13. Еще про >>=. >>= для других типов
14. Три поиска Найти в списке: первое число, меньшее 5 первое число, большее 10 первое число, не
15. «Выполнять до первой неудачи» f xs = do x y 10) xs z return (x+y+z) Если
16. do для Maybe >> и return (и, следовательно, do) определены и для Maybe Смысл такой же
17. Что такое монады, формально Монада – это тип, для которого определены операции >>= return Строго говоря
18. В каких случаях используют монады? f xs = do x y 10) xs z return (x+y+z)
19. Функция print print выражение print 56 56 Ничего не возвращает, только печатает Смысл очень понятен Но
20. Пример: вывод + рекурсия pr 0 = print 0 pr n = do print n pr
21. Задача про >>> и ее продолжение
22. >>> Что-то вроде композиции, но специально для функций вида список -> (значение, список) Пример вызова: f
23. Недостатки >>> Нужно ли еще что-то, чтобы гибко комбинировать функции такого вида? Пример 1: Найти число
24. Символьные вычисления
25. eval data Expr = Num Integer | X | Add Expr Expr | Mult Expr Expr
26. diff data Expr = Num Integer | X | Add Expr Expr | Mult Expr Expr
27. Если хотим использовать несколько переменных? X ? Var "a", Var "sum" и т.д. Add (Mult (Num
28. Про некоторые доп.задачи
30. Скачать презентацию

Слайд 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)

Или то же:
fact_cps n f = fact_cps (n-1)
(\res -> f(res*n))
Или, короче:
fact_cps n f = fact_cps (n-1)
(f.(*n))
Вызов:
fact_cps 3 (^2)
? 36
fact_cps 5 id ? 120

После вычисления (n-1)! нам еще надо:
домножить на n
ну и потом вызвать f

Слайд 10

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

?
fact 1 ?
fact 0 ? 1
* 1
* 2
* 3
* 4

fact_cps
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)) 1 ?
24

Постепенно сооружаем функцию, примерно как логическую функцию в задачах про allDiff

Слайд 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

Можно использовать list comprehension!
f xs = [x+y+z | x<- find (<5) xs,
y<-find (>10) xs,
z<- find (/=7) xs]
Используя do
f xs = do
x <- find (<5) xs
y <- find (>10) xs
z <- find (/=7) xs
return (x+y+z)

Слайд 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)
Т.е. мы описываем некоторые действия
Которые должны выполняться одно за другим
И при этом должно автоматически происходить что-то дополнительное
Примерно как если бы в обычном языке мы могли бы переопределить точку с запятой

Вычислить find (<5) xs, потом вычислить find (>10) xs, потом вычислить find (/=7) xs
И, кроме этого выполнять дополнительные действия (проверять, удачно ли завершились вызовы)

Слайд 19

Функция print
print выражение
print 56
56
Ничего не возвращает, только печатает
Смысл очень понятен
Но непонятно

как это сочетается отсуствием побочных эффектов и т.д.
Об этом в следующий раз

Последовательность print записывается с помощью do
Например:
do print 56
print 3.14159
print "abc"
56
3.14159
"abc"

Слайд 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

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

Содержание

findMajorНайти число больше суммы всех остальныхИдея: можно сначала сосчитать сумму s

findMajor - продожениеНаписать специальный findfind cond [] = Nothingfind cond (x:xs)

allDiffListsallDiffLists n k = allDiffLists' n k []allDiffLists' n k s

findInListsБез failure continuation как-то так:искать в первом подспискеif нашли then вернуть

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

Continuation-passing styleContinuation: параметр–функция. Задает, что делать после окончания работы функцииfailure continuation

Continuation-passing style – простой примерОбычная функция: sqr x = x*xCPS sqr_cps x f

CPS и рекурсия. Пример: факториалОбычная программа fact 0 = 1fact n = fact

Как это работает?Обычный factfact 4 ? fact 3 ? fact 2

Чего так можно добиться?Оказывается, к такому виду можно привести любую программуfact_cps

Некоторые примененияМожно реализовывать сложную передачу управленияPeter Landin: как программу с goto

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

Три поискаНайти в списке:первое число, меньшее 5первое число, большее 10первое число,

«Выполнять до первой неудачи»f xs = do x <- find (<5)

do для Maybe>> и return (и, следовательно, do) определены и для

Что такое монады, формальноМонада – это тип, для которого определены операции>>=returnСтрого

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

Функция printprint выражениеprint 5656Ничего не возвращает, только печатаетСмысл очень понятенНо непонятно

Пример: вывод + рекурсия pr 0 = print 0pr n =