Почему алгебраические типы данных Haskell “закрываются”?
Я не совсем уверен, что вы просите, поэтому я просто предположу:
Если вы хотите отсортировать этот массив без каких-либо операций сравнения, то вы должны использовать сортировку распределения, например Radix
Если вы хотите отсортировать ваш массив без какого-либо встроенного метода сортировки, вам нужно создать свой собственный метод. Пример кода
7 ответов
Тот факт, что ADT закрыты, значительно упрощает написание общих функций. Это функции, которые всегда производят результат для всех возможных значений своего типа, например.
maybeToList :: Maybe a -> [a]
maybeToList Nothing = []
maybeToList (Just x) = [x]
Если бы Maybe было открыто, кто-то мог бы добавить дополнительный конструктор, и функция mightToList была бы внезапно обрыв.
В объектно-ориентированном стиле это не проблема, когда вы используете наследование для расширения типа, потому что, когда вы вызываете функцию, для которой нет определенной перегрузки, она может просто использовать реализацию для суперкласса. То есть, вы можете вызвать 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
Теперь,
Ответ связан с тем, как легко расширять код, напряжением между классами и алгебраическими типами данных, которое Фил Вадлер назвал «проблемой выражения»:
С алгебраическими данными типы,
Очень дешево добавлять новую операцию для вещей : вы просто определяете новую функцию. Все старые функции в этих вещах продолжают работать без изменений.
Очень дорого добавлять новые вещи : вам нужно добавить новый конструктор к существующему типу данных , и вы должны отредактировать и перекомпилировать каждую функцию, которая использует этот тип .
С классами,
Очень дешево добавить новый тип : просто добавьте новый подкласс, и при необходимости вы определите специализированные методы в этом классе, для всех существующих операций. Суперкласс и все остальные подклассы продолжают работать без изменений.
Добавление новой операции к объектам является очень дорогим : вы должны добавить объявление нового метода к суперклассу и, возможно, добавить определение метода к каждому существующему подклассу . На практике нагрузка варьируется в зависимости от метода.
Итак, алгебраические типы данных закрыты, потому что закрытый тип хорошо поддерживает определенные виды эволюции программ. Например, если ваши типы данных определяют язык, легко добавить новые проходы компилятора без аннулирования старых или изменения данных.
Возможно иметь «открытые» типы данных, но, за исключением тщательно контролируемых обстоятельств, проверка типов становится сложной. Тодд Миллстайн выполнил очень красивую работу над дизайном языка, который поддерживает открытые алгебраические типы и расширяемые функции, и все это с модульной системой проверки типов. Мне было очень приятно читать его статью.
Установите флажок «Открытые типы данных и открытые функции» http://lambda-the-ultimate.org/node/1453
В объектно-ориентированных языках это легко расширять данные, определяя новые классы, но сложно добавить новые функции. В функциональном языках ситуация обратная: добавление новых функций не создает проблемы, но расширение данных (добавление новые конструкторы данных) требует изменение существующего кода . Эта проблема поддержки обоих направлений расширяемость известна как проблема выражения . Мы представляем открытые типы данных и открытые функции как легкое решение выражения проблема в языке Haskell. идея состоит в том, что конструкторы открытых данных типы и уравнения открытых функций может казаться разбросанным по всему программа. В частности, они могут находятся в разных модулях. предполагаемая семантика выглядит следующим образом: программа должна вести себя так, как будто данные типы и функции были закрыты, определены в одном месте. Получатель чего-то функция уравнения определяется наиболее подходящее сопоставление с образцом, где конкретный шаблон имеет приоритет над неспецифический. Мы показываем, что наши решение применимо к проблема выражения, общий программирование и исключения. Мы зарисовываем две реализации. Простой, полученный из семантики, и один на основе взаимно рекурсивных модулей который позволяет раздельную компиляцию.
Если вы напишете функцию наподобие
maybeToList Nothing = []
maybeToList (Just x) = [x]
, то вы знаете, что она никогда не приведет к ошибке выполнения, потому что вы рассмотрели все случаи. Это перестает быть истинным, как только тип Maybe становится расширяемым. В тех случаях, когда вам нужен расширяемый тип (а они встречаются реже, чем вы думаете), каноническим решением Haskell является использование класса типа.
Во-первых, в противовес ответу Чарли, это не свойственно функциональному программированию. OCaml имеет концепцию открытых объединений или полиморфных вариантов , которые по сути делают то, что вы хотите.
Что касается почему , я считаю, что этот выбор был сделан для Haskell, потому что
- это позволяет типам быть предсказуемыми - их всего лишь конечное число конструкторов для каждого
- легко определять свои собственные типы.
- многие функции Haskell полиморфны, и классы позволяют расширять настраиваемые типы для соответствия параметрам функций (подумайте об интерфейсах Java).
Так что, если вы предпочитаете цвет данных rbg = Red r | Синий б | Зеленый тип g , его легко создать, и вы можете легко заставить его действовать как монада, функтор или другие функции, которые потребуются.
Другой (более или менее) интуитивный способ взглянуть на типы данных и классы типов по сравнению с К объектно-ориентированным классам относятся следующие:
Класс Foo в объектно-ориентированном языке представляет как конкретный тип Foo , так и класс всех Foo -типов: тех, которые являются непосредственно или косвенно производный от Foo .
В объектно-ориентированных языках вы просто случайно запрограммировали неявно против класса Foo -типов, который позволяет вам «расширять» Foo .
Хорошо, под «открытым» здесь вы подразумеваете «может быть производным от», а не открывать в смысле Ruby и Smalltalk, где вы можете расширить класс новыми методами при выполнении- время, верно?
В любом случае, обратите внимание на две вещи: во-первых, в большинстве объектно-ориентированных языков, которые в основном основаны на наследовании, есть способ объявить класс, чтобы ограничить его возможность наследования. В Java есть «финал», и в C ++ для этого есть хаки. Поэтому он просто делает опцию по умолчанию для других объектно-ориентированных языков.
Во-вторых, вы можете по-прежнему создавать новый тип, который использует закрытый ADT и добавляет другие методы или другие реализации. Так что на самом деле вы не ограничены таким образом. Опять же, формально кажется, что они обладают одинаковой силой; то, что вы можете выразить в одном, можно выразить в другом.
На самом деле функциональное программирование - это совсем другая парадигма («шаблон»). Если вы войдете в него с ожиданием, что он должен быть похож на объектно-ориентированный язык, вы будете регулярно удивляться.