Как объявить тип контейнера абстрактных данных в Haskell?

Я прочитал Уильяма Кука "О абстракции данных, пересмотренный" и перечитал Ральфа Леммеля "Лемма выражения", чтобы попытаться понять, как применять предыдущие идеи в Haskell. Итак, я пытаюсь понять, как вы могли реализовать, например, функцию объединения соединений в Haskell без указания типов?

Ответ 1

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

Бетонные, но непрозрачные типы. Прошло немного времени с тех пор, как я прочитал прекрасную бумагу Кука, но, оглядываясь назад, я думаю, что это ближе всего к тому, что он говорит как ADT. Стандартный способ сделать это в Haskell - экспортировать тип без его конструкторов; что это означает в Haskell:
- Совпадение шаблонов по значениям абстрактного типа
- Никаких построчных значений типа, кроме использования функций, экспортированных из его модуля
Как это относится к бумаге Кука:
- Независимость от представления: извне представление недопустимо.
- Проверка нескольких представлений: внутри модуля ADT представления могут быть проверены свободно.
- Уникальные реализации/модули: различные реализации могут предоставляться различными модулями, но типы не могут взаимодействовать, кроме как обычными средствами. Вы не можете использовать Data.IntMap.null, чтобы увидеть, пустой ли Data.Map.Map Int a.
Этот метод широко используется в стандартных библиотеках Haskell, особенно для типов данных, которые должны поддерживать какой-то инвариант или иным образом ограничивать возможность построения значений. Таким образом, в этом случае наилучшим способом реализации набора ADT из бумаги является следующий код:
```
import qualified Data.Set as S
```
Хотя это, возможно, не столь мощное средство абстракции, как могло бы быть на языке с более выразительной модульной системой.
Экзистенциальная квантификация и интерфейс. Haskell на самом деле не имеет ключевое слово exists как таковое, но термин "экзистенциальный" используется в различных обстоятельствах для описания некоторых видов полиморфных типов, Общая идея в каждом случае состоит в объединении значения с набором функций, работающих на нем, так что результат является полиморфным в типе значения. Рассмотрим эту сигнатуру функции:
```
foo :: (a, a -> Bool) -> Bool
```
Хотя он получает значение типа a, потому что a полностью полиморфно, единственное, что он может сделать с этим значением, - это применить к нему функцию. Таким образом, в некотором смысле, в этой функции первая половина кортежа является "абстрактным типом данных", а вторая половина - "интерфейсом" для работы с этим типом. Мы можем сделать эту идею явной и применить ее за пределами одной функции, используя экзистенциальный тип данных:
```
data FooADT = forall a. FooADT a (a -> Bool)

foo :: FooADT -> Bool
```
Теперь, когда мы имеем значение типа FooADT, все, что мы знаем, это то, что существует некоторый тип a такой, что мы можем применить второй аргумент FooADT к его первому.

То же самое относится к полиморфным типам с ограничениями класса; единственное различие заключается в том, что функции, действующие на тип, предоставляются неявным образом классом типа, а не явно связаны со значением.

Теперь, что это значит с точки зрения бумаги Бука?
- Независимость от представления все еще применяется.
- Общая изоляция: в отличие от ранее, знание экзистенциально квантифицированного типа навсегда потеряно. Ничто не может проверить представление, кроме самого интерфейса, который он сам предоставляет.
- Произвольные реализации: не только реализации не обязательно уникальны, но и вообще невозможно их ограничить! Все, что может обеспечить один и тот же интерфейс, может быть обернуто внутри экзистенциального и быть неотличимым от других значений.
Короче говоря, это очень похоже на описание Кука объектов. Более подробно об экзистенциальных ADT, документ Unfolding Abstract Datatypes - неплохое начало; но имейте в виду, что то, что он обсуждает, принципиально не то, что Кук вызывает ADT.

И короткое добавление: перейдя ко всем проблемам выше, чтобы описать абстракции экзистенциального типа, я хотел бы выделить что-то о типе FooADT: потому что все, что вы можете с ним сделать, это применить функцию для получения Bool, принципиально нет разницы между FooADT и Bool, за исключением того, что первый обфускает ваш код и требует расширений GHC. Я настоятельно рекомендую прочитать это сообщение в блоге, прежде чем устанавливать для использования экзистенциальных типов в коде Haskell.

Ответ 2

Вы можете либо потребовать предоставления функции сравнения, либо потребовать, чтобы типы были экземплярами уравнения. См. nub и nubBy для примеров этой техники:

nub :: (Eq a) => [a] -> [a]
nubBy :: (a -> a -> Bool) -> [a] -> [a]