Похожие презентации:
Функциональное программирование
1.
Функциональноепрограммирование
Парадигма программирования,
рассматривающая выполнение программы как
вычисление математических операций.
На практике:
Нет присваивания!
Функции – в математическом смысле!
Нет побочных эффектов!
2.
Зачем?Проще писать правильно
(Вещи не меняют значения по ходу дела)
Проще распараллеливать
(Та же причина, можно выполнять многие
вещи в любом порядке)
Это красиво и математично!
(Ибо воистену!)
3.
HaskellСоздан вовсе не Хаскеллом Карри, тот вообще
умер раньше.
Всё можно в Википедии прочитать.
Мы будем пользоваться
интерпретатором HUGS, но
компиляторы тоже есть.
4.
Что тут есть?Функции высшего порядка
(Функции, принимающие или возвращающие
функции)
Лямбда-выражения
(Функции без названия)
Ленивые вычисления
(Задержка вычисления до востребования)
Сильное колдунство вроде монад
5.
Лексика--это комментарий
{--а это
многострочный комментарий}
Имена
с маленькой буквы переменные и функции
с большой буквы типы и константы (как True)
можно использовать кавычки (например
функция f')
6.
Числа и операторыОбычные числа: 21 2.71 6.1e24
Сколькоугоднозначные 2^1000
Операции: + - * / div mod ^
Сравнение < > <= >= /=
&& || not
True False
7.
ФункцииБез скобок, запятых или подобного
sin x
mod k 10 + div k 10
Приоритет: функции раньше операторов
sin x*x это (sin x)*x
f g x это (f g) x
Осторожно!
sin sin 1 это (sin sin) 1 --ошибка!
8.
Как определить функцию(продолжение)
Порядок важен!
fact n = n * fact (n-1)
fact 0 = 1 --сюда не дойдёт!
Без повторений!
func n n = ... --так нельзя!
Джокер
func 0 _ = 0 --второй аргумент – что угодно
9.
Частичная параметризацияЕсли "f" – функция от четырёх параметров, то
"f 1" – функция от трёх, "f 1 2" – от двух, а "f 1 2
3" – от одного. Обязательно слева направо!
Для операторов тоже работает: "+1" – вполне
себе функция от одного параметра, ">3" и "3>"
тоже.
10.
Условный операторif условие then выражение else выражение
abs x = if x > 0
then x
else -x
Отступы важны!
11.
ОператорыМожно определять свои. Пример:
i @@ j = i*i + j*j
Пример вызова:
5 @@ 7
74
Обычные функции от двух переменных можно
использовать как инфиксный оператор, взяв в
обратные кавычки.
40 `mod` 7
12.
Накапливающий параметрДавайте вычислять факториал, перемножая
числа сразу по ходу рекурсии.
fact' 1 p = p
fact' n p = fact’ (n-1) (n*p)
fact n = fact’ n 1
Почти как цикл в обычном языке!
13.
Хвостовая рекурсияЕсли вызов функции – это последнее, что
происходит при вычислении правила, то он
называется хвостовым вызовом (tail call).
Если в некоторой функции все рекурсивные
вызовы – хвостовые, то говорят, что в этой
функции используется хвостовая рекурсия (tail
recursion)
fact n = n * fact (n-1)
Это хвостовая рекурсия?
14.
Хвостовая рекурсия(продолжение)
Нет!
А вот
fact' n p = fact’ (n-1) (n*p)
да!
Полезно тем, что параметры функции, из
которой происходит вызов, не хранятся в
памяти.
15.
Сравнитеfact 0 = 1
fact n = n * fact (n-1)
При каждом вызове в памяти сохраняется ещё
одно n.
fact' 1 p = p
fact' n p = fact’ (n-1) (n*p)
fact n = fact’ n 1
А тут нет!
16.
Задача: sumfactНаписать функцию sumfact, принимающую n и
возвращающую сумму факториалов чисел от 1
до n.
Наиболее эффективно!
17.
Решениеsumfact' 0 i p s = s
sumfact' n i p s = sumfact' (n-1) (i+1) (p*i) (s+p*i)
sumfact n = sumfact' n 1 1 0
Хвостовая рекурсия!
Накапливающий параметр!
18.
letsumfact' n i p s = let
p' = p*i
in sumfact' (n-1) (i+1) p' (s+p')
Правда, лучше?)
Можно перечислять несколько обозначений
19.
let (продолжение)В общем случае:
let
правило1
правило2
…
in выражение
И опять отступы важны!
Но можно так: let {правило1; правило2;
правило3} in выражение
20.
whereКак let, но по другому:
sumfact' n i p s = sumfact' (n-1) (i+1) p’ (s+p’)
where p’ = p*i
левая часть = правая часть
where вспомогательные определения
Тоже двумерный синтаксис!
Разница:
let – где угодно
where – часть правила
21.
СпискиСписки – основной тип данных
Примеры:
[1,2,3] [3.1, 4.14, -5.1415] [True, False, True]
Элементы списка должны быть одного типа!
[1, True, 2] --ошибка!
Оператор ":" приписывает элемент в начало
списка
1 : [2, 3] –получится [1, 2, 3]
22.
Списки (продолжение)[a..b] – список чисел от a до b с шагом 1.
Кстати, ['a'..'z'] – тоже можно!
И даже [2, 4..20] можно!
На самом деле [1, 5, 7] – просто сокращение
для 1 : 5 : 7 : []
Пример:
f 0 = []
f n = n : f (n-1)
23.
Обработка списков (первыйспособ)
head xs – первый элемент xs
tail xs все элементы xs, кроме первого
last и init – аналогично, но куда дольше
24.
Обработка списков (второйспособ)
f [x]
f [x, y, z]
f [1, y, 2]
f (x:y:xs) -- скобки обязательны!
f (x:1:xs)
Помним про линейность!
f [x,y,x] --ошибка!
25.
Пример работы со спискамиСумма всех элементов списка
sum [] = 0
sum xs = head xs + sum(tail xs)
Или так:
sum [] = 0
sum (x:xs) = x + sum xs
На самом деле это стандартная функция
26.
Ещё примерСтандартная функция product тоже есть.
Поэтому совсем правильно писать факториал
так:
fact n = product [1..n]
Это и есть стиль Haskell!
27.
КонкатенацияНесмотря на то, что это очень страшное и
умное слово, всё очень просто.
[1,2] ++ [3,4] [1,2,3,4]
Но помните:
xs : x -- нельзя, только в начало!
xs ++ x -- нельзя, ++ работает только со
списками!
xs ++ [x] -- можно, но медленно!
28.
Задача: sqrlistНаписать функцию sqrlist, которая принимает
число n и возвращает список квадратов чисел
от 1 до n.
Наиболее эффективно!
29.
Решение (вариант 1)sqrlist 0 = []
sqrlist n = (sqrlist (n-1)) ++ [n^2]
Правильно, но очень медленно
30.
Решение (Вариант 2)sqrlist' n m = if (n >= m)
then (m^2) : (sqrlist' n (m+1))
else []
sqrlist n = sqrlist' n 1
Уже лучше, но можно проще
31.
Решение (вариант 3)sqrlist' [] = []
sqrlist' (x:xs) = (x^2):(sqlist' xs)
sqrlist n = sqrlist' [1..n]
Хорошо! Но когда мы познаем всю... вернее,
чуть большую часть мощи Хаскеля, мы будем
писать это так:
sqrlist n = map (\x -> x^2) [1..n]
Или даже так: sqrlist n = map (^2) [1..n]
32.
Функции высшего порядкаПример: map
map применяет функцию ко всем элементам
списка.
map f [] = []
map f (x:xs) = f x : map f xs
Пример вызова:
map (^2) [1..3]
[1,4,9]
33.
Лямбда-выраженияЗадача: умножить все числа списка xs на 10, а
потом прибавить к ним 5.
f x = x * 10 + 5
map x xs
Можно короче!
map (\x -> 10 * x + 5) xs
\ - то, что осталось от лямбды
34.
Некоторые встроенные функциивысшего порядка
maximum, minimum – думаю, понятно, что
делают)
foldr, foldl – легче на примере
foldr @ [a,b,c] = a @ (b @ c)
foldl @ [a,b,c] = (a @ b) @ c
foldl куда медленнее работает, используют
редко.
35.
Всякие задачиНаписать функцию reverse, разворачивающую
список
Написать функцию check, проверяющую, есть
ли в списке элемент, удовлетворяющий
данному условию (на самом деле такая есть
стандартная, называется, правда, any)
Написать функцию check, проверяющую, есть
ли в списке чисел два числа дающие в сумме
10.