Когда выставлять конструкторы типа данных при проектировании структур данных?

Ответ 1

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

Например, если вы представляете что-то вроде двухмерных точек со своим типом (включая новый тип), вы можете также выставить конструктор. Реальность заключается в том, что изменение этого типа данных не будет изменяться в отношении того, как представлены 2d-точки, это будет изменение в вашей потребности использовать 2d баллов (возможно, вы обобщаете 3D-пространство, возможно, вы добавление понятия слоев или что-то еще), и почти наверняка потребуется внимание в частях кода, используя значения этого типа независимо от того, что вы делаете. [1]

Комплексный тип, представляющий что-то конкретное для вашего приложения или области, скорее всего, подвергнется изменениям в представлении, продолжая поддерживать подобные операции. Поэтому вам нужны только другие модули в зависимости от операций, а не от внутренней структуры. Поэтому вы не должны раскрывать конструкторы.

Другие типы представляют вещи с каноническими определениями, но не канонические представления. Все знают свойства, ожидаемые от карт и наборов, но существует множество способов представления значений, поддерживающих эти свойства. Поэтому вам снова нужны только другие модули в зависимости от операций, которые они поддерживают, а не от конкретных представлений.

Некоторые типы, независимо от того, являются ли они простыми с каноническими представлениями, позволяют создавать значения в программе, которые не представляют собой действительное значение в абстрактной концепции, которую должен представлять тип. Простым примером может быть тип, представляющий собой самобалансирующееся двоичное дерево поиска; клиентский код с доступом к конструкторам может легко построить недопустимые деревья. Выявление конструкторов означает, что вам нужно предположить, что такие значения, переданные извне, могут быть недействительными, и поэтому вам нужно сделать что-то разумное даже для причудливых значений или означает, что ответственность программистов, работающих с вашим интерфейсом, Не нарушайте никаких предположений. Обычно лучше просто создавать такие типы непосредственно вне вашего модуля.

В основном это сводится к концепции, которую должен представлять ваш тип. Если ваша концепция имеет очень простой и понятный способ [2] непосредственно к значениям в некоторых типах данных, которые не являются "более инклюзивными", чем концепция, из-за которой компилятор не может проверить необходимые инварианты, тогда концепция в значительной степени "то же", что и тип данных, и разоблачение его структуры в порядке. Если нет, тогда вам, вероятно, нужно будет скрывать структуру.

[1] Вероятное изменение, однако, заключалось бы в изменении того, какой числовой тип вы используете для значений координат, поэтому вам, вероятно, придется подумать о том, как минимизировать влияние таких изменений. Это довольно ортогонально тому, выставляете ли вы конструкторы.

[2] "Очевидное" здесь означает, что если вы попросите 10 человек самостоятельно придумать тип данных, представляющих концепцию, все они вернутся с тем же, поменяв имена.

Ответ 2

Существенным фактором для меня является ответ на следующий вопрос:

Является ли структура моего типа данных релевантной для внешнего мира?

Например, внутренняя структура типа данных списка очень важна для внешнего мира - у него есть индуктивная структура, которая, безусловно, очень полезна для разоблачения для потребителей, поскольку они строят функции, которые производятся индукцией по структуре список. Если список конечен, то эти функции гарантированно завершатся. Кроме того, определение функций таким образом облегчает предоставление свойств о них, опять же путем индукции.

В отличие от этого, лучше всего, чтобы тип данных Set оставался абстрактным. Внутренне он реализуется как дерево в пакете containers. Однако он мог бы быть реализован с использованием массивов или (более полезно в функциональной настройке) с деревом с немного другой структурой и с учетом различных инвариантов (сбалансированный или неуравновешенный, ветвящийся фактор и т.д.). Необходимость принудительного применения каких-либо инвариантов выше и выше тех, которые конструкторы уже применяют по своим типам, между прочим, препятствует тому, чтобы тип данных был конкретным.

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

В качестве побочного элемента можно было бы возразить, что на самом деле индуктивная структура списков, которая настолько фундаментальна для записи функций, прекращение и поведение которых легко рассуждать, абстрагируется абстрактно двумя функциями, которые потребляют списки: foldr и foldl. Учитывая эти два основных оператора списка, большинству функций вообще не нужно проверять структуру списка, и поэтому можно утверждать, что списки слишком совместимы, чтобы быть абстрактными. Этот аргумент обобщается на многие другие подобные структуры, такие как все структуры Traversable, все структуры Foldable и т.д. Однако почти невозможно зафиксировать все возможные рекурсионные шаблоны в списках, и на самом деле многие функции не являются рекурсивными в все. Если заданы только foldr и foldl, можно было бы написать, например, запись head, хотя это было бы довольно утомительно:

head xs = fromJust $ foldl (\b x -> maybe (Just x) Just b) Nothing xs

Нам гораздо лучше отдать внутреннюю структуру списка.

Конечным моментом является то, что иногда фактическое представление типа данных не имеет отношения к внешнему миру, потому что, скажем, это какой-то оптимизированный и не может быть каноническим представлением, или нет ни одного "канонического", представление. В этих случаях вы хотите сохранить абстрактный тип данных, но предлагаете "представления" вашего типа данных, которые предоставляют конкретные представления, которые могут быть сопоставлены с образцом.

Одним из примеров могло бы быть, если бы хотелось определить тип данных Complex для комплексных чисел, где как декартовы формы, так и полярные формы можно считать каноническими. В этом случае вы сохраните Complex abstract, но экспортируете два вида, т.е. Функции polar и cartesian, которые возвращают пару длины и угол или координату в декартовой плоскости соответственно.

Ответ 3

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

Тогда существуют типы, для которых невозможно или трудно построить несогласованные/неправильные значения либо потому, что тип этого не позволяет, либо потому, что вам нужно будет ввести нижние части. Примером этого может служить тип списка индексированных по длине (обычно называемый Vec) и большинство монад.

В конечном счете это ваше собственное решение. Поставьте себя в точку зрения пользователя и сделайте компромисс между удобством и безопасностью. Если нет компромиссов, всегда открывайте конструкторы. В противном случае пользователи библиотеки будут ненавидеть вас за ненужную непрозрачность.

Ответ 4

Если тип данных служит простой цели (например, Maybe a), и никакие (явные или неявные) предположения о типе данных могут быть нарушены путем прямого построения значения через конструкторы данных, я бы разоблачил конструкторы.

С другой стороны, если тип данных более сложный (например, сбалансированное дерево) и/или его внутреннее представление, вероятно, изменится, я обычно скрою конструкторы. При использовании пакета существует неписанное правило, что интерфейс, открытый не-внутренним модулем, должен быть "безопасным" для использования в данном типе данных. Учитывая пример сбалансированного дерева, публикация конструкторов данных позволяет (случайно) построить несбалансированное дерево, и поэтому предполагаемые гарантии времени выполнения для поиска дерева и т.д. Могут быть нарушены.

Ответ 5

Я бы предложил другое, значительно более ограничительное правило, чем большинство людей. Главным критерием будет:

Вы гарантируете, что этот тип никогда не изменится? Если это так, разоблачение конструкторов может быть хорошей идеей. Удачи вам, хотя!

Но типы, для которых вы можете сделать эту гарантию, как правило, являются очень простыми, общими типами "основания", такими как Maybe, Either или [], которые можно было бы написать один раз, а затем больше не повторять.

Хотя даже это может быть поставлено под сомнение, потому что время от времени они пересматриваются; есть люди, которые использовали версии, закодированные Церковью Maybe и List, в различных контекстах по причинам производительности, например:

{-# LANGUAGE RankNTypes #-}

newtype Maybe' a = Maybe' { elimMaybe' :: forall r. r -> (a -> r) -> r }
nothing = Maybe' $ \z k -> z
just x = Maybe' $ \z k -> k x

newtype List' a = List' { elimList' :: forall r. (a -> r -> r) -> r -> r }
nil = List' $ \k z -> z
cons x xs = List' $ \k z -> k x (elimList' k z xs)

Эти два примера подчеркивают что-то важное: вы можете заменить реализацию типа Maybe', показанную выше, любой другой реализацией, если она поддерживает следующие три функции:

nothing :: Maybe' a
just :: a -> Maybe' a
elimMaybe' :: Maybe' a -> r -> (a -> r) -> r

... и следующие законы:

elimMaybe' nothing z x  == z
elimMaybe' (just x) z f == f x

И этот метод может быть применен к любому типу алгебраических данных. Который мне говорит, что сопоставление шаблонов с конкретными конструкторами недостаточно абстрактно; он на самом деле не дает вам ничего, что вы не можете получить из абстрактного конструктора + шаблон деструктора, и он теряет гибкость реализации.