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

Есть несколько способов, в зависимости от того, какая версия «абстрактных типов данных» вам нужна.

• Конкретные, но непрозрачные типы : Прошло немного времени с тех пор, как я прочитал прекрасную статью Кука, но, оглядываясь назад, я думаю, что это ближе всего к тому, о чем он говорит как о ADT. Стандартный способ сделать это в Haskell - экспортировать тип без его конструкторов; что это означает в Haskell:

  • Нет сопоставления с образцом для значений абстрактного типа

  • Нет конструирования значений типа, кроме использования функций, экспортированных из его модуля

  Как это относится к статье Кука:

  • Независимость представления : Извне представление недоступно.

  • Проверка нескольких представлений: Внутри модуля ADT представления можно проверять свободно.

  • Уникальные реализации / модули: Различные реализации могут быть предоставлены разными модулями, но типы не могут взаимодействовать друг с другом, кроме как обычными средствами. Вы не можете использовать Data.IntMap.null , чтобы увидеть, является ли Data.Map.Map Int a пустым.

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

   импорт квалифицированных данных.Установить как 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 можно найти в статье Развертывание абстрактных типов данных ; но имейте в виду, что то, что он обсуждает, по сути не то, что Кук называет ADT.

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