Что же такое Алгебраические Типы Данных(Algebraic Data Types(ADT))? Обычно определение состоит из терминов теории типов и обязательно с примером на Haskell. Но на практике всё не так сложно.

Типы данных

Сначала разберемся с типами данных в общем случае.

Тип данных - это допустимое множество всех значений именнованой абстракции.

Например

Самый простой тип данных bit. Его значения: {0, 1}.

Тип bool = {true, false}.

Тип byte = {0,1,..,255} или {-128, -127,…, 127} или {ASCII Table}

Обычно на уровне языка реализовано несколько “примитивных” типов: логический, целочисленные, числа с плавающей запятой, строковые и указатели/ссылки.

Множество может быть пустым, а еще может состоять из одного элемента. Такие типы тоже бывают.

Единичный тип, он же unit, обычно обозначается (). Этот тип указывает на отсутствие определенного значения. unit имеет только одно значение, которое выступает в качестве заполнителя, если другое значение не существует или не требуется. В C подобных языках похожую функцию выполняет void.

Пустое множество. Тип без значения. Подобный тип данных называют ненаселенным (uninhabited type). Обычно он используется, чтобы показать невычислимость выражения, например, брошено исключение, выход из программы, бесконечный цикл, и т.п. В rust это never type.

Но этого мало. Нужно больше. Мы хотим объединять и комбинировать типы.

Алгебраический тип данных

Сделаем из простых типов другие, составные и более сложные. Это и будут алгебраические тип данных. А называются они так потому, что новые типы получаются с помощью сложения и умножения.

Тип Произведения (Product Type)

Cамый простой способ получить новый тип данных на основе существующих - объединить их вместе. Такие типы реализованы через struct, class, tuple, record и пр.

Создадим новый тип произведения:

type NewProductType struct {
	a bool
	b byte
}

NewProductType состоит из типа bool И типа byte.

NewProductType = {true, false} * {0,1,…,255} = {(true,0),(false,0),(true,1),(false,1),..,(true,255),(false,255)}

Получается множество/тип NewProductType с мощностью 2*255=510.

Это то чем мы ежедневно пользуемся, создавая новые типы c помощью классов, структур и пр.

Тип Сумма (Sum Type)

Он же tagged union или просто variant. Встречается реже чем product type и обычно когда говорят про ADT имеют ввиду именно тип sum type.

Sum Type — значения этого типа могут быть одним из нескольких взаимоисключающих вариантов.

Например

Тип bool. Его значения - это True ИЛИ False — два взаимоисключающих варианта.

Если смотреть в сторону rust, то это enum.

Option можете принимать два значения None ИЛИ любой тип.

enum Option<T> {
    None,
    Some(T),
}

Растовский ответ null ссылкам. The Option Enum and Its Advantages Over Null Values

Если функция может вернуть ошибку(Err) ИЛИ результат успешного завершения(OK), тогда нам поможет enum Result.

enum Result<T, E> {
   Ok(T),
   Err(E),
}

Pattern Matching

Остался вопрос о том как определить значения такого типа. В идеале нужен pattern matching. Гибкий и удобный механизм.

Например

Функция find ищет указанное значение в слайсе. Нам нужен индекс найденного элемента или сообщения о том, что такого элемента в слайсе нет.

fn find(value: i32, slice: &[i32]) -> Option<usize> {
    for (index, &element) in slice.iter().enumerate() {
        if element == value {
            // Return a value
            return Some(index);
        }
    }
    // Return no value
    None
}

Используем конструкцию match, что бы обработать полученные значения:

fn main() {
    let array = [1, 2, 3, 4, 5];
    
    match find(2, &array) {
        Some(index) =>println!("The element 2 is at index {}.", index),
        None => println!("The element 2 is not in the array.")
    }
}

Как дела в Go

В Go нет sum type в классическом виде и что более печально нет pattern matching. Подробнее почему это так можно прочитать в faq.

Если кратко, то ответ такой: в go есть интерфейсы и type switch, они не такие элегантные, гибкие и безопасные, но основные потребности перекрывают.

Пример из wiki - это бинарное дерево. Дерево может быть пустым, листом или содержать левых\правых детей:

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

функция поиска глубины дерева:

 depth :: Tree -> Int
 depth Empty = 0
 depth (Leaf n) = 1
 depth (Node l r) = 1 + max (depth l) (depth r)

Вариант на Go:

type Tree interface {
}

type Empty struct {
}

type Leaf struct {
    v int
}

type Node struct {
    left, right Tree
}

func depth(t Tree) int {
    switch nt := t.(type) {
    case Empty:
        return 0
    case Leaf:
        return 1
    case Node:
        return 1 + max(depth(nt.left), depth(nt.right))
    default:
        log.Fatalf("unexpected type %T", nt)
    }
    return 0
}

Комментарии в Telegram-группе!