Функциональное программирование

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.

let
sumfact' 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.