В чем разница между типами классов и абстрактными типами данных?
Я понимаю, что это основная задача для программистов Haskell, но я исхожу из фона Scala и буду интересоваться примерами в Scala. Самое лучшее, что я могу найти прямо сейчас, это то, что классные классы "открыты", а ADT "закрыты". Было бы также полезно сравнить и сопоставить типы моделей со структурными типами.
ADT (которые в этом контексте не являются абстрактными типами данных, что является еще одним понятием, но являются алгебраическими типами данных), а классы типов - это совершенно разные понятия, которые решают разные проблемы.
ADT, как следует из аббревиатуры, является типом данных. Для структурирования ваших данных необходимы ADT. Самое близкое совпадение в Scala, я думаю, представляет собой комбинацию классов case и запечатанных признаков. Это основное средство построения сложных структур данных в Haskell. Я думаю, что самым известным примером ADT является Maybe type:
data Maybe a = Nothing | Just a
Этот тип имеет прямой эквивалент в стандартной библиотеке Scala, называемой Option:
sealed trait Option[+T]
case class Some[T](value: T) extends Option[T]
case object None extends Option[Nothing]
Это не совсем так, как Option определяется в стандартной библиотеке, но вы получаете точку.
В основном ADT представляет собой комбинацию (в некотором смысле) нескольких названных кортежей (0-арный, как Nothing/None; 1-ary, as Just a/Some(value), возможны более высокие значения).
Рассмотрим следующий тип данных:
-- Haskell
data Tree a = Leaf | Branch a (Tree a) (Tree a)
// Scala
sealed trait Tree[+T]
case object Leaf extends Tree[Nothing]
case class Branch[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]
Это простое двоичное дерево. Оба эти определения читаются в основном следующим образом: "Бинарное дерево является либо Leaf, либо Branch, если оно является ветвью, то оно содержит некоторое значение и два других дерева". Это означает, что если у вас есть переменная типа Tree, то она может содержать либо Leaf, либо Branch, и вы можете проверить, какая из них есть, и при необходимости извлекать содержащиеся данные. Первичным средним для таких проверок и извлечения является сопоставление с образцом:
-- Haskell
showTree :: (Show a) => Tree a -> String
showTree tree = case tree of
Leaf -> "a leaf"
Branch value left right -> "a branch with value " ++ show value ++
", left subtree (" ++ showTree left ++ ")" ++
", right subtree (" ++ showTree right ++ ")"
// Scala
def showTree[T](tree: Tree[T]) = tree match {
case Leaf => "a leaf"
case Branch(value, left, right) => s"a branch with value $value, " +
s"left subtree (${showTree(left)}), " +
s"right subtree (${showTree(right)})"
}
Эта концепция очень проста, но также очень эффективна.
Как вы заметили, ADT закрыты, т.е. вы не можете добавить больше именованных кортежей после того, как тип был определен. В Haskell это выполняется синтаксически, а в Scala это достигается с помощью ключевого слова sealed, которое запрещает подклассы в других файлах.
Эти типы называются алгебраическими по причине. Именованные кортежи можно рассматривать как продукты (в математическом смысле) и "комбинации" этих кортежей как суммирование (также в математическом смысле), и такое рассмотрение имеет глубокий теоретический смысл. Например, вышеупомянутый тип двоичного дерева можно записать следующим образом:
Tree a = 1 + a * (Tree a) * (Tree a)
Но я думаю, что это не подходит для этого вопроса. Я могу найти некоторые ссылки, если вы хотите узнать больше.
Типы классов, с другой стороны, являются способом определения полиморфного поведения. Грубо типы классов - это контракты, которые предоставляет определенный тип. Например, вы знаете, что ваше значение x удовлетворяет контракту, который определяет какое-либо действие. Затем вы можете вызвать этот метод, и фактическая реализация этого контракта затем выбирается автоматически.
Обычно типы классов сравниваются с интерфейсами Java, например:
-- Haskell
class Show a where
show :: a -> String
// Java
public interface Show {
String show();
}
// Scala
trait Show {
def show: String
}
Используя это сравнение, экземпляры классов типов соответствуют реализации интерфейсов:
-- Haskell
data AB = A | B
instance Show AB where
show A = "A"
show B = "B"
// Scala
sealed trait AB extends Show
case object A extends AB {
val show = "A"
}
case object B extends AB {
val show = "B"
}
Существуют очень важные различия между интерфейсами и типами классов. Во-первых, вы можете написать собственный тип типа и сделать любой тип экземпляром:
class MyShow a where
myShow :: a -> String
instance MyShow Int where
myShow x = ...
Но вы не можете так поступать с интерфейсами, то есть вы не можете заставить существующий класс реализовать свой интерфейс. Эта функция, как вы также заметили, означает, что классы классов открыты.
Эта возможность добавления экземпляра класса типа для существующих типов является способом решения проблемы . Язык Java не имеет средств для его решения, но Haskell, Scala или Clojure имеют.
Другим различием между типами классов и интерфейсов является то, что интерфейсы являются полиморфными только по первому аргументу, а именно по неявному this. Типовые классы в этом смысле не ограничены. Вы можете определить классы типов, которые отправляют даже по возвращаемому значению:
class Read a where
read :: String -> a
Это невозможно сделать с помощью интерфейсов.
Типы классов могут быть эмулированы в Scala с использованием неявных параметров. Этот шаблон настолько полезен, что в последних версиях Scala существует даже специальный синтаксис, который упрощает его использование. Вот как это делается:
trait Showable[T] {
def show(value: T): String
}
object ImplicitsDecimal {
implicit object IntShowable extends Showable[Int] {
def show(value: Int) = Integer.toString(value)
}
}
object ImplicitsHexadecimal {
implicit object IntShowable extends Showable[Int] {
def show(value: Int) = Integer.toString(value, 16)
}
}
def showValue[T: Showable](value: T) = implicitly[Showable[T]].show(value)
// Or, equivalently:
// def showValue[T](value: T)(implicit showable: Showable[T]) = showable.show(value)
// Usage
{
import ImplicitsDecimal._
println(showValue(10)) // Prints "10"
}
{
import ImplicitsHexadecimal._
println(showValue(10)) // Prints "a"
}
Showable[T] признак соответствует типу класса, а определения неявных объектов соответствуют его экземплярам.
Как вы можете видеть, типы классов - это своего рода интерфейс, но более мощный. Вы даже можете выбрать различные реализации классов типов, в то время как код, который их использует, остается тем же. Эта мощность, однако, идет за счет шаблонов и дополнительных объектов.
Обратите внимание, что возможно записать эквивалент Haskell выше программы Scala, но для этого потребуется записать несколько модулей или обертки newtype, поэтому я не представляю их здесь.
BTW, Clojure, диалект Lisp, работающий на JVM, имеет протоколы, которые объединяют интерфейсы и типы классов. Протоколы отправляются по одному первому аргументу, но вы можете реализовать протокол для любого существующего типа.
В действительности ваш вопрос затрагивает три различных понятия: типэлементов, абстрактных типов данных и типов алгебраических данных. Достаточно смутно, как "абстрактные", так и "алгебраические" типы данных могут быть сокращенно "ADT"; в контексте Haskell, ADT почти всегда означает "Алгебраическое".
Итак, давайте определим все три члена.
Тип алгебраических данных (ADT) - это тип, который может быть создан путем объединения более простые типы. Основная идея здесь - "конструктор", который является символ, определяющий значение. Подумайте об этом как о ценности в Перемычка в стиле Java, за исключением того, что она также может принимать аргументы. Простейший алгебраический тип данных имеет только один конструктор без аргументов:
data Foo = Bar
существует только одно значение этого типа: Bar. Само по себе это не очень интересно; нам нужно каким-то образом создать более крупные типы.
Первый способ - дать аргументы конструктора. Например, мы можем иметь наш Bar взять int и строку:
data Foo = Bar Int String
Теперь Foo имеет много разных возможных значений: Bar 0 "baz", Bar 100 "abc" и т.д. Более реалистичным примером может быть запись для сотрудника, выглядящая примерно так:
data Employee = Employee String String Int
Другим способом создания более сложных типов является выбор нескольких конструкторов. Например, мы можем иметь как Bar, так и Baz:
data Foo = Bar
| Baz
Теперь значения типа Foo могут быть либо Bar, либо Baz. Это на самом деле то, как работают булевы; Bool определяется следующим образом:
data Bool = True
| False
Он работает точно так, как вы ожидали. Действительно интересные типы могут использовать оба метода для объединения. Как довольно надуманный пример, представьте формы:
data Shape = Rectangle Point Point
| Circle Point Int
Форма может быть либо прямоугольником, определяемым его двумя углами, либо окружностью, которая является центром и радиусом. (Мы просто определим Point как (Int, Int).) Достаточно справедливо. Но здесь мы сталкиваемся с проблемой: оказывается, что существуют и другие формы! Если какой-то еретик, который верит в треугольники, хочет использовать наш тип в своей модели, может ли он добавить конструктор Triangle после факта? К сожалению, нет: в Haskell алгебраические типы данных закрыты, что означает, что после факта вы не можете добавлять новые альтернативы.
Одна важная вещь, которую вы можете сделать с алгебраическим типом данных, - это совпадение с шаблоном. Это в основном означает возможность перехода на альтернативы ADT. В качестве очень простого примера вместо использования выражения if вы можете сопоставить соответствие шаблону на Bool:
case myBool of
True → ... -- true case
False → ... -- false case
Если ваши конструкторы имеют аргументы, вы также можете получить доступ к этим значениям путем сопоставления шаблонов. Используя Shape сверху, мы можем написать простую функцию area:
area shape = case shape of
Rectange (x₁, y₁) (x₂, y₂) → (x₂ - x₁) * (y₂ - y₁)
Circle _ r → π * r ^ 2
_ просто означает, что нам не важно значение точечного центра.
Это всего лишь базовый обзор алгебраических типов данных: оказывается, что еще немного интереснее. Вы можете взглянуть на соответствующую главу в разделе "Узнайте, что вы Haskell" (LYAH для краткости), чтобы узнать больше.
Теперь, что относительно абстрактных типов данных? Это относится к другой концепции. Абстрактный тип данных - это тот, где реализация не отображается: вы не знаете, как выглядят значения типа. Единственное, что вы можете сделать с этим - применить функции, экспортированные из своего модуля. Вы не можете сопоставить шаблон или создать новые значения самостоятельно. Хорошим примером на практике является Map (от Data.Map). Карта на самом деле представляет собой конкретный вид дерева двоичного поиска, но ничто в модуле не позволяет напрямую работать с древовидной структурой. Это важно, потому что дерево должно поддерживать определенные дополнительные инварианты, которые вы могли бы легко испортить. Поэтому вы всегда используете Map как непрозрачный blob.
Алгебраические и абстрактные типы - это несколько ортогональные понятия; довольно печально, что их имена делают так легко ошибочно принимать одно за другого.
Заключительная часть головоломки - это класс. Класс, в отличие от алгебраических и абстрактных типов данных, не является самим типом. Скорее, подумайте о классе как наборе типов. В частности, typeclass - это набор всех типов, которые реализуют определенные функции.
Простейшим примером является Show, который является классом всех типов, которые имеют строковое представление; т.е. все типы a, для которых мы имеем функцию show ∷ a → String. Если тип имеет функцию Show, мы говорим, что это "в Show"; иначе это не так. Большинство типов, которые вы знаете как Int, Bool и String, находятся в Show; с другой стороны, функции (любой тип с →) не находятся в Show. Вот почему GHCi не может распечатать функцию.
Класс типов определяется тем, какие функции должен выполнять тип, чтобы быть частью этого. Например, Show может быть определен² только функцией Show:
class Show a where
show ∷ a → String
Теперь, чтобы добавить новый тип, например Foo в Show, нам нужно написать экземпляр для него. Это фактическая реализация функции Show:
instance Show Foo where
show foo = case foo of
Bar → "Bar"
Baz → "Baz"
После этого Foo находится в Show. Мы можем написать экземпляр для Foo в любом месте. В частности, мы можем писать новые экземпляры после определения класса, даже в других модулях. Это то, что означает, что классные классы должны быть открыты; в отличие от алгебраических типов данных, мы можем добавлять новые вещи к классам после факта.
Кроме того, в классах есть больше; вы можете прочитать о них в той же самой главе LYAH.
¹ Технически есть еще одно значение, которое называется ⊥ (bottom), но на этот раз мы его проигнорируем. Вы можете узнать об этом позже.
² В действительности Show имеет другую возможную функцию, которая переводит список a в String. Это, в основном, хак, чтобы строки выглядели красиво, поскольку строка представляет собой список Char, а не собственный тип.
Разница между классом типа и ADT заключается в следующем:
Например, рассмотрим функцию print:
print :: (Show a) => a -> IO ()
Типы являются статическими и не могут меняться на протяжении всего жизненного цикла программы, поэтому, когда вы используете класс типа, используемый вами метод выбирается статически во время компиляции на основе выбранного типа на сайте вызова. Поэтому в этом примере я знаю, что я использую экземпляр Char для Show, даже не запуская программу:
main = print 'C'
ADT позволяют динамически изменять поведение функции. Например, я мог бы определить:
print2 :: Either Char String -> IO ()
print2 (Left c ) = putStrLn [c]
print2 (Right str) = putStrLn str
Теперь, если я вызываю print2 в некотором контексте:
print2 e
... Я не могу знать, какая ветвь принимает print2, если я не знаю значения времени выполнения e. Если e является Left, тогда я беру ветвь Left, и если e является Right, я беру ветвь Right. Иногда я могу статически рассуждать о том, какой конструктор e будет, но иногда я не могу, например, в следующем примере:
main = do
e <- readLn -- Did I get a 'Left' or 'Right'?
print2 e -- Who knows until I run the program