Непротиворечивые типы против простого старого подтипирования

Ответ 1

Вы смешиваете нечистоплотные типы с экзистенциальными типами. Непротиворечивые типы позволяют вводить полиморфные значения в структуру данных, а не произвольные конкретные. Другими словами, [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)]. Правильный словарь для каждого типа просматривается и сохраняется в скрытом поле автоматически в точке, где мы обертываем каждое число.

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

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

Ответ 2

Ответ на @hammar совершенно прав. Вот способ 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._. Благодаря волшебству implicits:

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

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