edu-fp

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

## Лекции 2, 3

## Основы функционального программирования

Пенской А.В., 2024

----

## План лекции

- (Лекция 2) Чистые и грязные функции
- Циклы и рекурсии
- Чисто функциональные структуры данных
- Алгебраический (индуктивный) тип данных
- Структурная / вполне обоснованная рекурсия
- Функции высших порядков
- (Лекция 3) Отображения и свёртки
- Замыкания (Closure)
- Бесточечный стиль, комбинаторы
- Рекурсия и вычислительная сложность
- Ссылочная прозрачность

*[Элементы функциональных языков Евгений Кирпичёв — Журнал «Практика функционального программирования», 3, 2009](https://www.fprog.ru/2009/issue3/practice-fp-3-screen.pdf)*

---

## Disclaimer

Языки программирования очень разные.

Особенности языков распределены неравномерно.

"Стоимость" использования фич ФП может значительно отличаться.

Если что-то не очевидно — спросите. Синтаксис показан только через примеры.

---

## Чистые и грязные функции

![](figures/function-side-effects.png)
![](figures/lambda-with-no-name.jpeg)

----

### Грязная функция инкремента

```go
package main

import "fmt"

func inc(m *int) {
    *m = *m + 1
}

func main() {
    x := 0
    inc(&x)
    fmt.Println("Result: ", x)
}
```

*Question*: что за язык и как он вам?

*Offtopic*: как это написать на Python?

----

### Чистая функция инкремента

```go
package main

import "fmt"

func inc(m int) int {
    return m + 1
}

func main() {
    x := 0
    x = inc(x)
    fmt.Println("Result: ", x)
}
```

*Question*: Является ли функция main чистой?

----

### Чистый инкремент <br/> с вроде чистой main

```go
package main

import "fmt"

func inc(m int) int {
    return m + 1
}

func main() {
    x1 := 0
    x2 := inc(x1)
    fmt.Println("Result: ", x2)
}
```

---

## Циклы и рекурсии

Задачи требуют циклов:

- Последовательности.
- Коллекции, массивы, списки.
- Выч-мат.

![](figures/loops-vs-recursion.png)

</div><div class="col">

![](figures/pooh-and-recursion.jpeg)

</div></div>

----

### Факториал через цикл

```python
def fac(n):
    assert n >= 0
    acc = 1
    for e in range(n, 1, -1):
        acc *= e
    return acc
```

----

### Факториал через рекурсию

```python
def fac(n):
    assert n >= 0
    if n == 0: return 1
    return n * fac(n - 1)
```

*Вопрос:* достоинства и недостатки данной реализации?

Notes: повторные проверки, рост стека

----

#### Стек вызова при расчёте факториала

![](figures/factorial-call-stack.png)

----

### Факториал через <br/> хвостовую рекурсию

```python
def fac(n):
    assert n >= 0
    return fac_inner(n, 1)

def fac_inner(n, acc):
    if n <= 1: return acc
    return fac_inner(n - 1, acc * n)
```

*Вопрос:* достоинства и недостатки данной реализации?

----

### Расчёт факториала в математическом стиле

$fac(n) = \begin{cases} 1, & if \: n = 0 \\\\ n * fac(n-1) \end{cases}$

С использованием Haskell и сопоставления с образцом:

```haskell
fac 0 = 1
fac n = n * fac(n-1)
```

*Questions:*

- Достоинства и недостатки данной реализации?
- На какое свойство влияет тип аргумента?
    - Проблема остановки. 
    - Проблема отличия машинных и математических типов.

---

## Чисто функциональные структуры данных

Рекурсивный код $\rightarrow$ рекурсивные данные.

A *purely functional data* (PFD) structure is a data structure that can be implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongly) immutable.

Пример: Array если copy on write.

*Вопрос:* Какова эффективность таких структур?

----

### Single-linked list

#### Нефункциональное объединение списков

![](figures/imperative-append-to-list.png)

----

#### Функциональное объединение списков

![](figures/functional-append-to-list.png)

----

### Binary search tree

Вставка в бинарное дерево

![](figures/btree-insert-before.png)
![](figures/btree-insert-after.png)

----

### Binary Search Tree: <br/> Recursive Search

![](figures/bt-recursive.png)

----

### Элегантная быстрая сортировка

![](figures/qsort.jpg)

```haskell
qsort [] = []
qsort (x:xs)
    = qsort (filter (\a -> a <= x) xs)
    ++ [x]
    ++ qsort (filter (\a -> a > x) xs)
```

*Questions:* достоинства и недостатки данной реализации?

----

### Advantages

- Allows safe sharing — no need for cloning operations
- Allows trivial roll back of changes e.g. undo operations, backtracking, handling exceptions
- Automatically safe from data races in concurrent / parallel programming
- Simpler GC and STM
- Recursive organisation and processing?

</div><div class="col">

### Disadvantages

- Higher worst-case complexity than the best imperative structures often incur a logarithmic overhead
- Not as well studied and documented
- Requires memory management (GC or ref counts)
- Causes more allocations (but not necessarily more residence)

</div></div>

----

*Question*: Как быть со строками?

---

## Алгебраический (индуктивный) тип данных

Тип данных, состоящий из нескольких различимых разновидностей (возможно, составных) термов (значений).

![](figures/illegal-state-unrepresentable.jpg)

----

```c
enum ShapeType { RECTANGLE, CIRCLE, TRIANGLE };

struct Rectangle {
    Point topLeft, bottomRight;
};

struct Circle {
    Point center;
    double radius;
};

struct Triangle {
    Point a,b,c;
};

union ShapeData {
    struct Rectangle rectangle;
    struct Circle circle;
    struct Triangle triangle;
};

struct Shape {
    enum ShapeType type;
    union ShapeData data;
}
```

</div><div class="col">

```haskell
data Shape
    = Rectangle
        { topLeft :: Point
        , bottomRight :: Point
        }
    | Circle
        { center :: Point
        , radius :: Double
        }
    | Triangle
        { a :: Point
        , b :: Point
        , c :: Point
        }
```

</div></div>

*Question*: Какие способы реализации вы видите в "обычных" языках?

----

### Представление JSON объектов

encode :: JSObject -> String
encode JSNull = "null"
encode (JSBool True) = "true"
encode (JSBool False) = "false"
encode (JSString s) = s
encode (JSArray xs) = show $ map encode xs

example = JSArray [ JSBool True, JSString "s" ]
main = putStrLn (encode example) -- => ["true","s"]
```

*Question*: Что такое $JSObject_1$ и $JSObject_2$ в определении типа?

----

### Maybe/Optional vs. nil

```haskell
data Maybe a = Just a | Nothing
type MaybeInt = Maybe Int
a = Just 12
b = Nothing
case _ of
  Just x -> x
  Nothing -> error "nothing"
```

$maybeint = (Int \times \\{ just \\}) \cup \\{ nothing \\}$

```clojure
(def a 12)
(def b nil)
```

$maybeint = Int \cup \\{ nil \\}$

```clojure
(let [flag (get-flag-value ...)]
  (when flag
    (process flag)))
```

---

## Структурная / <br/> вполне обоснованная рекурсия

Рекурсия, аргумент вызова в "меньше" аргумента исходного.

```haskell
data List a = Cons a (List a) | Empty

example = Cons 1 (Cons 2 (Cons 3 Empty))

length Empty = 0
length (Cons x xs) = 1 + length xs
```

- Если пуст (`Empty`) — вычисление окончено.
- Если список не пуст (`Cons`), то осуществим индуктивный переход для аргумента `Cons x xs -> xs`, тогда:
    - Если список конечен, то в нём присутствует `Empty` — вычисление окончено.
    - Если список бесконечен, алгоритм не завершится.

----

### Рекурсия vs. цикл

- Зависимость между шагами рекурсии явно определена.
- Обоснованная рекурсия -> конечный алгоритм. Некоторые языки требуют обоснованной рекурсии (Coq, Agda).
- Рекурсия позволяет естественно использовать динамическую память.
- Возможно ли обойти произвольное бинарное дерево в $O(1)$ по памяти?

```c
struct BTree {
    BTree * left;
    BTree * right;
    int value;
}
```

---

## Функции высших порядков

- в качестве аргументов получают функции
- в качестве результатов возвращают функции

Примеры использования:

- параметризация обобщённых функций (сортировка),
- декораторы (модифицируют стандартное поведение),
- комбинация функций вместо комбинации объектов,
- и т.п.

----

### Анонимные функции

Python

```python
lambda e: e + 1
(lambda e: e + 1)(1) # => 2
```

Haskell

```haskell
\x -> x + 1
(+1) -- with carry, see next slide
(\x -> x + 1) 1 -- => 2
```

Clojure

```clojure
(fn [x] (+ 1 x))
#(+ 1 %)
((fn [x] (+ 1 x)) 1) ;; => 2
```

*Возможно ли выразить рекурсию?*

----

### Карирование и композиция функций

```python
import functools

add = lambda a, b: a + b
inc = functools.partial(add, 1)

def comp(g, h):
    return lambda x: g(h(x))
inc2 = comp(inc, inc)

inc2(1) # => 3
```

```haskell
:t (+) -- => (+) :: Num a => a -> a -> a
:t (+ 1) -- => (+ 1) :: Num a => a -> a

inc = (+1)
inc2 x = inc (inc x)

(.) :: (b -> c) -> (a -> b) -> a -> c
g . h = \x -> g (h x)
inc2' = inc . inc
inc2' 1 -- # => 3
```

```clojure
(def inc (partial + 1))
((comp inc inc) 1) ; => 3
```

----

#### Фильтрация (Python)

```python
def myfilter(pred, lst):
  acc = []
  for e in lst:
    if pred(e):
      acc.append(e)
  return acc
```

```python
x = myfilter(lambda e: e % 2 == 1, [1,2,3])
x # => [1, 3]
x # => [1, 3]
```

----

#### Фильтрация с генератором (Python)

```python
def myfilter2(pred, lst):
  for e in lst:
    if pred(e):
      yield e
```

В чём отличие генератора от списка/массива/т.п.?

```python
x = myfilter2(lambda e: e % 2 == 1, [1,2,3])
x # => <generator object myfilter2 at 0x7fe747a61e40>
list(x) # => [1, 3]
list(x) # => []
```

----

#### Фильтрация на Haskell

```haskell
filter pred [] = []
filter pred (x:xs)
    | pred x = x : filter pred xs
    | otherwise = filter pred xs

filter2 pred xs =
    if null xs
    then []
    else if pred x
         then x : filter pred xs
         else filter pred xs

head (x:_) = x
head [] = error "head from empty list"
-- f $ g x <=> f (g x)
```

```haskell
head $ filter even [1..9] -- => 2
head $ filter even [1..] -- => 2
```

Почему не зависнет?

----

#### Фильтрация на Haskell. Лень

```haskell
head $ filter even [1..9] =>
head $ filter even (1 : [2..9]) =>
head $ if even 1 then 1 : (filter even [2..9])
.................else      filter even [2..9] =>
head $ if false  then 1 : (filter even [2..9])
.................else      filter even [2..9] =>
head $ filter even (2 : [3..9]) =>
head $ if even 2 then 2 : (filter even [3..9])
.................else      filter even [3..9] =>
head $ if true   then 2 : (filter even [3..9])
.................else      filter even [3..9] =>
head $ 2 : (filter even [3..9]) =>
2
```

- Haskell — лениво любое значение.
- Ленивая коллекция — в первую очередь коллекция.
- Генератор значений — в первую очередь генератор, а не коллекция.

---

## Отображения и свёртки

![](figures/map-filter-reduce-joke.jpg)

----

### Императивные отображения

```python
def map(f, lst):
    acc = []
    for e in lst:
        acc.append(f(e))
    return acc
```

```python
def map(f, lst):
    for e in lst:
        yield f(e)
```

</div><div class="col">

![](figures/map.png)

</div></div>

----

#### Функциональное отображение

```haskell
map _ [] = []
map f (x:xs) = f x : map f xs
```

где `:` — добавление к списку новой головы.

Пример 1

```haskell
1 : [2, 3] =>
[1, 2, 3]
```

Пример 2

```haskell
map inc (0:1:[]) =>
inc 0 : map inc (1:[]) =>
inc 0 : inc 1 : [] =>
1 : 2 : []
```

----

### Свертки

![](figures/foldings.png)

</div><div class="col">

```python
def reduce(f, init, lst):
    acc = init
    for e in lst:
        acc = f(acc, e)
    return acc

reduce(
    lambda a, b: a + b,
    0,
    [1,2,3])
```

</div></div>

```haskell
foldl :: (s -> a -> s) -> s -> [a] -> s
foldl _ _ [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

foldl (+) 0 [1,2,3]
```

*Функции `map`, `fold`, `filter` позволяют скрыть структуру данных.*

----

### Map-Reduce

![](figures/map-reduce.png)

</div><div class="col">

Трудности реализации:

<div>

- обработка ошибок
- проблема остановки/отмены
- консистентность
- отказ узлов

</div>

</div></div>

---

## Замыкания (Closure)

<dl>
  <dt> Closure (lexical closure or function closure) </dt>
  <dd>  is a technique for implementing lexically scoped name binding in a language with first-class functions. </dd>
</dl>
 
![](figures/closure-everywhere.jpeg)

А какие ещё бывают scope-ы?

----

### Чистые замыкания

```python
weekdays = {
    0: 'Sunday',
    1: 'Monday',
    2: 'Tuesday',
    3: 'Wednesday',
    4: 'Thursday',
    5: 'Friday',
    6: 'Saturday',
    7: 'Sunday',
}

def n2weekdayName(n):
    return weekdays[n]

workdays = [1, 2, 3, 4, 5]

print(list(map(n2weekdayName, workdays)))
# => ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']
```

----

### Чистые замыкания, сортировка

```python
def itemSort(items, price):
    return sorted(items, key=lambda x: abs(price - x))
```

Динамический тип функции.

```go
sort.Slice(items, func(i, j int) bool {
    return math.Abs(items[i]) > math.Abs(items[j])
})
```

Статический тип функции.

----

### Грязные замыкания

```python
def mk_counter(begin=0):
    i = begin
    def counter():
        nonlocal i
        tmp = i
        i += 1
        return tmp
    return counter

c1 = mk_counter(0)
c2 = mk_counter(10)

print(c1(), c1(), c2(), c2(), c1()) # => 0 1 10 11 2
```

----

### ООП как обычно

```python
class DogByClass(object):
    def __init__(self, name, age):
        self.name = name
        self.age = age
    def description(self):
        return '{} is {} years old'.format(self.name, self.age)
    def speak(self, sound):
        return '{} says {}'.format(self.name, sound)
    def happy_birth_day(self):
        self.age += 1

d1 = DogByClass("Fluffy", 1)

print(d1.description())  # Fluffy is 1 years old
print(d1.speak("woof"))  # Fluffy says woof
d1.happy_birth_day()
print(d1.description())  # Fluffy is 2 years old
```

----

### ООП через замыкания, Python

```python
def DogByClosure(name, age):
    def description():
        return '{} is {} years old'.format(name, age)
    def speak(sound):
        return '{} says {}'.format(name, sound)
    def happy_birth_day():
        nonlocal age
        age += 1
    return {
        'description': description,
        'speak': speak,
        'happy_birth_day': happy_birth_day,
    }

d2 = DogByClosure("Buddy", 1)
print(d2['description']())  # Buddy is 1 years old
print(d2['speak']("bark"))  # Buddy says bark
d2['happy_birth_day']()
print(d2['description']())  # Buddy is 2 years old
```

----

### ООП через замыкания, Clojure

```clojure
(defn dog [name age]
  (let [*age (atom age)]
    {:description #(str name " is " @*age " years old")
     :speak #(str name " says " %)
     :happy-birth-day #(swap! *age + 1)}))

(def d (dog "Skippy" 1))

((:description d))      ; => "Skippy is 1 years old"
((:happy-birth-day d))  ; => 2
((:description d))      ; => "Skippy is 2 years old"
((:speak d) "bork")     ; => "Skippy says bork"

(defmacro => [obj method & args]
  `((~method ~obj) ~@args))

(macroexpand '(=> d :speak "bork")) ; => ((:speak d) "bork")

(=> d :speak "bork")    ; =>"Skippy says bork"
```

- `atom` — примитив синхронизации. Хранение изменяемого состояния. Гарантирует атомарность изменений.

----

### ООП через процессы и сообщения, Erlang

```erlang
start(Name, Age) ->
    spawn(fun() -> loop(Name, Age) end).

loop(Name, Age) ->
  receive
    {description, From} ->
      From ! {self(), io:format("~s is ~p years old", [Name, Age])},
      loop(Name, Age);
    {speak, Sound, From} ->
      From ! {self(), io:format("~s says ~s", [Name, Sound])},
      loop(Name, Age);
    {happy_birth_day, From} ->
      NewAge = Age + 1,
      From ! {self(), NewAge},
      loop(Name, NewAge)
  end.
```

</div><div class="col">

```erlang
description(Dog) ->
    Dog ! {description, self()},
    receive {Dog, Msg} -> Msg end.

speak(Dog, Sound) ->
    Dog ! {speak, Sound, self()},
    receive {Dog, Msg} -> Msg end.

happy_birth_day(Dog) ->
    Dog ! {happy_birth_day, self()},
    receive {Dog, NewAge} -> NewAge end.
```

</div></div>

```erlang
Dog = start("Buddy", 1), % => <0.93.0>
description(Dog),      % => Buddy is 1 years old__ok
speak(Dog, "bark"),    % => Buddy says bark__ok
happy_birth_day(Dog),  % => 2
description(Dog).      % => Buddy is 2 years old__ok
```

---

## Бесточечный стиль, комбинаторы

Комбинаторное программирование — парадигма программирования, не требующая явного упоминания аргументов определяемых функций и использующая вместо переменных комбинаторы и их композиции.

----

### Java streams

```java
Stream.of("a1", "a2", "a3")
    .map(s -> s.substring(1))
    .mapToInt(Integer::parseInt)
    .max()
    .ifPresent(System.out::println);  // => 3
```

```java
List<Person> persons =
    Arrays.asList(
        new Person("Max", 18),
        new Person("Peter", 23),
        new Person("Pamela", 23),
        new Person("David", 12));

String phrase = persons
    .stream()
    .filter(p -> p.age >= 18)
    .map(p -> p.name)
    .collect(Collectors.joining(
        " and ",
        "In Germany ",
        " are of legal age."));

System.out.println(phrase);
// => In Germany Max and Peter and Pamela are of legal age.
```

Notes: <https://winterbe.com/posts/2014/07/31/java8-stream-tutorial-examples/>

----

### Бесточечный стиль, <br/> комбинаторы в Haskell

```haskell
foldl (+) 0 . map (\Just x -> x) . filter isJust . map readMaybe
```

где:

- `readMaybe` — пытаемся преобразовать строку в значение заданного типа. Пример:
    - `readMaybe "1" :: Maybe Int <=> Just 1`
    - `readMaybe "f" :: Maybe Int <=> Nothing`
- `(.)` — комбинация функций (`f x = g(h(x)) <=> f = g . h`)
- `\x -> ...` —  анонимная функция от одного аргумента

----

### Трансдьюсеры

Transducers are composable algorithmic transformations. They are independent from the context of their input and output sources and specify only the essence of the transformation in terms of an individual element.

```clojure
(fn [coll]
  (->> coll
       (filter #(re-matches #"^\d+$" %))
       (map #(Integer/parseInt %))
       (reduce +)))
```

</div><div class="col">

```clojure
(defn try-int [s]
  (when (re-matches #"^\d+$" %)
    (Integer/parseInt %)))
(fn [coll]
  (->> coll
       (keep try-int)
       (reduce +)))
```

</div></div>

где:

- `(fn [x] ...)` и `#(... % ...)` — анонимные функции
- `re-match` — проверка регулярного выражения
    - `(re-matches #"^\d+$" "1") <=> "1"`
    - `(re-matches #"^\d+$" "a") <=> nil`

----

### Threading Macros (Clojure)

`->`

```clojure
(defn transform* [person]
   (-> person
       (assoc :hair-color :gray)
       (update :age inc)))
```

```clojure
(defn transform* [person]
   (-> person
       (assoc  ,,, :hair-color :gray)
       (update ,,, :age inc)))
```

```clojure
(some-> x try-int inc)
```

</div><div class="col">

`->>`

```clojure
(defn calculate* []
   (->> (range 10)
        (filter odd?)
        (map #(* % %))
        (reduce +)))
```

```clojure
(defn calculate* []
   (->> (range 10)
        (filter odd?     ,,,)
        (map    #(* % %) ,,,)
        (reduce +        ,,,)))
```

</div></div>

----

**Джон Бэкус**. Можно ли освободить программирование от стиля фон Неймана? Функциональный стиль и алгебра программ

![](figures/backus-example-combinators.png)

Объясните алгоритм?

![](figures/backus-example-von-neumann.png)

---

## Рекурсия и вычислительная сложность

```haskell
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
```

*Question*: В чём проблема реализации?

<div>

![](figures/fib-compelixity.png)

</div><div class="col">

$O(\phi n)$

$\phi = 1 + \sqrt{\frac{5}{2}}$.

</div></div>

</div>

----

### Мемоизация. Python. Библиотека

Сохранение результатов выполнения функций для предотвращения повторных вычислений.

```python
import time

def dur(f):
    t = time.time()
    x = f()
    print("dur: ", time.time()-t)
    return x

def fib(n):
    if n == 0 or n == 1: return 1
    return fib(n-1) + fib(n-2)

dur(lambda: fib(32)) # => dur:  1.2896251678466797

import functools
fib = functools.cache(fib)

dur(lambda: fib(32)) # => dur:  2.8848648071289062e-05
```

----

### Мемоизация. Python. Реализация

```python
def mycache(f):
    buf = {}
    def foo(x):
        if x in buf: return buf[x]
        tmp = f(x)
        buf[x] = tmp
        return tmp
    return foo

@mycache
def fib(n):
    if n == 0 or n == 1: return 1
    return fib(n-1) + fib(n-2)

# def fib(n):
#     ...
# fib = mycache(fib)

dur(lambda: fib(32)) # => dur:  0.00015401840209960938
```

----

### Мемоизация. Haskell

```haskell
fib n = fiblist !! n
  where
    fiblist = 1 : 1 : ( zipWith (+) fiblist (tail fiblist) )
```

*Question*: Как данный пример работает?

```haskell
fiblist = 1 : 1 : ( zipWith (+) fiblist
................................(tail fiblist) )
fiblist = 1 : 1 : ( zipWith (+) [ 1 : 1 ...
................................[ 1 : ...
..................................\-> 2

fiblist = 1 : 1 : ( zipWith (+) [ 1 : 1 : 2...
................................[ 1 : 2 :...
......................................\-> 3

fiblist = 1 : 1 : ( zipWith (+) [ 1 : 1 : 2 : 3 ...
................................[ 1 : 2 : 3 ...
..........................................\-> 5
```

---

## Ссылочная прозрачность

An expression is called **referentially transparent** if it can be replaced with its corresponding value (and vice-versa) without changing the program's behavior.

![](figures/r-reference-transperency.png)

Одинаково $\rightarrow$ взаимозаменяемо.

----

### Проверка на равенство. Разночтения

<div>

- `=` compares only numbers, regardless of type.
- `eq` compares symbols. Two objects are `eq` if they are actually the same object in memory. Don't use it for numbers and characters.
- `eql` compares symbols similarly to `eq`, numbers (type sensitive) and characters (case sensitive)
- `equal` compares more general objects. Two objects are `equal` if they are `eql`, strings of `eql` characters, bit vectors of the same contents, or lists of `equal` objects. For anything else, `eq` is used.
- `equalp` is like `equal`, just more advanced. Comparison of numbers is type insensitive. Comparison of chars and strings is case insensitive. Lists, hashes, arrays and structures are `equalp` if their members are `equalp`. For anything else, `eq` is used.

это Common Lisp. JS — всё понятно. А в Python?

</div>

----

#### Равенство в Python

```python
x = 0
y = 0
while True:
    x += 1
    y += 1
    print(x, y, x is y, x == y)
    if x is not y:
        break
# => 1 1 True True
# => 2 2 True True
# => ...
# => 256 256 True True
# => 257 257 False True
```

----

#### Замыкания в Python

```python
def create_functions():
    funcs = []
    for i in range(4):
        funcs.append(lambda: i)
    return funcs

funcs = create_functions()

for f in funcs:
    print(f())
```

Ожидаемый вывод?

</div><div class="col">

```python
def create_functions_fixed():
    funcs = []
    for i in range(4):
        funcs.append(lambda i=i: i)
    return funcs

funcs = create_functions_fixed()

for f in funcs:
    print(f())
```

</div></div>

----

#### Примеры эквивалентности <br/> при ссылочной прозрачности

```python
a = [1, 2, 3]
b = [1, 2, 3]

c = {:a 1 :b 2}
d = {:a 1 :b 2}
```

</div><div class="col">

```python
a = [1, 2, 3]
b = a

c = {:a 1 :b 2}
d = c
```

</div></div>

```python
a = f(x)
b = f(x)
c = a + b
```

</div><div class="col">

```python
a = f(x)
c = a + a
```

</div></div>

Подстановка выражение, убирание дублирования.

----

```c
for (int x = 0; x < 100; x++) {
    delete(x);
}
```

</div><div class="col">

```c
for (int x = 0; x < 100; x += 5 ) {
    delete(x);
    delete(x + 1);
    delete(x + 2);
    delete(x + 3);
    delete(x + 4);
}
```

</div></div>

Loop unrolling

```python
def foo(p, a, b):
    if p(a):
        return b

foo(is_even, x, bar(x))
```

</div><div class="col">

```python
def foo(p, a, b):
    if p(a):
        return bar(x)

foo(is_even, x, x)
```

</div></div>

Reordering

----

```python
def double(x): return x + x

def quadruple(x): return double(double(x))
```

```python
def double(x): return 2 * x

def quadruple(x): return 2 * double(x)
```

```python
def quadruple(x): return 2 * 2 * x
```

```python
def quadruple(x): return 4 * x

print(quadruple(3))  # ==> 12
```

Лёгкий намёк на суперкомпиляцию.

----

И драматизация в рамках параллельного программирования:

![](figures/reference-transperancy.png)

----

### Сопоставление с образцом

```haskell
reverse xs = reverse' xs []
  where
    reverse' [] acc = acc
    reverse' (x:xs) acc = reverse' xs (x:acc)
```

</div><div class="col">

```text
reverse (1:2:[]) =>
reverse' (1:2:[]) [] =>
reverse' (2:[]) (1:[]) =>
reverse' (2:[]) (1:[]) =>
reverse' [] (2:1:[]) =>
(2:1:[])
```

</div></div>

```erlang
is_z_atom(z) -> true;
is_z_atom(_) -> false.
% is_z_atom(z). % => true
% is_z_atom(123). % => false

is_equal(X, X) -> true;
is_equal(_, _) -> false.
% is_equal(1, 2) % => false.
% is_equal(1, 1)% => true.
```

</div><div class="col">

```clojure
(require '[clojure.core.match :refer [match]])

(doseq [n (range 1 101)]
  (println
    (match [(mod n 3) (mod n 5)]
      [0 0] "FizzBuzz"
      [0 _] "Fizz"
      [_ 0] "Buzz"
      :else n)))
```

</div></div>

----

```clojure
(def x (map #(throw %) (range 1000)))
; (prn x) ?
```

```clojure
(prn x) ; => Execution error ... (
; (prn x) ?
```

```clojure
(prn x) ; => ()

(def y (map #(if (= % 40) (throw %) %) (range 100)))
; (prn x)
; (prn x) ?
```

```clojure
(prn y) ; => Execution error ... (0 1 2 ...... 27 28 29 30
(prn y) ; => (0 1 2 3 4 5 6 7 8 9 10 11 ...... 27 28 29 30 31)

(let [z (map #(if (= % 2) (throw %) %) [1 2 3])]
  (.start (Thread. #(doall z)))
  (Thread/sleep 100)
  z)
; Return or exception?
```

```clojure
; => ()
```