Предсказательные типы против простого старого подтипа

Question

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

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

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

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

Тем не менее, основным, общеизвестным недостатком подтипирования по сравнению с классами типов является тесная связь: моим типам A, B и C должно быть подчинено их поведение T. Предположим, что это главный нарушитель правил,и я не могу использовать подтипы.Таким образом, золотая середина в Scala - сутенеры ^ H ^ H ^ H ^ H ^ Подразумеваемые преобразования: учитывая некоторые A => T, B => T и C => T в неявном объеме, я снова могу довольно счастливо заполнить List[T] моим *Значения 1048 *, B и C ...

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

Хорошо, поэтому мой вопрос, наконец, таков:Предположим, комбинация из пары вопросов, которые ранее задавались здесь: «Почему следует избегать подтипов?» и «Преимущества подтипов над классами типов» ... существует ли объединяющая теория, которая говоритнеимоверный полиморфизм и полиморфизм подтипа - это одно и то же?Являются ли неявные преобразования каким-то образом тайным дитя любви двух?И может ли кто-нибудь сформулировать хороший, чистый шаблон для выражения нескольких границ (как в последнем примере выше) в Scala?

Answer 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 содержит скрытое поле, в котором хранится словарь классов типов (он же vtable / implicit), поэтому нам нужен тип оболочки.

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

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

Answer 2

@ Хаммар ответ совершенно прав. Вот скала способ сделать это. Для примера я возьму 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. Более точный тип super super между 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

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