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);
    }
}

![](images/coffee-without-effects.png){width=450}

![](images/coffee-without-effects-list.png){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 ``` `f x y = (f x) y` `</td> </td>`

:::{.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, поэтому сортироваться ничто не будет. (Зачем делать то, что можно не делать) :::

Если хотите быстро и просто потыкаться, тут есть интерктивная штука:

haskell.org

Синтаксис

Функции

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 : [] ``` `[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 Поменялся только тип! :::

Где и как смотреть "стандартную библиотеку"

Hackage

(Там вам нужен только пакет base. Ссылка ведет прямо на него.) Еще если там нажать s, то будет поиск.
Hoogle

Это поиск по типам. Например: Int -> [Int] -> [Int] (Тут вам опять же нужен только пакет base. Нужно чтобы справа было "package:base".)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

1.md

1.md

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

Программировать можно без боли

Эффекты?

нотация

Композиция

Haskell

Чисто функциональный

Referential transparency

(Любую константу можно заменить на само значение)

Immuatble

Совсем immutable

Нет переменных, циклов и условных переходов

Очень ленивый

Синтаксис

Функции

Pattern matching

Структуры

Произведение типов

(обычные поля структур)

Еще немного функций

Суммы типов

И еще немного функций

Лямбда-выражения

Давайте придумаем синтаксис для функции нескольких аргументов!

Currying

Funny fact

Funny fact 2

Funny fact 3

Список

Односвязный список

QuickSort

Еще немного структур

Параметрический полиморфизм

(Дженерики)

Где и как смотреть "стандартную библиотеку"

Files

1.md

Latest commit

History

1.md

File metadata and controls

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

Программировать можно без боли

Эффекты?

нотация

Композиция

Haskell

Чисто функциональный

Referential transparency

(Любую константу можно заменить на само значение)

Immuatble

Совсем immutable

Нет переменных, циклов и условных переходов

Очень ленивый

Синтаксис

Функции

Pattern matching

Структуры

Произведение типов

(обычные поля структур)

Еще немного функций

Суммы типов

И еще немного функций

Лямбда-выражения

Давайте придумаем синтаксис для функции нескольких аргументов!

Currying

Funny fact

Funny fact 2

Funny fact 3

Список

Односвязный список

QuickSort

Еще немного структур

Параметрический полиморфизм

(Дженерики)

Где и как смотреть "стандартную библиотеку"