21 KiB
| theme | author |
|---|---|
| superblack | Ilya Kostyuchenko |
Функциональное программирование
:::{.notes} Функциональное программирование это не про использование map filter reduce. Функциональное программирование это вообще ортогонально к ооп. ИМХО проблема с ООП -- наследование (которое тоже ортогонально к ООП) -- нет разграничения между абстракцией и реализацией. и вообще обзывание это функциональным программированием -- не совсем правильно. то, что мы сейчас будем пытаться сделать -- сделать код более переиспользуемым. сделать наши данные максимально тупыми => переиспользуемыми. пытаться комбинировать слишком умные куски -- не получится -- слишком сложно. мы хотим сделать простые куски, которые просто комбинировать и еще чтобы компилятор проверял эти наши комбинации на валидность. :::
Программировать можно без боли
Функциональное программирование -- метапрограммирование над эффектами.
Эффекты?
class Cafe {
Coffee buyCoffee(CreditCard cc, Payments p) {
Coffee cup = new Coffee();
p.charge(cc, cup.price);
return cup;
}
}
{width=450}
class Cafe {
Pair<Coffee, Charge> buyCoffee(CreditCard cc) {
Coffee cup = new Coffee();
return new Pair(cup, cup.price);
}
}
| {width=450} | {width=450 .fragment} |
Функциональное программирование:
функции -- это тоже данные.
Int -> Bool (функция) -- ровно такие же данные как и Int. Их также
можно складывать в структуры, передавать как аргументы и т. п.
нотация
| ```java int x; ``` | ```haskell x :: Int ``` |
| ```java int f(int x) ``` | ```haskell f :: Int -> Int ``` |
| ```java static T f(T x) ``` | ```haskell f :: a -> a ``` |
| ```java static T f(T x) ``` | ```haskell f :: a -> a ``` |
| ```java f(x); ``` | ```haskell f x ``` |
| ```java f(x, y); ``` |
```{.fragment .haskell}
f x y
```
|
:::{.notes} Left-associative Currying :::
| ```java static T f(T x) static T g(T x) ``` | ```haskell f :: a -> a g :: a -> a ``` |
| ```java f(g(x)); g(f(x)); ``` | ```haskell f (g x) g (f x) ``` |
Композиция
f :: a -> a
g :: a -> a
f (g x)
(f . g) x == f (g x)
h = f . g
h x == f (g x)
f :: a -> a
g :: a -> a
h :: a -> a
h = f . g
f x = x * 2
g x = x - 3
(f . g) 5
-- 4
:::{.notes} моноид -- у тебя есть две штуки одного типа и ты можешь получить еще одну штуку такого же типа. Это очень простой способ рождения сложности из простоты причем тип h выводится из определения. Нам его указывать не надо. если у нас изначальные маленькие кусочки хорошо описаны, то порожденные большие кусочки будут автоматически хорошо описанными. :::
Haskell
Чисто функциональный
Все что функция может сделать -- посмотреть на свои аргументы это вернуть значение.
:::{.notes} Нельзя просто произвольно распечатать строку в консоль, нельзя просто произвольно отправить запрос на бд, нельзя просто произвольно изменить глобальную переменную. :::
Referential transparency
(Любую константу можно заменить на само значение)
int x = 8;
int y = x++;
System.out.println(y + " might be the same as " + y);
int x = 8;
System.out.println(x++ + " might be the same as " + x++);
:::notes Сильно упрощает рефакторинг и понимание кода. :::
Immuatble
Совсем immutable
Можно не думать о порядке выражений.
Нет переменных, циклов и условных переходов
[Зато есть константы и нормальная рекурсия (А переходов вообще нет)]{.fragment}
Очень ленивый
xs = [4, 1, 3, 2]
xs' = sort xs
print xs
:::fragment
xs' не нужен чтобы распечатать xs, поэтому сортироваться ничто
не будет. (Зачем делать то, что можно не делать)
:::
Если хотите быстро и просто потыкаться, тут есть интерктивная штука:
Синтаксис
Функции
add2 :: Int -> Int
add2 x = x + 2
Все функции и константы всегда обозначаются словами с маленькой буквы без пробелов.
(Константы это просто функции с нулем аргументов.)
:::notes Мы буквально говорим что функция на таком-то аргументе равна чему-то. :::
Pattern matching
fixBuz :: Int -> String
fixBuz 3 = "Fiz"
fixBuz 5 = "Buz"
fixBuz 15 = "FizBuz"
fixBuz _ = "Some other number"
Так матчить можно произвольные структуры произвольного уровня вложенности.
_ -- специальное название константы, которое говорит
что вам все равно что в ней лежит.
:::notes функции объявляются в несколькро строк. Первая -- обьявленик типа функции, а последующие -- реализация. В общем случае тип можно не указывать, но указывать тип у высказыванй на самом верхнем уровне (не вложенные) считается хорошим тоном и улучшает выведение типов и ошибки компиляции. У функции может быть несколько реализаций: какая из них вызовется зависит от значений передаваемых аргументов. матчинг произхводится сверху вниз. если в аргемантах написано слово с маленькой буквы, то значение аргумента биндится на эту константу. :::
Структуры
Произведение типов
(обычные поля структур)
:::notes После констрктора можно укзать существующие типы, которые в нем храняться. :::
data PersonType = Person String Int
vasya :: PersonType
vasya = Person "Vasya" 8
-- тип можно не укзывать
petya = Person "Petya" 5
getName :: PersonType -> String
getName (Person name _) = name
greetPerson :: PersonType -> String
greetPerson p = "Hello, " ++ getName p
greetPerson petya
-- "Hello, Petya"
vasya = Person "Vasya" 8
petya = Person "Petya" 5
matchVasya :: PersonType -> Bool
matchVasya (Person "Vasya" _) = True
matchVasya _ = False
matchVasya vasya
-- True
matchVasya petya
-- False
data Foo = Bar
qux :: Foo
qux = Bar
Foo -- тип структуры. Bar -- конструктор структуры.
Тут у Foo всего одно значение Bar.
Еще немного функций
greetPerson :: PersonType -> String
greetPerson p = "Hello, " ++ getName p
greetPerson :: PersonType -> String
greetPerson p = "Hello, " ++ name
where
name = getName p
greetPerson :: PersonType -> String
greetPerson p = "Hello, " ++ name
where
getName' (Person name _) = name
name = getName' p
data PersonType = Person String Int
getName :: PersonType -> String
getName (Person name _) = name
greetName :: String -> String
greetName name = "Hello, " ++ name
greetPerson :: PersonType -> String
greetPerson p = greetName (getName p)
greetPerson :: PersonType -> String
greetPerson = greetName . getName
greetPerson petya
-- "Hello, Petya"
(greetName . getName) petya
-- "Hello, Petya"
Суммы типов
:::notes Функции нескольких аргументов -- странный синтаксис -- потом расскажу. А пока используем тюпли!
В большинстве других языков этого нет и используются всякие странные кодирования типо нулевые указатели, и никто не просит тебя их проверять, что очень плохо. :::
data Bool = False | True
x :: Bool
x = True
y = False
ifThenElse :: (Bool, a, a) -> a
ifThenElse (True, a, _) = a
ifThenElse (False, _, b) = b
ifThenElse (True, "Hello", "World")
-- "Hello"
ifThenElse (False, "Hello", "World")
-- "World"
data CircleType = Circle Double Double Double
data RectangleType = Rectangle Double Double Double Double
data Shape =
CircleShape CircleType | RectangleShape RectangleType
surface :: Shape -> Double
surface (CircleShape (Circle _ _ r)) =
pi * r ^ 2
surface (RectangleShape (Rectangle x1 y1 x2 y2)) =
(abs (x2 - x1)) * (abs (y2 - y1))
shape = CircleShape (Circle 0 0 2)
surface shape
-- 12.566370614359172
otherShape = RectangleShape (Rectangle 1 2 3 4)
surface otherShape
-- 4.0
И еще немного функций
Лямбда-выражения
add8 :: Int -> Int
add8 x = x + 8
add8 = \x -> x + 8
[λ -- \ (λ печатать тяжело)]{.fragment}
foo :: (Int -> Int) -> Int
foo add8
foo (\x -> x + 8)
Давайте придумаем синтаксис для функции нескольких аргументов!
x, y :: Int
x = 42
y = 69
xPlusY :: Int
xPlusY = add x y
[Применение функции -- лево-ассоциативно]{.fragment}
xPlusY = (add x) y
xPlusY = f y
f = add x
f :: Int -> Int
add :: Int -> (Int -> Int)
add :: Int -> (Int -> Int)
[Тип -> -- право-ассоциативный]{.fragment}
add :: Int -> Int -> Int
add a b = a + b
add = \a b -> a + b
Любая функция берет строго один аргумент.
Функция нескольких аргументов все равно берет строго одтн аргумент и возвращает функцию, которая берет следующий.
(И из-за того, что применение функции лево-ассоциативно, вызов таких не трубует особого синтаксиса.)
Currying
add :: Int -> Int -> Int
add a b = a + b
add8 :: Int -> Int
add :: Int -> (Int -> Int)
add8 = add 8
add8 3
-- 11
Funny fact
[Оператор (например +) -- функция, название которой не содержит буквы и цифры.]{.fragment}
x +&+ y = x + y
8 +&+ 9
-- 17
Funny fact 2
[Оператор можно превратить в функцию, окружив его скобками.]{.fragment}
8 +&+ 9
-- 17
(+&+) 8 9
-- 17
add :: Int -> Int -> Int
add x y = x + y
add = (+&+)
add = (+)
Funny fact 3
[Функцию можно превратить в оператор, окружив ее обратными кавычками.]{.fragment}
add :: Int -> Int -> Int
add x y = x + y
add 8 9
-- 17
8 `add` 9
-- 17
Список
Односвязный список
data IntList = Nil | Cons Int IntList
Cons :: Int -> IntList -> IntList
Nil :: IntList
nums :: IntList
nums = 1 `Cons` (2 `Cons` (3 `Cons` Nil))
sum :: IntList -> Int
sum (Cons x xs) = x + sum xs
sum Nil = 0
sum (Cons x xs) = x + sum xs
sum nums
-- 6
take :: Int -> IntList -> IntList
take _ Nil = Nil
take 0 _ = Nil
take n (Cons x xs) = Cons x (take (n - 1) xs)
nums :: IntList
nums = 1 `Cons` (2 `Cons` (3 `Cons` Nil))
take 2 nums
-- Cons 1 (Cons 2 Nil)
take 1029 nums
-- Cons 1 (Cons 2 (Cons 3 Nil))
take 0 nums
-- Nil
repeat :: Int -> IntList
repeat n = Cons n (repeat n)
repeat 8
-- Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (Cons 8 (...
(take 3 . repeat) 8
-- Cons 8 (Cons 8 (Cons 8 Nil))
(sum . take 3 . repeat) 8
-- 24
| Наша самодеятельность | В стандартной библиотеке |
| ```haskell IntList ``` | ```haskell [Int] ``` |
| ```haskell Nil ``` | ```haskell [] ``` |
| ```haskell Cons ``` | ```haskell : ``` |
| ```haskell Cons 3 (Cons 4 Nil) ``` |
``` {.fragment .haskell }
3 : 4 : []
```
|
data IntList = Nil | Cons Int IntList
data [Int] = [] | Int : [Int]
repeat, sum и take тоже есть в стандартной библиотеке.
repeat 8
-- [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, ...
[8 ..]
-- [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...
[8 .. 11]
-- [8, 9, 10, 11]
[8 .. 8]
-- [8]
[8 .. 5]
-- []
QuickSort
quicksort :: [Int] -> [Int]
quicksort (x:xs) =
quicksort smaller ++ [x] ++ quicksort larger
where
smaller = filter (< x) xs
larger = filter (>= x) xs
filter :: (Bool -> Int) -> [Int] -> [Int]
filter f (x:xs) =
if f x
then x:(filter f xs)
else filter f xs
filter _ [] = []
filter f (x:xs) =
if f x
then filter f xs
else x:(filter f xs)
quicksort :: [Int] -> [Int]
quicksort (x:xs) =
quicksort smaller ++ [x] ++ quicksort larger
where
smaller = filter (< x) xs
larger = filter (>= x) xs
filter _ [] = []
filter f (x:xs) =
if f x
then filter f xs
else x:(filter f xs)
quicksort :: [Int] -> [Int]
quicksort [] = []
quicksort (x:xs) =
quicksort smaller ++ [x] ++ quicksort larger
where
smaller = filter (< x) xs
larger = filter (>= x) xs
filter _ [] = []
filter f (x:xs) =
if f x
then filter f xs
else x:(filter f xs)
quicksort [2, 1, 3, 4]
-- [1, 2, 3, 4]
filter тоже есть в стандартной библиотеке.
Еще немного структур
Параметрический полиморфизм
(Дженерики)
data IntList = Cons Int IntList | Nil
:::notes Мы научиоись делать список интов. А что если мы хотим сделать просто список. Чего-нибудь. :::
data List a = Cons a (List a) | Nil
class List<T> { ...
ints :: List Int
ints = Cons 1 (Cons 2 (Cons 3 Nil))
-- Типы как всегда можно не писать
strings :: List String
strings = Cons "one" (Cons "two" (Cons "three" Nil))
things = Cons "one" (Cons 2 Nil)
• Couldn't match type ‘Int’ with ‘String’
Expected type: List String
Actual type: List Int
|
10 | things = Cons "one" (Cons 2 Nil)
| ^^^^^^^^^^^^
data List a = Cons a (List a) | Nil
[a должен всегда быть a.]{.fragment}
take :: Int -> IntList -> IntList
take _ Nil = Nil
take 0 _ = Nil
take n (Cons x xs) = Cons x (take (n - 1) xs)
take :: Int -> List a -> List a
take _ Nil = Nil
take 0 _ = Nil
take n (Cons x xs) = Cons x (take (n - 1) xs)
:::notes Поменялся только тип! :::