Неисправность с инкапсулирующими «рекурсивными типами» в Scala

Question

Извините, мне трудно найти подходящий заголовок для моей проблемы.

Я хочу моделировать следующее поведение: я разработал «язык» с выражениями, которые инкапсулируют стандартные типы Scala. Выражения могут быть либо переменными, либо последовательностями выражений. В дальнейшем A может быть стандартным типом Scala (а именно Boolean, Int, Double). Я также хочу реализовать метод замены выражений другим в выражениях (особенно в последовательностях). Я пробовал код, который я не могу скомпилировать. Я помещал кавычки, когда я действительно не знаю, какой тип поставить, но все это, вероятно, беспорядочно. У меня есть особые проблемы с вещью Sequence, из-за ее рекурсивного характера.

sealed trait Expression[A] { 
    def replace[B](a: Expression[B], b: Expression[B]): Expression[?] 
} 

trait Variable[A] extends Expression[A] { 
    def replace[B](a: Expression[B], b: Expression[B]) = 
    if (a == this) b else this 
} 

case class Sequence[A <: Expression[B]](values: Seq[A]) extends Expression[A] { 
    def replace[B](a: Expression[B], b: Expression[B]) = 
    if (a == this) b 
    else Sequence(values.map(_.replace(a, b))) 
} 

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

Благодарим за помощь.

Answer 1

Похоже, вы столкнулись с одним из тех угловых случаев, где Scala не имеет элегантного решения.

Что вам нужно вместо Expression[?], поскольку тип возвращаемого типа фактически представляет собой тип, который представляет «этот тип», являющийся типом, в котором черта фактически смешивается. В Scala нет сокращения, которое позволяет вам выразить это простым способом, и вы также не можете использовать this.type, поскольку это слишком специфично и может использоваться только тогда, когда вы действительно всегда возвращаете this.

Решение обычно быстро вводит шаблон сгибания ума. Коллекции Scala, например, страдают от одной и той же проблемы, такие черты, как MapLike, нуждаются в кодировании подобных вещей.

Я попытался быстро модифицировать образец для кодирования такого типа. Я удостоверился, что он компилирует, но я не запустить его:

sealed trait Expression[A, ThisType <: Expression[A, ThisType]] { 
    def replace[B,C <: Expression[B,C]](a: Expression[B,C], b: Expression[B,C]): ThisType 
} 

trait Variable[A] extends Expression[A, Variable[A]] { 
    def replace[B,C <: Expression[B,C]](a: Expression[B,C], b: Expression[B,C]) = 
    if (a == this) b.asInstanceOf[Variable[A]] else this 
} 

case class Sequence[A <: Expression[_,A]](values: Seq[A]) extends Expression[A, Sequence[A]] { 
    def replace[B,C <: Expression[B,C]](a: Expression[B,C], b: Expression[B,C]) = 
    if (a == this) b.asInstanceOf[Sequence[A]] 
    else Sequence(values.map(_.replace(a, b))) 
} 

Он даже использовать бросок, который обычно является запах сам по себе, но я не уверен, что есть способ избежать в этом случае. По крайней мере, это безопасно, мы знаем, что он должен иметь правильный тип, просто компилятор этого не знает. :-)

Answer 2

Обычно в таких ситуациях существует необходимая связь между A и B. Например, рассмотрим, что происходит, когда вы добавляете элемент в (гипотетической и очень упрощенно) Тип последовательности:

class Sequence[+A] { 
    def +: [B >: A](b: B): Sequence[B] = { 
    /* Build the new sequence with b at the beginning and this sequence's elments after */ 
    } 
} 

Так что в вашем случае (если этот шаблон применяется для вас), подпись в Expression[A] будет:

def replace[B >: A](a: Expression[B], b: Expression[B]): Expression[B] 

Answer 3

Благодарим за ответы. Я закончил упрощение своей проблемы, чтобы получить более простое решение. Я просто «уплощенные» параметр типа последовательностей:

case class Sequence[A] (values: Seq[Expression[A]]) extends Expression[A] { 
    def replace[B <: A](a: Expression[A], b: Expression[B]) { 
    // (Code in initial question) 
    } 
} 

A в Expression означает, что теперь Expression либо переменная типа A, последовательность переменных типа A, последовательность последовательности переменных типа A ...

Я теряю выразительность здесь, но выигрываю в удобстве использования.Наличие двух параметров для выражения было слишком сложным и нарушило взаимодействие Java. Возможно, я попытаюсь улучшить это позже.