Найдите наибольший общий подтип двух типов Scala

В соответствии с этим вопросом я пытаюсь найти способ заставить компилятор Scala вывести наибольший общий подтип двух типов А и В.

Что-то вроде «А без Б», где определение такое:

(A without B = C) === (A = C with B)

Или функция типа, которая возвращает C, где:

РЕДАКТИРОВАТЬ:

A <: C && C <:!< B

т.е. A является подтипом C, а C не является подтипом B

На самом деле я ожидаю, что кто-то укажет, что это не то же самое, что «самый большой общий подтип», поскольку мне на самом деле не требуется этот A <: B.

Применение:

trait Syntax

trait ANYSYNTAX extends Syntax
trait NUMERIC extends ANYSYNTAX
trait DISCRETE extends ANYSYNTAX
trait POSITIVE extends ANYSYNTAX
trait CONST extends ANYSYNTAX     
type NUMCONST = NUMERIC with CONST
type POSCONST = POSITIVE with CONST
type ORDINALCONST = DISCRETE with CONST
type INTEGER = NUMERIC with DISCRETE
type POSNUM = POSITIVE with NUMERIC
type POSINT = POSNUM with INTEGER
type INTCONST = INTEGER with NUMCONST with ORDINALCONST
type POSNUMCONST = POSNUM with POSCONST with NUMCONST
type POSINTCONST = POSNUMCONST with INTCONST with POSINT

Затем я хотел бы иметь возможность распространять ограничения типа следующим образом:

abstract class Expression[+R]( val args: Expression[_]* )

case class Add[A <: R, R <: NUMERIC]( arg1: Expression[A], arg2: Expression[A] ) extends Expression[R] {
case class Subtract[A <: R, R : A without POSITIVE]( arg1: Expression[A], arg2: Expression[A] ) extends Expression[R] {
case class Multiply[A <: R, R <: NUMERIC]( arg1: Expression[A], arg2: Expression[A] ) extends Expression[R]{
case class Divide[A <: R, R : A without DISCRETE]( arg1: Expression[A], arg2: Expression[A] ) extends Expression[R] {

Я пытался придумать что-то, используя некоторые ограничения типа, заимствованные из других ответов SO:

sealed class =!=[A,B]

trait LowerPriorityImplicits {
  implicit def equal[A]: =!=[A, A] = sys.error("should not be called")
}
object =!= extends LowerPriorityImplicits {
  implicit def nequal[A,B](implicit same: A =:= B = null): =!=[A,B] =
    if (same != null) sys.error("should not be called explicitly with same type")
    else new =!=[A,B]
}

// Encoding for "A is not a subtype of B"
trait <:!<[A, B]

// Uses ambiguity to rule out the cases we're trying to exclude
implicit def nsub[A, B] : A <:!< B = null
implicit def nsubAmbig1[A, B >: A] : A <:!< B = null
implicit def nsubAmbig2[A, B >: A] : A <:!< B = null

У меня есть несколько тестовых случаев:

implicitly[POSINT <:!< CONST]
implicitly[POSITIVE <:!< OPINION]
implicitly[DOGMA <:!< CONST]

implicitly[POSINTCONST <:< POSITIVE with CONST]
implicitly[POSINTCONST <:< POSCONST]
implicitly[POSITIVE with CONST <:!< POSINTCONST]

implicitly[POSITIVE =:= POSCONST without CONST]
implicitly[NUMERIC =:= INTEGER without DISCRETE]
implicitly[POSINT =:= POSINTCONST without CONST]

Они должны потерпеть неудачу:

implicitly[POSINT =:= POSINTCONST without OPINION]
implicitly[POSINT with OPINION =!= POSINTCONST without OPINION]

scala type-constraints
person RealName    schedule 19.08.2013    source источник
comment
Я не уверен, что понимаю ваше определение. Звучит так, будто если A <: B, то C не существует, а иначе C — это просто A.   -  person Travis Brown    schedule 19.08.2013
comment
@TravisBrown Например, C: POSINT, B: CONST. Тогда A: C with B = POSINTCONST. Согласно моему первому определению, POSINTCONST without CONST =:= POSINT. Если, с другой стороны, A <:!< B, например. NUMCONST without POSITIVE то я бы ожидал C:NUMCONST как вы говорите.   -  person RealName    schedule 19.08.2013
comment
На самом деле @Travis Я сделал ошибку во втором определении (теперь исправлено, надеюсь).   -  person RealName    schedule 24.08.2013

Ответы (2)


arrow_upward
3
arrow_downward

Похоже, вам нужна наименьшая верхняя граница (LUB) типов scala? Я бы посмотрел на библиотеку Майлза Shapeless для вдохновения, где у них действительно есть Ограничение LUB.

Или, если вам нужна большая нижняя граница (GLB), боюсь, мне придется отослать вас к использованию определения макроса, в котором вы можете получить либо LUB, либо GLB, см. Типы.

person wheaties    schedule 19.08.2013
comment
Lubs и glbs также могут быть вычислены с помощью отражения во время выполнения. - person Eugene Burmako; 19.08.2013
comment
@wheaties Я видел Shapeless и «заглядывал» в него, но я нахожу его довольно непроницаемым. Я считаю, что GLB - это то, что я хочу, и эта ссылка может быть полезной, однако я надеялся получить более подробный ответ. - person RealName; 20.08.2013
comment
Отражение во время выполнения @Eugene было бы хорошо, поскольку, в конце концов, я хочу иметь возможность создавать новые выражения во время выполнения. - person RealName; 20.08.2013

arrow_upward
1
arrow_downward

Что ж, после случайных ударов по клавиатуре и прочтения всего, что я мог понять об ограничениях типов, вот что я придумал:

// A without B is C
sealed abstract class isWithout[A, B, C]

object Syntax {

  implicit def composedWithout[A <: C, B, C](implicit ev: C <:!< B): isWithout[A, B, C] = new isWithout[A, B, C] {
    def apply(a: A) = a
  }

  type without[A, B] = {
    type l[C] = isWithout[A, B, C]
  }
}

Проверьте, работает ли это:

implicitly[isWithout[POSCONST, POSITIVE, CONST]]
implicitly[isWithout[POSINTCONST, DISCRETE, POSNUMCONST]]
implicitly[isWithout[POSINTCONST, DISCRETE, POSITIVE]]
implicitly[isWithout[POSNUM, CONST, POSNUM]]
implicitly[isWithout[POSCONST, CONST, POSITIVE ]]
implicitly[isWithout[POSCONST, POSITIVE, CONST ]]
implicitly[isWithout[INTEGER, DISCRETE, NUMERIC ]]
implicitly[isWithout[POSINTCONST, CONST, POSINT ]]

И терпит неудачу, когда он должен:

implicitly[isWithout[POSINTCONST, INTCONST, POSINTCONST]]
implicitly[isWithout[NUMERIC, ANYSYNTAX, ANYSYNTAX]]
implicitly[isWithout[INTEGER, POSITIVE, POSINT]]
implicitly[isWithout[POSNUM, DISCRETE, POSCONST]]

implicitly заставляет компилятор искать неявную функцию в текущей неявной области видимости, которая может создать объект требуемого типа (в данном случае экземпляр класса isWithout). Если он находит тот, который удовлетворяет сигнатуре типа, он компилируется (я не думаю, что имеет значение, что возвращает метод apply, определенный в классе). Важным моментом является подпись типа, в которой используется <:!<, упомянутый в вопросе и заимствованный из другого ответа SO Майлза.

Эта сигнатура типа говорит: A является подтипом C, а C не должен быть подтипом B. Альтернативная версия (соответствующая первому определению в вопросе) будет:

implicit def composedWithout[A <: C with B, B, C](implicit ev: C <:!< B): isWithout[A, B, C] = new isWithout[A, B, C] {
  def apply(a: A, b: B) = a
}

Это можно использовать несколькими способами:

  1. Чтобы проверить правильность иерархии типов (т. е. тестовых случаев), как показано выше, используйте implicitly.

  2. Чтобы указать тип параметра метода:

    def test[R : without[POSINTCONST, DISCRETE]#l](v: R) = v

    Обратите внимание, что здесь используется проекция типа without#l[C] = isWithout[A, B, C] в качестве контекстной привязки, которую компилятор десахарит:

    def test[R](v: R)(implicit $ev0: isWithout[POSINTCONST, DISCRETE, R]) = v

    Таким образом, требуется, чтобы указанный имплицит находился в области видимости.

  3. В качестве ограничения типа, как запрошено в исходном вопросе:

    case class Subtract[A <: R, R <: A without POSITIVE]( arg1: Expression[A], arg2: Expression[A] ) extends BinaryPrimitive[A, R]( arg1, arg2 )

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

person RealName    schedule 24.08.2013