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

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

data Maybe a = Nothing | Just a

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

8 56
oop type-systems haskell primitive-types functional-programming

8 ответов:

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

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

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

в OO это не проблема, когда вы используете наследование для расширения типа, потому что когда вы вызываете функцию, для которой нет конкретной перегрузки, она может просто использовать реализацию суперкласса. То есть, вы можете позвонить 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 класса.

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

66

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

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

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

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

  • классов,

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

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

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

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

78

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

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

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

15

Проверьте "открытые типы данных и открытые функции"http://lambda-the-ultimate.org/node/1453

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

11

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

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

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

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

7

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

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

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

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

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

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

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

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

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

5

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

класс Фу в языке OO представляет как конкретный тип Фу а также класс всех Фу - типы: те, которые прямо или косвенно получены из Фу.

в языках OO вы просто неявно программируете против класса Футипы что позволяет вам "расширить"Фу.

2

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

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

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

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

1