Scala: разница между стилем и ADT?

Question

В чем разница между типами моделей и абстрактными типами данных?

Я понимаю, что это основная задача для программистов Haskell, но я исхожу из фона Scala и буду интересоваться примерами в Scala. Самое лучшее, что я могу найти сейчас, это то, что typeclasses являются «открытыми», и ADT «закрыты». Было бы также полезно сравнить и сопоставить типы моделей со структурными типами.

Answer 1

АТД (которые в данном контексте являются не абстрактные типы данных, что еще одно понятие, но Алгебраические типы данных) и классы типов - это совершенно разные понятия, которые решают разные проблемы.

ADT, как следует из акронима, является типом данных. Для структурирования ваших данных необходимы ADT. Самое близкое совпадение в Scala, я думаю, представляет собой комбинацию классов дел и запечатанных признаков. Это основное средство построения сложных структур данных в Haskell. Я думаю, что самое известный пример ADT является Maybe типа:

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-ичных, так как 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" 
} 

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

class MyShow a where 
    myShow :: a -> String 

instance MyShow Int where 
    myShow x = ... 

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

Эта возможность добавления экземпляра класса типа для существующих типов является способом решения expression problem. Язык 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, имеют протоколы , которые объединяют интерфейсы и классы типов. Протоколы отправляются по одному первому аргументу, но вы можете реализовать протокол для любого существующего типа.

Answer 2

Разница между классом типа и АТД является:

• классы Используйте тип, если вы хотите, чтобы послать метод, основанный прочь типа что-то
• Используйте АТД, если вы хотите, чтобы направить метод основаны от стоимости что-то

Для примера рассмотрим функцию print:

print :: (Show a) => a -> IO() 

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

main = print 'C' 

АТДА позволяет изменить поведение функции динамически. Например, я мог бы определить:

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 

Answer 3

Ваш вопрос на самом деле затрагивает три различных понятий: абстрактных классов типов типов данных и алгебраической типов данных. Допустимо, что и «абстрактные», и «алгебраические» типы данных могут быть сокращенно «ADT»; в контексте Haskell, ADT почти всегда означает «алгебраический».

Итак, давайте определим все три условия.

Тип алгебраических данных (ADT), тип, который может быть получен путем объединения более простых типов. Основная идея здесь - «конструктор», который является символом , который определяет значение. Подумайте об этом как значение в перечислении Java-стиля , за исключением того, что он также может принимать аргументы. Простейший алгебраического типа данных имеет только один конструктор без аргументов:

data Foo = Bar 

есть только one¹ значения этого типа: Bar.Само по себе это не очень интересно; нам нужно каким-то образом создать более крупные типы.

Первый способ - дать аргументы конструктора. Например, мы можем иметь наши Bar s принимают 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. В качестве простого примера, вместо того, чтобы использовать, если выражение, вы могли бы сопоставление с образцом на 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 

_ просто означает, что мы не заботимся о ценности отцентрировать точку в.

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

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

Алгебраические и абстрактные типы - это несколько ортогональные понятия; довольно печально, что их имена делают так легко ошибочно принимать одно за другого.

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

Простейший пример: Show, который является классом всех типов, имеющих строковое представление; то есть все типы a, для которых у нас есть функция show ∷ a → String. Если тип имеет функцию show, мы говорим, что это «в Show»; иначе это не так. Большинство типов вам известно, как Int, Bool и String все размещены в Show; с другой стороны, функции (любой тип с →) являются не в Show. Вот почему GHCi не может распечатать функцию.

Класс типа определяется, какие функции должен выполнять тип, чтобы быть частью его. Например, Show может быть defined² только функцией 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 в любом месте. В частности, мы можем писать новые экземпляры после определения класса, даже в других модулях. Это то, что означает, что для товарных знаков должно быть open; в отличие от алгебраических типов данных, мы можем добавить новые вещи к классам после факта.

Существует также несколько моделей; вы можете прочитать о них в same LYAH chapter.

¹ Технически есть еще одно значение, называемое ⊥ (bottom), но пока мы его не будем игнорировать. Вы можете узнать об этом позже.

² В действительности, на самом деле имеет Show другую возможную функцию, которая принимает лист из a сек в String. В основном это взломать, чтобы строки выглядели красиво, потому что строка - это всего лишь список Char s, а не его собственный тип.