Импрессивные типы против простого старого подтипирования

Question

На прошлой неделе мой друг представлял собой, казалось бы, безобидный вопрос языка Scala, на который у меня не было хорошего ответа: есть ли простой способ объявить коллекцию вещей, принадлежащих к некоторому обычному классу , Конечно, в Scala нет первоклассного понятия «typeclass», поэтому мы должны думать об этом с точки зрения черт и границ контекста (т. Е. Implicits).

В частности, учитывая некоторые черты T[_] представляющих класс типов, а также типов A, B и C с соответствующим implicits в рамках T[A], T[B] и T[C], мы хотим объявить что-то вроде List[T[a] forAll { type a }], в которую мы можем бросить экземпляры A , B и C с безнаказанностью. Это, конечно, не существует в Scala; a question last year обсуждает это более подробно.

Естественный вопрос о последующей деятельности - «как это делает Хаскелл?» Ну, GHC, в частности, имеет расширение системы типа impredicative polymorphism, описанное в документе "Boxy Types". Короче говоря, с учетом спецификации T можно юридически построить список [forall a. T a => a]. Учитывая объявление этой формы, компилятор выполняет некоторую магию передачи словаря, которая позволяет нам сохранять экземпляры typeclass, соответствующие типам каждого значения в списке во время выполнения.

Вещь, «передача словарям» звучит так же, как «vtables». В объектно-ориентированном языке, таком как Scala, подтипирование является гораздо более простым, естественным механизмом, чем подход «Типы Boxy». Если наши A, B и C все расширят признак T, тогда мы можем просто объявить List[T] и быть счастливыми. Аналогично, как отмечает Майлз в комментарии ниже, если все они расширят черты , T2 и T3, то я могу использовать List[T1 with T2 with T3] в качестве эквивалента импрессивного Haskell [forall a. (T1 a, T2 a, T3 a) => a].

Однако основной, хорошо известный недостаток с подтипами по сравнению с классами типов является тесной связью: мои A, B и C типов должны иметь их T поведения, запеченные в Давайте предположим, что это крупный dealbreaker, и я могу. 't использование подтипирование. Таким образом, середина в Scala является сутенеры^преобразования H^H^H^H^Himplicit: даны некоторые A => T, B => T и C => T в неявной области, я могу снова вполне счастливо заселить List[T] с моим A, B и C ценностей ...

... до List[T1 with T2 with T3]. В этот момент, даже если у нас есть неявные преобразования A => T1, A => T2 и A => T3, мы не можем поместить в список A. Мы могли бы реструктурировать наши неявные преобразования, чтобы буквально предоставить A => T1 with T2 with T3, но я никогда не видел, чтобы кто-то делал это раньше, и это похоже на еще одну форму жесткой связи.

Итак, мой вопрос, наконец, я полагаю, сочетание пару вопросов, которые ранее попросили здесь: "why avoid subtyping?" и "advantages of subtyping over typeclasses" ... есть некоторая объединяющая теория, которая говорит непредикативный полиморфизм и подтип полиморфизм один и те же ? Являются ли скрытые преобразования каким-то тайным любовным ребенком этих двух? И может ли кто-нибудь сформулировать хороший, чистый шаблон для выражения нескольких границ (как в последнем примере выше) в Scala?

Answer 1

Вы вводите в заблуждение неспецифические типы с экзистенциальными типами.Импрессивные типы позволяют поместить значения polyorphic в структуру данных, а не произвольные конкретные. Другими словами, [forall a. Num a => a] означает, что у вас есть список, в котором каждый элемент работает как любой числовой тип, поэтому вы не можете указать, например. Int и Double в виде [forall a. Num a => a], но вы можете положить что-то вроде 0 :: Num a => a. Империкативные типы не то, что вы хотите здесь.

Что вы хотите - это экзистенциальные типы, то есть [exists a. Num a => a] (не настоящий синтаксис Haskell), в котором говорится, что каждый элемент является неизвестным числовым типом. Для того, чтобы написать это в Haskell, однако, нам нужно ввести тип данных обертки:

data SomeNumber = forall a. Num a => SomeNumber a 

Обратите внимание на изменения от exists до forall. Это потому, что мы описываем конструктор . Мы можем поместить любой числовой тип в, но тогда система типа «забывает», какой тип был. Как только мы берем его обратно (путем сопоставления с образцом), все, что мы знаем, это то, что это некоторый числовой тип. То, что происходит под капотом, состоит в том, что тип SomeNumber содержит скрытое поле, в котором хранится словарь типа type (aka. Vtable/implicit), поэтому нам нужен тип оболочки.

Теперь мы можем использовать тип [SomeNumber] для списка произвольных чисел, но нам нужно обернуть каждое число на пути, например. [SomeNumber (3.14 :: Double), SomeNumber (42 :: Int)]. Правильный словарь для каждого типа просматривается и сохраняется в скрытом поле автоматически в точке, где мы обертываем каждое число.

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

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

data TwoNumbers = forall a. Num a => TwoNumbers a a 

f :: TwoNumbers -> TwoNumbers 
f (TwoNumbers x y) = TwoNumbers (x+y) (x*y) 

list1 = map f [TwoNumbers (42 :: Int) 7, TwoNumbers (3.14 :: Double) 9] 
-- ==> [TwoNumbers (49 :: Int) 294, TwoNumbers (12.14 :: Double) 28.26] 

или даже более интересные вещи. Как только мы сопоставим шаблон с оберткой, мы возвращаемся в землю классов классов. Хотя мы не знаем, какие типы x и y, мы знаем, что они те же, и у нас есть правильный словарь для выполнения числовых операций над ними.

Все вышеперечисленное работает аналогично с несколькими типами классов. Компилятор будет просто генерировать скрытые поля в типе обертки для каждой таблицы vtable и вносить их все в область, когда мы сопоставляем шаблон.

data SomeBoundedNumber = forall a. (Bounded a, Num a) => SBN a 

g :: SomeBoundedNumber -> SomeBoundedNumber 
g (SBN n) = SBN (maxBound - n) 

list2 = map g [SBN (42 :: Int32), SBN (42 :: Int64)] 
-- ==> [SBN (2147483605 :: Int32), SBN (9223372036854775765 :: Int64)] 

Как я очень новичок, когда речь идет о Scala, я не уверен, что могу помочь с заключительной части Вашего вопроса, но я надеюсь, что это, по крайней мере прояснилась некоторые неясности и дал вам некоторые идеи о том, как действовать.

Answer 2

@ Ответ на хаммар совершенно прав. Вот способ scala сделать это.Для примера я возьму Show как класс типа и значения i и d упаковать в списке:

// The type class 
trait Show[A] { 
    def show(a : A) : String 
} 

// Syntactic sugar for Show 
implicit final class ShowOps[A](val self : A)(implicit A : Show[A]) { 
    def show = A.show(self) 
} 

implicit val intShow = new Show[Int] { 
    def show(i : Int) = "Show of int " + i.toString 
} 

implicit val stringShow = new Show[String] { 
    def show(s : String) = "Show of String " + s 
} 


val i : Int = 5 
val s : String = "abc" 

То, что мы хотим, чтобы иметь возможность запустить следующий код

val list = List(i, s) 
for (e <- list) yield e.show 

Строительство список прост, но список не будет «запоминать» точный тип каждого из его элементов. Вместо этого он будет поднимать каждый элемент до общего супер-типа T. Более точный супер супер тип между String и Int составляет Any, тип списка List[Any].

Проблема в том, что забыть и что запомнить? Мы хотим забыть точный тип элементов, но мы хотим помнить, что это все экземпляры Show. Следующий класс делает точно, что

abstract class Ex[TC[_]] { 
    type t 
    val value : t 
    implicit val instance : TC[t] 
} 

implicit def ex[TC[_], A](a : A)(implicit A : TC[A]) = new Ex[TC] { 
    type t = A 
    val value = a 
    val instance = A 
} 

Это кодирование экзистенциальным:

val ex_i : Ex[Show] = ex[Show, Int](i) 
val ex_s : Ex[Show] = ex[Show, String](s) 

Это пакет значения с соответствующим экземпляром класса типа.

Наконец, мы можем добавить экземпляр Ex[Show]

implicit val exShow = new Show[Ex[Show]] { 
    def show(e : Ex[Show]) : String = { 
    import e._ 
    e.value.show 
    } 
} 

import e._ требуется для приведения экземпляра в область видимости. Благодаря волшебству неявки:

val list = List[Ex[Show]](i , s) 
for (e <- list) yield e.show 

который очень близок к ожидаемому коду.