Почему алгебраические типы данных Haskell "закрыты"?

Question

Поправьте меня, если я ошибаюсь, но кажется, что алгебраические типы данных в Haskell полезны во многих случаях, когда вы используете классы и наследование в ОО-языках. Но есть большая разница: как только объявлен алгебраический тип данных, он не может быть расширен в другом месте. Закрыто". В ОО вы можете расширить уже определенные классы. Например:

data Maybe a = Nothing | Just a

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

Answer 1

Ответ связан с тем, как легко расширить код, между классами и алгебраическими типами данных, которые Фил Вадлер назвал «проблемой выражения»:

• С алгебраическими типами данных

  • Очень дешево добавить новую операцию над вещами : вы просто определяете новую функцию. Все старые функции на этих объектах продолжают работать без изменений.

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

• с занятиями,

  • Очень дешево добавить новый вид вещи : просто добавьте новый подкласс, и при необходимости вы определите специализированные методы в этом классе для всех существующие операции. Суперкласс и все остальные подклассы продолжают работать без изменений.

  • Очень дорого добавить новую операцию с вещами : вам нужно добавить объявление нового метода в суперкласс и, возможно, добавить определение метода для каждого существующего подкласса . На практике нагрузка варьируется в зависимости от метода.

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

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

Answer 2

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

maybeToList :: Maybe a -> [a]
maybeToList Nothing  = []
maybeToList (Just x) = [x]

Если бы Maybe было открыто, кто-то мог добавить дополнительный конструктор, и функция maybeToList внезапно сломалась бы.

В ОО это не проблема, когда вы используете наследование для расширения типа, потому что когда вы вызываете функцию, для которой нет конкретной перегрузки, она может просто использовать реализацию для суперкласса. То есть, вы можете просто вызвать printPerson(Person p) с объектом Student, если Student является подклассом Person.

В Haskell вы обычно используете классы инкапсуляции и типов, когда вам нужно расширить свои типы. Например:

class Eq a where
   (==) :: a -> a -> Bool

instance Eq Bool where
  False == False = True
  False == True  = False
  True  == False = False
  True  == True  = True

instance Eq a => Eq [a] where
  []     == []     = True
  (x:xs) == (y:ys) = x == y && xs == ys
  _      == _      = False

Теперь функция == полностью открыта, вы можете добавить свои собственные типы, сделав ее экземпляром класса Eq.

---

Обратите внимание, что была проделана работа над идеей расширяемых типов данных , но это определенно не является частью Haskell.

Answer 3

Если вы напишите такую ​​функцию, как

maybeToList Nothing = []
maybeToList (Just x) = [x]

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

Answer 4

Отметьте «Открыть типы данных и открыть функции» http://lambda -the-ultimate.org / node / 1453

В объектно-ориентированных языках это легко расширять данные, определяя новые классы, но трудно добавить новые функции. В функционале языки, ситуация обратная: добавление новых функций не создает проблемы, но расширение данных (добавление новые конструкторы данных) требует изменение существующего кода . Эта проблема поддержки обоих направлений расширяемость известна как проблема выражения . Мы представляем открытые типы данных и открытые функции как облегченное решение для выражения проблема в языке Haskell. Идея заключается в том, что конструкторы открытых данных типы и уравнения открытых функций может казаться разбросанным по всему программа. В частности, они могут проживать в разных модулях. Предполагаемая семантика выглядит следующим образом: Программа должна вести себя так, как будто данные типы и функции были закрыты, определяется в одном месте. Получатель чего-то Функция уравнения определяется наилучшее соответствие шаблону, где конкретный образец имеет приоритет над неспецифический. Мы показываем, что наши решение применимо к проблема выражения, общая программирование и исключения. Мы рисуем две реализации. Простой, вытекает из семантики, и один на основе взаимно рекурсивных модулей это разрешает отдельную компиляцию.

Answer 5

Во-первых, в отличие от ответа Чарли, это не присуще функциональному программированию. У OCaml есть концепция открытых союзов или полиморфных вариантов , которые по сути делают то, что вы хотите.

Что касается , почему , я считаю, что этот выбор был сделан для Haskell, потому что

• это позволяет типам быть предсказуемыми - они являются конечным числом конструкторов для каждого
• Легко определить свои собственные типы.
• многие функции Haskell являются полиморфными, а классы позволяют расширять пользовательские типы для соответствия параметрам функций (например, интерфейсы Java).

Так что, если вы предпочитаете иметь тип data Color r b g = Red r | Blue b | Green g, его легко сделать, и вы можете легко заставить его действовать как монада или функтор, или как вам понадобятся другие функции.

Answer 6

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

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

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

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

Фактически, AST компилятора являются одним из классических мотивирующих примеров «Банды четырех» для шаблона посетителя, который является ООП аналогом закрытых сумм и исчерпывающего сопоставления с шаблоном. Полезно поразмышлять над тем фактом, что ОО-программисты в итоге изобрели шаблон для восстановления закрытых сумм.

Аналогично, процедурные и функциональные программисты изобрели шаблоны для получения эффекта сумм. Простейшим является кодирование «запись функций», соответствующее интерфейсам ОО. Запись функций - это, по сути, таблица отправки . (Обратите внимание, что программисты на Си использовали эту технику целую вечность!) Хитрость заключается в том, что очень часто существует большое количество возможных функций данного типа - часто бесконечно много. Таким образом, если у вас есть тип записи, чьи поля являются функциями, тогда он может легко поддерживать астрономически большой или бесконечный набор альтернатив. И более того, поскольку записи создаются во время выполнения и могут быть выполнены гибко в зависимости от условий выполнения, альтернативы имеют поздний предел .

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

Функциональное программирование - и, в частности, статически типизированные разновидности ML / Haskell - давно подчеркивали композицию над поздним связыванием. Но в действительности оба вида техники существуют в обеих парадигмах и должны быть в наборе инструментов хорошего программиста.

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

Answer 7

Другой (более или менее) интуитивно понятный взгляд на типы данных и классы типов по сравнению с объектно-ориентированными классами заключается в следующем:

Класс Foo на языке ОО представляет как конкретный тип Foo , так и класс всех Foo -типов: те, которые непосредственно или косвенно происходит от Foo .

В ОО-языках вы просто неявно программируете класс Foo -типа, который позволяет вам "расширять" Foo .

Answer 8

Хорошо, здесь под словом "открыть" вы подразумеваете "может быть получен из" и не открыт в смысле Ruby и Smalltalk, где вы можете расширить класс новыми методами во время выполнения, верно?

В любом случае обратите внимание на две вещи: во-первых, в большинстве ОО-языков, которые в основном основаны на наследовании, есть способ объявить класс, чтобы ограничить его способность наследоваться. У Java есть «финал», и в C ++ для этого есть хаки. Таким образом, он просто делает по умолчанию опцией в других языках OO.

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

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