Алгебраїчний тип даних

Алгебраїчний тип даних - в теорії програмування будь-який тип, значення якого є значеннями деяких інших типів, "обгорненими" конструкторами алгебраїчного типу. Іншими словами, алгебраїчний тип даних має набір конструкторів типу, кожен з яких приймає на вхід значення певних типів і повертає значення конструируемого типу. Важлива відмінність конструктора типу від функції полягає в тому, що конструктор не виконується, але єдина його задача - створення значення свого типу на основі вхідних значень. Для роботи з такими значеннями використовується механізм зіставлення зі зразками, як найбільш ефективний спосіб розбору значень (але це не означає, що інші механізми роботи з значеннями не застосовні до алгебраїчних типів даних).

Найпростішим алгебраїчним типом даних є список. Дійсно, список має два конструктора - конструктор порожнього списку і конструктор пари, першим елементом якої є значення певного типу, а другим - список. Приклад визначення списку на мові Haskell :

 data List a = Nil | Cons a (List a) 

Так що видно, що алгебраїчні типи даних є контейнерними типами - вони містять усередині себе значення інших типів (або того ж самого типу). Те, що у списку перший конструктор не приймає на вхід-яких параметрів, не повинно вводити в сумнів. Така форма конструктора є необхідною для створення значень, які всередині себе не містять нічого, але є "одиничними" елементами алгебраїчних типів даних.

Спеціальними різновидами алгебраїчних типів даних є декартові типи (вони мають тільки один конструктор) і перерахування (у них все конструктори аргументів не мають зовсім, хоча самих конструкторів може бути декілька). Так найпростішим, але дуже широко використовуваним перерахуванням є логічний тип. Код на Haskell :

 data Bool = False | True 

Також алгебраїчний тип даних може бути абстрактним, якщо такий тип визначений в деякому модулі, з якого не експортуються конструктори відповідного типу, а доступ до значень усередині алгебраїчного типу даних здійснюється за допомогою спеціальних методів - селекторів. Особливо варто відзначити так звані " узагальнені алгебраїчні типи даних ", які реалізовані в мовах Haskell і ML.

Залишається відзначити, що з точки зору синтаксично-орієнтованого конструювання даних алгебраїчним типом даних є розмічених об'єднання декартових добутків типів. Кожен доданок в розміченому об'єднанні відповідає одному конструктору, а кожен конструктор в свою чергу визначає декартовій твір типів, відповідних параметрам конструктора. Конструктори без параметрів є порожніми творами. Якщо алгебраїчний тип даних є рекурсивним, все розмічених об'єднання обгортається рекурсивним типом, і кожен конструктор типу повертає рекурсивний тип.


1. Реалізація

1.1. Мова Haskell

У мові Haskell будь-який тип даних, який не є примітивним, є алгебраїчним. Всі можливі види значень ( перерахування, об'єкти, структури і т. д.) будуються за допомогою конструкторів алгебраїчних типів даних. Тому дана тема є надзвичайно важливою для розуміння системи типізації мови Haskell.


1.2. Мова Nemerle

У мові Nemerle існує ключове слово "variant", за допомогою якого можна описати алгебраїчний тип даних. Всі створені таким шляхом варіанти можуть бути зіставлені із зразком через ключове слово "match".

Перегляд цього шаблону Типи даних
Неінтерпретіруемие
Числові
Текстові
Покажчик

Адреса Посилання

Композитні
Інші

Логічний Нижчий тип Колекція Перераховуються тип Виняток First-class function Opaque data type Recursive data type Семафор Потік Вищий тип Type class Unit type Void

Пов'язані теми