Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Алгебраические структуры

1. Полугруппа (Semigroup)

Полугруппа это базовая алгебраическая структура, которая используется в коллекциях, редьюсах (fold, sum, product, concat, collect, join, group, aggregate), параллелизме и агрегировании.

Полугруппа = тип + бинарная операция, которая:

  • замкнута: результат операции снова того же типа
  • ассоциативна: (a ⋆ b) ⋆ c = a ⋆ (b ⋆ c)

Коммутативность: (90% комбинаторного взрыва одним свойством, порядок событий нам больше не важен)

A + B = B + A

a.merge(&b) == b.merge(&a)

Ассоциативность: (9% комбинаторного взрыва, защищает от разных "группировок" событий)

(A + B) + C = A + (B + C)

(a.merge(b)).merge(c) == a.merge(b.merge(c))

Ассоциативные операции: Числа + сложение и * умножение, Max/Min, Строки + конкатенация

(1 + 2) + 3 = 1 + (2 + 3) = 6 => Совпадают

(1 * 2) * 3 = 1 * (2 * 3) = 6 => Совпадают

max(max(a,b),c) = max(a,max(b,c))

("a" + "b") + "c" = "a" + ("b" + "c")

use rayon::prelude::*;

fn main() -> std::io::Result<()> {
    let data = [1,2,3];

    /*
        Ассоциативно, можно разбить на полугруппы
        Потому что движок рандомно разбивает коллекцию:

        ((a + b) + (c + d)) + (e + f)
    */
    let res = data.par_iter().cloned().reduce(|| 1,  |a, b| a + b);// (1+1)+(1+2)+(1+3)=2+3+4=9

    /*
        Ассоциативно, можно разбить на полугруппы
        Потому что движок рандомно разбивает коллекцию:

        ((a ⋆ b) ⋆ (c ⋆ d)) ⋆ (e ⋆ f)
    */
    let res = data.par_iter().cloned().reduce(|| 1,  |a, b| a * b);// (1*1)*(1*2)*(1*3)=1+2+3=6

    // Не ассоциативно (нет полугруппы)
    let res = data.par_iter().cloned().reduce(|| 1,  |a, b| a / b);// Error: attempt to divide by zero

    // Не ассоциативно (нет полугруппы)
    let res = data.par_iter().cloned().reduce(|| 1,  |a, b| a - b);// -1
 

    Ok(())
}

Если операция ассоциативна её можно:

  • параллелить
  • распределять
  • безопасно редьюсить
  • кешировать
  • использовать в SQL GROUP
  • использовать в логировании
  • использовать для мерджа данных

Не ассоциативные операции: Числа - разность (вычитание), / деление

Если ассоциативность не выполняется → результат непредсказуемый:

(5 - 3) - 1 = 1  и  5 - (3 - 1) = 3  => Не совпадают


(100/10)/2=10/2=5 и 100/(10/2)=100/5=20  => Не совпадают

Такие операции нельзя использовать:

  • в параллельных reduce
  • в map-reduce
  • в SQL GROUP BY
  • в агрегатных функциях

2. Моноид (Monoid)

Моноид = полугруппа + нейтральный элемент

Моноид сам по себе "ничего не меняет" при одном применении (нейтральный элемент не влияет на результат), но именно это свойство делает его необходимым для корректного объединения частичных результатов — в том числе в параллельных и распределённых вычислениях.

Моноид является фундаментом всех reduce, fold, merge, accumulate, join.

Для ассоциативной операции сложения, полугруппа a + b то моноид это число 0 так как он ничего не менят: a + 0 = a

Для ассоциативной операции умножения, полугруппа a * b то моноид это число 1 так как он ничего не менят: a * 1 = a

Для ассоциативной операции конкатенации строк, полугруппа s1 + s2 то моноид это пустая строка "" так как она ничего не менят: s1 + "" = s1

Для ассоциативной операции расширения массива, полугруппа arr1 + arr2 то моноид это пустой массив [] так как он ничего не менят: arr1 + [] = arr1

use rayon::prelude::*;

fn main() -> std::io::Result<()> {
    let data = [1,2,3];
    let monoid = 0;
    let res = data.par_iter().cloned().reduce(|| monoid,  |a, b| a + b);// (0+1)+(0+2)+(0+3)=1+2+3=6

    // т.е. начать то надо с чего-то, и правильный monoid это решает

    let data = [1,3,4];
    let monoid = 1;
    let res = data.par_iter().cloned().reduce(|| 1,  |a, b| a * b);// (1*1)*(1*3)*(1*4)=1*3*4=12
    
    // Строки (конкатенация)
    let mut s1 = String::from("Rust");
    let mut monoid = String::from("");
    s1.push_str(&monoid);
    assert_eq!(s1, "Rust");
     
    // Массивы (конкатенация)
    let mut v1 = [1,2,3].to_vec();
    let monoid: Vec<i32> = [].to_vec();
    v1.extend(monoid);
    assert_eq!(v1, [1,2,3].to_vec());

    // операция: &&
    // monoid true
    let monoid = true;
    let mut a = false;
    assert_eq!(a && monoid, a);
    a = true;
    assert_eq!(a && monoid, a);

    // операция: ||
    // monoid false
    let monoid = false;
    let mut a = false;
    assert_eq!(a || monoid, a);
    a = true;
    assert_eq!(a || monoid, a);

    Ok(())
}

Морачивать моноиды на тип = значит сделать его foldable/reducible

Если тип — моноид, то над ним:

  • можно делать reduce
  • можно делать fold с identity
  • можно объединять в любом порядке
  • можно распараллеливать reduce
  • можно распределять merge между нодами
  • можно безопасно мерджить логи/события
  • можно оптимизировать SQL
  • можно делать MapReduce
fn main() -> std::io::Result<()> {
    // Для операции сложения моноидом является 0, но если мы возьмем другое значение:
    // если тип НЕ моноид — мы не можем корректно fold-нуть пустую коллекцию.
    let arr = [];
    let monoid = 1;
    let res = arr.iter().fold(monoid, |a,b| a + b);
    assert_eq!(res, 1);// 1 !
  
    Ok(())
}

3. Группа

Группа = моноид + обратимость

Группа — это такая система операций, где любую операцию можно “отменить”.

Если система позволяет вычитать последствия операции (отменять её), то под этим лежит групповая структура.

Группа = (A, ⊕, e)

если:
1) (A, ⊕) — ассоциативная операция
2) e — нейтральный элемент
3) для каждого a ∈ A существует обратный элемент a⁻¹ такой, что:
   a ⊕ a⁻¹ = e
   a⁻¹ ⊕ a = e

Группа: Целые числа с операцией сложения + (Целые числа с умножением — НЕ группа)

Группа = (i32, +, 0)

A = Z (все целые)
Операция = +
Нейтральный = 0
Обратный элемент = -a
 
Проверка:
5 + (-5) = 0 
 
let pos2 = pos1 + delta;
let pos1 = pos2 + (-delta);

Группа: Мультипликативная группа * дробных чисел (f64≠0)

В группе обратимость означает, что для любого элемента 'a' существует a⁻¹, такой что:
Нейтральный = 1
a * a⁻¹ = 1
a⁻¹ * a = 1



A = R\{0} (все дробные числа кроме 0)
Операция = *
Нейтральный = 1
Обратный элемент = 1/a

Проверка:
2 * 1/2 = 1
0.5 * 2 = 1

fn multiplicative_group_example(a: f64) {
    let inverse = 1.0 / a;       // обратный элемент
    let prod1 = a * inverse;     // a * a⁻¹
    let prod2 = inverse * a;     // a⁻¹ * a
    println!("a = {}", a);
    println!("Обратный элемент a⁻¹ = {}", inverse);
    println!("a * a⁻¹ = {}", prod1);
    println!("a⁻¹ * a = {}", prod2);
}

fn main() {
    multiplicative_group_example(2.0);
    multiplicative_group_example(0.5);
}
a = 2
Обратный элемент a⁻¹ = 0.5
a * a⁻¹ = 1
a⁻¹ * a = 1

a = 0.5
Обратный элемент a⁻¹ = 2
a * a⁻¹ = 1
a⁻¹ * a = 1

Группа: Булева группа по XOR

(bool, XOR, false) — булева группа

любая операция с обратным элементом возвращает нейтральный (false)

A = {true, false}
Операция = XOR (^)
Нейтральный = false
Обратный элемент = a

fn xor_group_example(a: bool) {
    let inverse = a;                 // обратный элемент в XOR — сам элемент
    let prod1 = a ^ inverse;         // a ⊕ a⁻¹
    let prod2 = inverse ^ a;         // a⁻¹ ⊕ a
    println!("a = {}", a);
    println!("Обратный элемент a⁻¹ = {}", inverse);
    println!("a ^ a⁻¹ = {}", prod1);
    println!("a⁻¹ ^ a = {}", prod2);
}

fn main() {
    xor_group_example(true);
    xor_group_example(false);
}
a = true
Обратный элемент a⁻¹ = true
a ^ a⁻¹ = false
a⁻¹ ^ a = false

a = false
Обратный элемент a⁻¹ = false
a ^ a⁻¹ = false
a⁻¹ ^ a = false

Группа: Группа множеств по симметрической разности

(HashSet, △, ∅) — группа множеств

A = все множества (HashSet)
Операция = симметрическая разность (A △ B)
Нейтральный = ∅
Обратный элемент = A (само множество)

use std::collections::HashSet;

fn symmetric_difference_group_example(a: HashSet<i32>) {
    let inverse = a.clone();  // обратный элемент — само множество
    let prod1: HashSet<_> = a.symmetric_difference(&inverse).cloned().collect(); // A △ A
    let prod2: HashSet<_> = inverse.symmetric_difference(&a).cloned().collect(); // A △ A
    println!("A = {:?}", a);
    println!("Обратный элемент A⁻¹ = {:?}", inverse);
    println!("A △ A⁻¹ = {:?}", prod1);
    println!("A⁻¹ △ A = {:?}", prod2);
}

fn main() -> std::io::Result<()> { 
    let a: HashSet<_> = [1, 2, 3].into_iter().collect();
    symmetric_difference_group_example(a);
     
    Ok(())
}
A = {2, 3, 1}
Обратный элемент A⁻¹ = {2, 3, 1}
A △ A⁻¹ = {}
A⁻¹ △ A = {}

Пример: механизм отката транзакция в БД основан на группах.

Транзакция делает набор изменений:

x = x + 10
y = y - 3
insert row
update price 100 → 90
delete id=5

И если что-то пошло не так — база должна выполнить:

x = x - 10
y = y + 3
delete row (обратное вставке)
update price 90 → 100 (инверсия)
insert id=5 (обратное удалению)

То есть у каждой операции есть обратная операция.

(a ⊕ b ⊕ c) ⊕ (c⁻¹ ⊕ b⁻¹ ⊕ a⁻¹) = e

где:

  • ⊕ — применение операции
  • e — состояние базы до транзакции
  • a⁻¹ — обратная операция

4. Кольцо

Кольцо = группа по сложению + моноид по умножению + распределение

Кольцо = структура, где есть две операции:

  • Сложение → образует группу
  • Умножение → образует моноид (Умножение распределяется относительно сложения.)

Кольцо — это тип данных или структура, в которой определены две операции: складывать и умножать, и они хорошо взаимодействуют.

Типичный пример:

  • i32
  • i64
  • BigInt
  • матрицы
  • векторы
  • булевы значения (с особыми операциями)
  • многочлены
  • интервалы
(Z, +, *, 0, 1)

по сложению все целые образуют группу

по умножению — моноид (но НЕ группу, т.к. нет обратимости 1/0)

распределение умножения над сложением:

a*(b+c) = ab + ac

Кольцо — это просто набор правил (операций), и эти правила можно реализовать для других типов — например, для матриц. Тогда операции + и * для матриц подчиняются тем же законам (аддитивная группа + мультипликативный моноид + дистрибутивность) — значит матрицы образуют кольцо. И потому общие алгоритмы, написанные для «произвольного кольца», автоматически работают и с матрицами.


// Cargo.toml
// [dependencies]
// num-traits = "0.2"

/*

Почему это важно:
— матрицы с обычным сложением и умножением образуют кольцо. 
Значит все алгоритмы, которые делаются «для любого кольца» — будут работать и для матриц. 
Мы ничего «нового» не придумываем: мы просто реализуем + и * в терминах базового типа T (значений в ячейке матрицы).

Как poly_eval общая:
— он требует, чтобы тип T поддерживал Add, Mul, Zero и Copy. 
Неважно, что это за T: скаляр, матрица, полином, комплекс — Horner’ом можно вычислить полином над любой алгебраической структурой, куда определены + и *.

Как использовать полином с матрицей и скалярными коэффициентами:
— у еас есть два подхода:

- поднимать скаляры в матричный вид (скаляр * I) и передавать массив коэффициентов-матриц в poly_eval (как я показал);

- написать poly_eval_scalar_coeffs(coeffs: &[S], x: M) где мы в цикле используем coeff * I автоматически (требуется One и скаляр-умножение матрицы).

Производительность: матричное умножение дорогое (O(n³)). Но семантика работает на любом кольце.
*/
use num_traits::{Zero, One};
use std::ops::{Add, Mul};
use std::fmt;

// Простая реализация квадратной матрицы n x n, хранится в row-major Vec<T>
#[derive(Clone, PartialEq)]
pub struct Matrix<T> {
    n: usize,
    data: Vec<T>,
}

impl<T> Matrix<T> {
    pub fn new(n: usize, data: Vec<T>) -> Self {
        assert!(data.len() == n * n);
        Matrix { n, data }
    }

    pub fn zeros(n: usize) -> Self
    where
        T: Zero + Clone,
    {
        Matrix { n, data: vec![T::zero(); n * n] }
    }

    pub fn identity(n: usize) -> Self
    where
        T: Zero + One + Clone,
    {
        let mut d = vec![T::zero(); n * n];
        for i in 0..n {
            d[i * n + i] = T::one();
        }
        Matrix { n, data: d }
    }

    #[inline] fn idx(&self, r: usize, c: usize) -> usize { r * self.n + c }

    pub fn get(&self, r: usize, c: usize) -> &T { &self.data[self.idx(r,c)] }
    pub fn set(&mut self, r: usize, c: usize, v: T) { let i = self.idx(r,c); self.data[i] = v; }
    pub fn size(&self) -> usize { self.n }
}

// Display для удобства
impl<T: fmt::Debug> fmt::Debug for Matrix<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for r in 0..self.n {
            writeln!(f, "{:?}", &self.data[r*self.n..(r+1)*self.n])?;
        }
        Ok(())
    }
}

// Сложение матриц: элемент-по-элементу
impl<T> Add for Matrix<T>
where
    T: Add<Output = T> + Clone,
{
    type Output = Matrix<T>;
    fn add(self, rhs: Matrix<T>) -> Matrix<T> {
        assert!(self.n == rhs.n);
        let data = self.data.into_iter().zip(rhs.data.into_iter())
            .map(|(a,b)| a + b).collect();
        Matrix::new(self.n, data)
    }
}

// Умножение матриц (обычное O(n^3))
impl<T> Mul for Matrix<T>
where
    T: Zero + Add<Output = T> + Mul<Output = T> + Clone,
{
    type Output = Matrix<T>;
    fn mul(self, rhs: Matrix<T>) -> Matrix<T> {
        assert!(self.n == rhs.n);
        let n = self.n;
        let mut out = vec![T::zero(); n * n];
        for i in 0..n {
            for j in 0..n {
                let mut acc = T::zero();
                for k in 0..n {
                    let a = self.data[i*n + k].clone();
                    let b = rhs.data[k*n + j].clone();
                    acc = acc + a * b;
                }
                out[i*n + j] = acc;
            }
        }
        Matrix::new(n, out)
    }
}

// Zero/One для Matrix оставим, но они не используются для создания матрицы конкретного размера без контекста
impl<T> Zero for Matrix<T>
where
    T: Zero + Clone,
{
    fn zero() -> Self { Matrix::zeros(0) } // не используем этот zero() для алгоритмов над матрицами
    fn is_zero(&self) -> bool {
        self.data.iter().all(|x| x.is_zero())
    }
}

impl<T> One for Matrix<T>
where
    T: Zero + One + Clone,
{
    fn one() -> Self { Matrix::identity(0) } // не используем
}

// Операции по ссылкам (чтобы не двигать)
impl<T> Add<&Matrix<T>> for &Matrix<T>
where
    T: Add<Output = T> + Clone,
{
    type Output = Matrix<T>;
    fn add(self, rhs: &Matrix<T>) -> Matrix<T> {
        assert!(self.n == rhs.n);
        let data = self.data.iter().cloned().zip(rhs.data.iter().cloned()).map(|(a,b)| a + b).collect();
        Matrix::new(self.n, data)
    }
}
impl<T> Mul<&Matrix<T>> for &Matrix<T>
where
    T: Zero + Add<Output = T> + Mul<Output = T> + Clone,
{
    type Output = Matrix<T>;
    fn mul(self, rhs: &Matrix<T>) -> Matrix<T> {
        assert!(self.n == rhs.n);
        let n = self.n;
        let mut out = vec![T::zero(); n * n];
        for i in 0..n {
            for j in 0..n {
                let mut acc = T::zero();
                for k in 0..n {
                    let a = self.data[i*n + k].clone();
                    let b = rhs.data[k*n + j].clone();
                    acc = acc + a * b;
                }
                out[i*n + j] = acc;
            }
        }
        Matrix::new(n, out)
    }
}

// Полезная функция: умножение скаляр * матрица (скаляр слева)
fn scalar_mul_matrix<T>(c: &T, m: &Matrix<T>) -> Matrix<T>
where
    T: Clone + Mul<Output = T> + Zero,
{
    let data = m.data.iter().cloned().map(|x| c.clone() * x).collect();
    Matrix::new(m.n, data)
}

// Horner, но инициализируем res последним коэффициентом, чтобы не требовать T::zero() для Matrix
fn poly_eval<T>(coeffs: &[T], x: T) -> T
where
    T: Clone + Add<Output = T> + Mul<Output = T>,
{
    assert!(!coeffs.is_empty(), "poly_eval: coeffs must be non-empty");
    let mut res = coeffs[coeffs.len()-1].clone();
    if coeffs.len() == 1 { return res; }
    for c in coeffs[..coeffs.len()-1].iter().rev() {
        res = res * x.clone() + c.clone();
    }
    res
}

fn main() {
    // scalar example
    let coeffs_scalar = [3i32, 2, 1]; // 1*x^2 + 2*x + 3
    let x_scalar = 2i32;
    let s = poly_eval(&coeffs_scalar, x_scalar);
    println!("p(2) = {:?}", s); // 11

    // matrix example
    let a = Matrix::new(2, vec![0i32, 1, 0, 0]);

    // build 3*I, 2*I, 1*I manually (coefficients must be Matrix<i32> because x is Matrix<i32>)
    let mut three_i = Matrix::identity(2);
    three_i.data.iter_mut().for_each(|v| *v = *v * 3i32);
    let mut two_i = Matrix::identity(2);
    two_i.data.iter_mut().for_each(|v| *v = *v * 2i32);
    let one_i = Matrix::identity(2);

    let coeffs_matrix = [three_i.clone(), two_i.clone(), one_i.clone()]; // corresponds to 1*A^2 + 2*A + 3*I
    let p_a = poly_eval(&coeffs_matrix, a.clone());  
    println!("p(A) = \n{:?}", p_a);
}
/*
Кольцо — это тип, на котором есть сложение и умножение.
Полином можно вычислять на любом элементе кольца.


Случай обычных чисел (кольцо ℤ)

    Полином: p(x) = x² + 2x + 3

    при x = 2:

    p(2) = 4 + 4 + 3 = 11


Случай матрицы: то же кольцо, но другой объект

    Мы подставили в тот же полином матрицу:
    A = [0 1]
        [0 0]
        
    и получили:    
    p(A) = A² + 2A + 3I =
        [3, 2]
        [0, 3]
*/

Практическое применение. Логирование и агрегация данных (моноид)

Реализация логов как множества событий

У нас есть полноценная структура Logs, которая одновременно:

  • Моноид: merge логов безопасен, ассоциативен и идемпотентен
  • Группа: есть undo/rollback через inverse
  • Распараллеливание: merge N потоков → корректный результат
  • Автоматическая проверка законов: identity, ассоциативность, идемпотентность, обратный элемент
/*

1. `Logs` — это **множество событий** (`BTreeSet`) → автоматически уникальные и упорядоченные.

2. `merge` — **моноидная операция**:

* **Ассоциативна**: `(A.merge(B)).merge(C) == A.merge(B.merge(C))`
* **Идемпотентна**: `A.merge(A) == A`
* **Нейтральный элемент**: пустой лог `Logs::empty()`

3. В `main` мы проверяем:

* ассоциативность
* нейтральный элемент

И в реальной распределённой системе это гарантирует **одинаковый результат на всех узлах**, независимо от порядка слияния логов.
*/
pub mod logs {
    use std::collections::BTreeSet;

    #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
    pub struct LogEntry {
        pub t: u64,
        pub msg: String,
    }

    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct Logs {
        pub added: BTreeSet<LogEntry>,   // события в логе
        pub removed: BTreeSet<LogEntry>, // события, которые были отменены
    }

    impl Logs {
        // Нейтральный элемент
        pub fn empty() -> Self {
            Logs {
                added: BTreeSet::new(),
                removed: BTreeSet::new(),
            }
        }

        // Создать лог из вектора событий
        pub fn from_vec(vec: Vec<LogEntry>) -> Self {
            Logs {
                added: vec.into_iter().collect(),
                removed: BTreeSet::new(),
            }
        }

        /*
        Моноидная операция: merge двух логов.
        Операция merge должна быть моноидом, что бы небыло расхождения кластера

        Которая должна:
            - комбинировать события
            - сортировать их по времени
            - убирать дубликаты
 
        Вариант с Vec + sort + dedup:
        fn merge(mut a: Logs, mut b: Logs) -> Logs { 
            a.extend(b); 
            a.sort_by_key(|e| (e.timestamp, e.node_id)); // фиксированный порядок 
            a.dedup(); // precise eq 
            a 
        }
        Вариант с BTreeSet сам гарантирует:
            - сортировку
            - уникальность
            - ассоциативность merge
            - идемпотентность merge
        */
        pub fn merge(&self, other: &Self) -> Self {
            let mut new_added = self.added.union(&other.added).cloned().collect::<BTreeSet<_>>();
            let mut new_removed = self.removed.union(&other.removed).cloned().collect::<BTreeSet<_>>();

            // Если событие одновременно в added и removed → удаляем
            for entry in new_added.intersection(&new_removed).cloned().collect::<Vec<_>>() {
                new_added.remove(&entry);
                new_removed.remove(&entry);
            }

            Logs {
                added: new_added,
                removed: new_removed,
            }
        }

        // Обратный элемент (undo / rollback)
        pub fn inverse(&self) -> Self {
            Logs {
                added: self.removed.clone(),
                removed: self.added.clone(),
            }
        }

        // Проверка группы: a merge a⁻¹ = нейтральный элемент
        pub fn check_inverse(&self) -> bool {
            self.merge(&self.inverse()) == Logs::empty()
        }

        // Проверка нейтрального элемента
        pub fn check_identity(&self) -> bool {
            self.merge(&Logs::empty()) == *self && Logs::empty().merge(self) == *self
        }

        // Проверка ассоциативности
        pub fn check_associative(&self, b: &Self, c: &Self) -> bool {
            self.merge(&b.merge(c)) == self.merge(b).merge(c)
        }

        // Проверка идемпотентности
        pub fn check_idempotent(&self) -> bool {
            self.merge(self) == *self
        }

        // Текущее состояние лога (added - removed)
        pub fn current(&self) -> BTreeSet<LogEntry> {
            self.added.difference(&self.removed).cloned().collect()
        }
    }
}

use rayon_logs::prelude::*;
pub mod rayon_logs{
    use std::collections::BTreeSet;
    use rayon::prelude::*;
    pub mod prelude{
        pub use rayon::iter::IntoParallelIterator;
        pub use rayon::iter::ParallelIterator;        
    }

    #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
    pub struct LogEntry {
        pub t: u64,
        pub msg: String,
    }

    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct Logs {
        pub added: BTreeSet<LogEntry>,
        pub removed: BTreeSet<LogEntry>,
    }

    impl Logs {
        // Нейтральный элемент
        pub fn empty() -> Self {
            Logs { added: BTreeSet::new(), removed: BTreeSet::new() }
        }
        // Создать лог из вектора событий
        pub fn from_vec(vec: Vec<LogEntry>) -> Self {
            Logs { added: vec.into_iter().collect(), removed: BTreeSet::new() }
        }
        // Merge (моноидная операция)
        pub fn merge(&self, other: &Self) -> Self {
            let mut new_added = self.added.union(&other.added).cloned().collect::<BTreeSet<_>>();
            let mut new_removed = self.removed.union(&other.removed).cloned().collect::<BTreeSet<_>>();

            // Если событие одновременно в added и removed → удалить из обоих
            for entry in new_added.intersection(&new_removed).cloned().collect::<Vec<_>>() {
                new_added.remove(&entry);
                new_removed.remove(&entry);
            }

            Logs { added: new_added, removed: new_removed }
        }

        // Обратный элемент (undo / rollback)
        pub fn inverse(&self) -> Self {
            Logs { added: self.removed.clone(), removed: self.added.clone() }
        }

        // Текущее состояние лога
        pub fn current(&self) -> BTreeSet<LogEntry> {
            self.added.difference(&self.removed).cloned().collect()
        }

        // Проверка группы
        pub fn check_inverse(&self) -> bool {
            self.merge(&self.inverse()) == Logs::empty()
        }

        /// Проверка нейтрального элемента (моноид)
        pub fn check_identity(&self) -> bool {
            let e = Logs::empty();
            self.merge(&e) == *self && e.merge(self) == *self
        }

        /// Проверка ассоциативности: (a ⋁ b) ⋁ c == a ⋁ (b ⋁ c)
        pub fn check_associative(&self, b: &Self, c: &Self) -> bool {
            let left = self.merge(&b.merge(c));
            let right = self.merge(b).merge(c);
            left == right
        }

        /// Проверка коммутативности: a ⋁ b == b ⋁ a
        pub fn check_commutative(&self, other: &Self) -> bool {
            self.merge(other) == other.merge(self)
        }

        /// Проверка идемпотентности: a ⋁ a = a
        pub fn check_idempotent(&self) -> bool {
            self.merge(self) == *self
        }
    }
 
    // Параллельное объединение логов с Rayon
    pub fn parallel_merge(logs_vec: Vec<Logs>) -> Logs {
        logs_vec.into_par_iter().reduce(|| Logs::empty(), |a, b| a.merge(&b))
    }

    // Параллельное объединение с возможностью undo
    pub fn parallel_merge_with_undo(logs_vec: Vec<Logs>) -> (Logs, Vec<Logs>) {
        // Каждый поток получает свой лог и его undo
        let undos: Vec<Logs> = logs_vec.iter().map(|l| l.inverse()).collect();
        
        let merged = logs_vec.into_par_iter().reduce(|| Logs::empty(), |a, b| a.merge(&b));

        (merged, undos)
    }

}

pub mod vec_logs{
    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct LogEntry {
        pub t: u64,
        pub msg: String,
    }

    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct Logs {
        pub entries: Vec<LogEntry>,
    }

    impl Logs {
        // Нейтральный элемент
        pub fn empty() -> Self {
            Logs { entries: Vec::new() }
        }

        pub fn new(entries: Vec<LogEntry>) -> Self {
            let mut logs = Logs { entries };
            logs.sort_and_dedup();
            logs
        }

        // Моноидная операция merge
        pub fn merge(&self, other: &Self) -> Self {
            let mut combined = self.entries.clone();
            combined.extend(other.entries.iter().cloned());
            let mut result = Logs { entries: combined };
            result.sort_and_dedup();
            result
        }

        /*
        Сортировка и удаление дубликатов

        Гарантирует:
        - стабильный порядок (ассоциативность)
        - удаление дубликатов (идемпотентность)
        - Logs::empty() — нейтральный элемент
        - Merge — ассоциативная и идемпотентная операция
         */
        pub fn sort_and_dedup(&mut self) {
            self.entries.sort_by(|a, b| a.t.cmp(&b.t));
            self.entries.dedup_by(|a, b| a.t == b.t && a.msg == b.msg);
        }

        // Проверка ассоциативности
        pub fn check_associative(&self, b: &Self, c: &Self) -> bool {
            self.merge(&b.merge(c)) == self.merge(b).merge(c)
        }

        // Проверка нейтрального элемента
        pub fn check_identity(&self) -> bool {
            self.merge(&Logs::empty()) == *self && Logs::empty().merge(self) == *self
        }

        // Проверка идемпотентности
        pub fn check_idempotent(&self) -> bool {
            self.merge(self) == *self
        }
    }
}

pub mod bad_logs{
    #[derive(Clone, Debug, PartialEq, Eq)]
    pub struct LogEntry {
        pub t: u64,
        pub msg: String,
    }

    #[derive(Clone, Debug, PartialEq)]
    pub struct Logs {
        entries: Vec<LogEntry>,
    }

    impl Logs {
        pub fn new(entries: Vec<LogEntry>) -> Self {
            Logs { entries }
        }

        // ❌ Плохой merge: сортировка нестабильна, дубликаты не учитываются
        pub fn merge(&self, other: &Self) -> Self {
            let mut result = self.entries.clone();
            result.extend(other.entries.iter().cloned());

            // сортировка по timestamp
            // ❌ нестабильная: одинаковый timestamp меняет порядок 
            // → одинаковый timestamp может поменять порядок между A и B → (A merge B) merge C != A merge (B merge C).
            result.sort_by(|a, b| a.t.cmp(&b.t));

            // ❌ нет правильного удаления дубликатов
            // → идемпотентность нарушена: merge(A,A) != A
            // result.dedup(); // забыли или неправильно

            Logs { entries: result }
        }
    }
}
 
fn main() {
 
// logs
    let e1 = logs::LogEntry { t: 2, msg: "A".into() };
    let e2 = logs::LogEntry { t: 2, msg: "A".into() };
    let e3 = logs::LogEntry { t: 3, msg: "C".into() };

    let a = logs::Logs::from_vec(vec![e1.clone(), e2.clone()]);
    let b = logs::Logs::from_vec(vec![e2.clone(), e3.clone()]);
    let c = logs::Logs::from_vec(vec![e1.clone(), e3.clone()]);

    // Проверяем моноидные законы
    assert!(a.check_identity(), "Нейтральный элемент нарушен");
    assert!(a.check_associative(&b, &c), "Ассоциативность нарушена");
    assert!(a.check_idempotent(), "Идемпотентность нарушена");

    println!("Моноидные законы соблюдены ✅");

    // Проверяем обратный элемент (группа)
    assert!(a.check_inverse(), "Обратный элемент нарушен");

    println!("Групповой закон соблюден: a merge a⁻¹ = нейтральный элемент ✅");

    // Демонстрация merge и undo
    let merged = a.merge(&b).merge(&c);
    println!("Merged current logs:");
    for e in merged.current() {
        println!("t={} msg={}", e.t, e.msg);
    }

    let undo = merged.inverse();
    println!("\nUndo merged logs (current should be empty):");
    for e in undo.current() {
        println!("t={} msg={}", e.t, e.msg);
    }

    // merge + undo = пустой лог
    assert!(merged.merge(&undo).current().is_empty());
    println!("\nПосле merge с обратным элементом: пустой лог ✅");
 
//-------------------------------------------------------
// rayon_logs
  
    let a = Logs::from_vec(vec![
        LogEntry { t: 1, msg: "A1".into() },
        LogEntry { t: 3, msg: "A3".into() },
    ]);

    let b = Logs::from_vec(vec![
        LogEntry { t: 2, msg: "B2".into() },
        LogEntry { t: 3, msg: "A3".into() }, // дубликат
    ]);

    let c = Logs::from_vec(vec![
        LogEntry { t: 4, msg: "C4".into() },
    ]);

    println!("A = {:?}", a.current());
    println!("B = {:?}", b.current());
    println!("C = {:?}", c.current());

    // --- ПРОВЕРКИ ---
    assert!(a.check_identity());
    assert!(a.check_commutative(&b));
    assert!(a.check_associative(&b, &c));
    assert!(a.check_idempotent());

    println!("\nВсе свойства моноида и решётки выполняются! ✔️");

    // --- ПОКАЗ ПОСЛЕ MERGE ---
    let ab = a.merge(&b);
    let abc1 = ab.merge(&c);   // (A ∪ B) ∪ C
    let bc = b.merge(&c);
    let abc2 = a.merge(&bc);   // A ∪ (B ∪ C)

    println!("\n(A ⋁ B) ⋁ C = {:?}", abc1.current());
    println!("A ⋁ (B ⋁ C) = {:?}", abc2.current());
    println!("\nАссоциативность подтверждена: обе формы одинаковые ✔️");

//-------------------------------------------------------
// vec_logs

    let a = vec_logs::Logs::new(vec![
        vec_logs::LogEntry { t: 1, msg: "A1".into() },
        vec_logs::LogEntry { t: 2, msg: "A2".into() },
    ]);

    let b = vec_logs::Logs::new(vec![
        vec_logs::LogEntry { t: 2, msg: "B1".into() },
        vec_logs::LogEntry { t: 3, msg: "B2".into() },
    ]);

    let c = vec_logs::Logs::new(vec![
        vec_logs::LogEntry { t: 1, msg: "C1".into() },
        vec_logs::LogEntry { t: 4, msg: "C2".into() },
    ]);

    // Проверяем законы
    assert!(a.check_identity(), "Нейтральный элемент нарушен");
    assert!(a.check_associative(&b, &c), "Ассоциативность нарушена");
    assert!(a.check_idempotent(), "Идемпотентность нарушена");

    // Merge для наглядности
    let merged = a.merge(&b).merge(&c);
    println!("Merged logs: {:#?}", merged);
 
//--------------------------------------------------------
// bad_logs

    // Создаем три лога с одинаковыми timestamp
    let a = bad_logs::Logs::new(vec![bad_logs::LogEntry { t: 2, msg: "A".into() }]);
    let b = bad_logs::Logs::new(vec![bad_logs::LogEntry { t: 2, msg: "A".into() }]);
    let c = bad_logs::Logs::new(vec![bad_logs::LogEntry { t: 3, msg: "C".into() }]);

    let ab_c = a.merge(&b).merge(&c);
    let a_bc = a.merge(&b.merge(&c));

    println!("(A merge B) merge C = {:#?}", ab_c);
    println!("A merge (B merge C) = {:#?}", a_bc);

    assert_eq!(ab_c, a_bc); // ❌ Ассерция может упасть!    
    
}

5. Булева алгебра

Приоритет операторов: Что выполняется первым: NOT, потом AND, потом OR. Всегда использовать скобки для сложных случаев, чтобы не полагаться на память.

Законы де Моргана: Позволяют упрощать и инвертировать сложные условия.

Исходное тождество !(A && B) эквивалентно ≡ !A || !B

  • Если теперь отрицать обе части, получим:
    • !(!(A && B)) ≡ !(!A || !B)
    • убираем двойное отрицание слева, получим:
    • A && B ≡ !(!A || !B)

Исходное тождество !(A || B) ≡ !A && !B

  • Если теперь отрицать обе части, получим:
    • A || B ≡ !(!A && !B)

Пример: "Если пользователь НЕ (админ И подключен из доверенной сети)"

// Плохо, сложно читать
if (!(user.isAdmin && ip.isTrusted)) { ... }

// Хорошо, применяем закон де Моргана
if (!user.isAdmin || !ip.isTrusted) { ... }
// Читается как: "Если пользователь не админ ИЛИ IP не из доверенной сети"

Короткий цикл вычислений (short-circuit evaluation): Понимание закона тождества, что в a && b значение b не вычислится, если a ложно, а в a || b значение b не вычислится, если a истинно. Это используется для безопасных проверок: if (obj != null && obj.isValid())

Законы Тождества (при любом A):

  • A && true = A
  • A && false = false
  • A || true = true
  • A || false = A

Дистрибутивность (Распределительный закон)

Дистрибутивность AND над OR: A && (B || C) = (A && B) || (A && C)

fn main(){
    let a = true;
    let b = false;
    let c = true;
    assert!(a && (b || c));
    assert_eq!(a && (b || c), (a && b) || (a && c));
}

Дистрибутивность OR над AND: A || (B && C) = (A || B) && (A || C)

fn main(){
    let a = false;
    let b = true;
    let c = true;
    assert!(a || (b && c));
    assert_eq!(a|| (b && c), (a || b) && (a || c));
}

Применение, фильтры как булева алгебра

use std::collections::BTreeSet;

#[derive(Clone, Debug, PartialEq, Eq)]
struct Filter {
    allowed: BTreeSet<String>,
}

impl Filter {
    fn new(allowed: Vec<&str>) -> Self {
        Filter { allowed: allowed.into_iter().map(|s| s.to_string()).collect() }
    }

    fn and(&self, other: &Self) -> Self {
        let allowed = self.allowed.intersection(&other.allowed).cloned().collect();
        Filter { allowed }
    }

    fn or(&self, other: &Self) -> Self {
        let allowed = self.allowed.union(&other.allowed).cloned().collect();
        Filter { allowed }
    }

    fn not(&self, universe: &BTreeSet<String>) -> Self {
        let allowed = universe.difference(&self.allowed).cloned().collect();
        Filter { allowed }
    }
}

fn main() {
    let f1 = Filter::new(vec!["read", "write"]);
    let f2 = Filter::new(vec!["write", "execute"]);
    let universe: BTreeSet<String> = ["read","write","execute","delete"].iter().map(|s| s.to_string()).collect();

    let and_filter = f1.and(&f2); // пересечение
    let or_filter = f1.or(&f2);   // объединение
    let not_filter = f1.not(&universe); // отрицание

    println!("AND: {:?}", and_filter.allowed);
    println!("OR: {:?}", or_filter.allowed);
    println!("NOT: {:?}", not_filter.allowed);
}

AND: {"write"}
OR: {"execute", "read", "write"}
NOT: {"delete", "execute"}

Полный набор базовых логических операций

(AND, ∧) в логике и программировании означает И (логическое умножение или конъюнкция). Это логическая операция, которая выдает истину (True), только если оба операнда истинны. Если хотя бы один из операндов ложен, то результат — ложь.

AND01
000
101

(OR, ∨) Это логическая операция, которая выдает истину (True), если хотя бы один из операндов истинен.

OR01
001
111

(XOR, ⊕) (от англ. Exclusive OR/Исключающее ИЛИ). Это логическая операция, которая выдает истину (True), если только один из операндов истинен, и ложь (False), если оба операнда одинаковы (оба истинны или оба ложны).

XOR01
001
110

(NOT, ¬) (Инвертор) Инвертирует входное значение. Истина становится Ложью, и наоборот.

0 -> NOT -> 1

1 -> NOT -> 0

NAND (Not-AND/И-НЕ) Противоположность AND. Выдает Ложь, только если оба входа Истинны. Т.е. сперва применяется операция AND и к результату ее применяется операция NOT: 1 AND 1 = 1 NOT = 0

NAND01
011
110

NOR (Not-OR/ИЛИ-НЕ) Противоположность OR. Выдает Истину, только если оба входа Ложны. Т.е. сперва применяется операция OR и к результату ее применяется операция NOT: 0 OR 0 = 0 NOT = 1

NOR01
010
100

XNOR (Exclusive-NOR/Исключающее ИЛИ-НЕ). Противоположность XOR. Выдает Истину, если оба входа одинаковы (оба Ложны или оба Истинны).

XNOR01
010
101

Сложное выражение

Для выражения: (A ∧ B) ∨ C

ABCA ∧ B(A ∧ B) ∨ C
00000
00101
01000
01101
10000
10101
11011
11111

Таблицы истинности

Для понимания, когда сложное выражение возвращает true, а когда false.

Таблица истинности превращает сложную логику из "магии" в предсказуемую и понятную систему, где видна каждая возможная комбинация условий!

Задача: Проверка доступа к системе

У нас есть сложное условие для доступа к админ-панели:

if ((isAdmin || isModerator) && isActive && !isBanned) {
    grantAccess();
}

Давайте построим таблицу истинности для этого выражения: (isAdmin || isModerator) && isActive && !isBanned

Шаг 1: Определяем все переменные

  • A = isAdmin
  • B = isModerator
  • C = isActive
  • D = isBanned

Перепишем выражение: (A || B) && C && !D

Шаг 2: Строим полную таблицу истинности

A (Admin)B (Moderator)C (Active)D (Banned)A ∨ B!D(A ∨ B) ∧ C ∧ !DДоступ
0000010❌
0001000❌
0010010❌
0011000❌
0100110❌
0101100❌
0110111✅
0111100❌
1000110❌
1001100❌
1010111✅
1011100❌
1100110❌
1101100❌
1110111✅
1111100❌

Шаг 3: Анализируем результаты

Из таблицы видно, что доступ разрешен только в 3 случаях:

  • A=0, B=1, C=1, D=0 - Модератор, активен, не забанен
  • A=1, B=0, C=1, D=0 - Админ, активен, не забанен
  • A=1, B=1, C=1, D=0 - Админ и модератор, активен, не забанен

Шаг 4: Практические выводы для программиста

Мы узнали критически важные вещи:

  • Активность обязательна - без isActive = true доступ никогда не дается
  • Бан блокирует всегда - если isBanned = true, доступ никогда не дается
  • Нужна хотя бы одна роль - без админа или модератора доступа нет
  • Edge cases видны явно - мы видим ВСЕ возможные комбинации

Шаг 5: Применяем для отладки

Представим, что пользователь жалуется: "Я админ, но меня не пускает!"

Смотрим в таблицу и сразу видим возможные причины:

  • isActive = false (строки 9-10)
  • isBanned = true (строки 11-12)
// Быстрая диагностика
console.log(`Admin: ${isAdmin}, Active: ${isActive}, Banned: ${isBanned}`);
// Сразу найдем проблему!

6. Алгебраические структуры — основа CRDT

Почему CRDT проще чем блокировки

Избегаем блокировок — разрешаем конфликты через структуры данных.

CRDT (Conflict-Free Replicated Data Types) — это структура данных, которая автоматически разрешает конфликты при репликации без координации между узлами.

Это подход без блокировок (lock-free), который масштабируется на распределённые системы и выдерживает сетевые сбои!

CRDT — это про данные, Mutex — про доступ.

Но CRDT работает только если данные можно определить как моноид. CRDT существует только там, где можно определить merge, т.е. на поведение реализующего типа наложены очень жёсткие ограничения:

  • Ассоциативность merge( merge(a, b), c ) == merge( a, merge(b, c) )
  • Коммутативность merge(a, b) == merge(b, a)
  • Идемпотентность merge(a, a) == a
  • Нейтральный элемент merge(x, empty) == x

CRDT силён, тем что не требует конфликт-резолвера (например, timestamp last-write-wins). То есть не требует внешней функции: «если конфликт — выбери левый или правый». CRDT = структура, в которой конфликтов НЕ бывает. Конфликты невозможны по определению, потому что операция merge всегда детерминирована, коммутативна, ассоциативна и идемпотентна.

Что может быть CRDT:

  • структуры данных могут быть CRDT: Множества (HashSet, BTreeSet), Карты, словари (Dictionary / Map / HashMap)
  • Счётчики: G-Counter (только увеличение), PN-Counter (увеличение/уменьшение через два счётчика)
  • Регистр (одно значение): LWW-Register (last-write-wins → timestamp max), MV-Register (множество всех одновременных значений)
  • Графы: Работает, если вершины и рёбра — CRDT множества.
  • Логи: если каждая запись формирует множество

Практические примеры где используются CRDT:

  1. Offline-First совместное редактирование (как Google Docs), заметки (Apple Notes, Simplenote), задачники (Todoist)
  2. Multiplayer игры, видимость объектов, позиции игроков, распределенный инвентарь магазина
  3. Онлайн-чаты и комментарии
  4. Распределенные очереди
  5. Геораспределенные системы
  6. IoT системы конфигурации устройств, хранилище сенсорных данных
  7. Социальные сети: счётчики, лайки, реактивные фиды
  8. Riak — самая известная CRDT-база
  9. Redis использует CRDT для: множества пользователей онлайн, Geo-распределённых ключей

CRDT не подходит для:

  • Транзакции, требующие строгой согласованности (банковские переводы)
  • Системы, где важен абсолютный порядок операций, т.е. если важна последовательность прихода событий
  • Если синхронизация должна быть быстрой, в CRDT merge линейный от размера структуры
  • CRDT ломаются, если есть side-effects от событий (логирование, отправка email, запись в стороннюю систему, списание денег в банке)
  • CRDT плохо подходят для больших бинарных объектов (видео, изображения). Потому merge будет тяжелым, а структуры grow-only → огромные.
    • CRDT = структура, которая хранит операции, а не только финальное состояние.
    • CRDT никогда не хранит «только текущее состояние», оно хранит кучу метаданных для merge, изменил 10 000 пикселей = 10 000 операций.
    • Картинка превращается в гигантское раздутое дерево CRDT-операций, огромный размер, гигантская память, дикая нагрузка.
    • CRDT оправдан, когда данные редактируют многие одновременно, для картинок это случается крайне редко.
// С блокировками:
def update_with_lock(shared_data):
    lock.acquire()          # ❌ Блокируем всех
    try:
        shared_data.value += 1
    finally:
        lock.release()

// С CRDT: 
def update_crdt(local_counter, increment):
    local_counter.value += increment  # ✅ Каждый работает локально
    # Потом асинхронно синхронизируем

CRDT vs Mutex

CRDT работают независимо от порядка событий

(а блокировки требуют строгого порядка)

Блокировки гарантируют:

  • один поток → входит
  • остальные → ждут
  • все операции → в строгом порядке

То есть порядок критичен.

Если порядок меняется — меняется результат.

Где CRDT бесполезны (и нужен Mutex / RwLock)

  • Последовательные операции balance -= 10. Эта операция зависит от предыдущего значения. Если два потока одновременно делают -10, мы можем уйти в минус.
  • Ограниченные ресурсы (состояния некоммутативные). Например:зарезервировать место в самолёте, два потока могут попытаться взять одно и то же место. Тут нет коммутативного merge.
  • Мутация единого объекта

Типы для CRDT

Обычная String не может быть CRDT из-за важности порядка символов и операции конкатенации и одновременного изменения.

Но можно использовать String если использовать спец. CRDT для последовательностей:

  • RGA (Replicated Growable Array)
  • LSEQ
  • WOOT
  • Yjs Text CRDT
  • Automerge Text

Так же и с Vec, если использовать спец. CRDT-последовательность:

  • Vec<CRDT_Item>
  • CRDT sequence (RGA, LSEQ, Yjs Array)

Массивы фиксированного размера [T; N]. Если T — CRDT → массив CRDT.

Может ли struct быть CRDT? Да — если каждая её часть (поле) — CRDT.