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

Вы путаете непредикативные типы с экзистенциальными типами. Импредикативные типы позволяют помещать в структуру данных полиморфные значения, а не произвольные конкретные. Другими словами [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.

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

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

Ответ @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._ требуется для включения экземпляра в область видимости. Благодаря магии имплицитов:

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

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