Изграждане на варианти на вложени класове case

Така че получих нещо подобно:

abstract class Term
case class App(f:Term,x:Term) extends Term
case class Var(s:String) extends Term
case class Amb(a:Term, b:Term) extends Term //ambiguity

И един термин може да изглежда така:

App(Var(f),Amb(Var(x),Amb(Var(y),Var(z))))

Така че това, от което се нуждая, са всички варианти, които са посочени от класа Amb. Това се използва за представяне на двусмислена гора за анализ и искам да напиша проверка на всеки възможен вариант и да избера правилния. В този пример ще ми трябва:

App(Var(f),Var(x))
App(Var(f),Var(y))
App(Var(f),Var(z))

Кой е най-добрият начин за създаване на тези вариации в scala? Ефективността би била добра, но всъщност не е изискване. Ако е възможно, обичам да се въздържам от използването на отражение.


scala case-class
person schlicht    schedule 26.09.2013    source източник
comment
Обърнете внимание, че може да искате да представите факта, че някои изрази са детерминистични, а други не са в системата от типове (така че например да не се притеснявате за съвпадение на Amb, след като сте изпълнили тази операция). Ето бърза скица на това как може да изглежда това.   -  person Travis Brown    schedule 26.09.2013
comment
Да, помислих за това, но вече имам доста голям абстрактен синтаксис и това би го направило огромен.   -  person schlicht    schedule 03.10.2013

Отговори (3)


arrow_upward
5
arrow_downward

Scala осигурява съпоставяне на шаблони за решаване на тези проблеми. Решението би изглеждало така:

def matcher(term: Term): List[Term] = {
  term match {
    case Amb(a, b) => matcher(a) ++ matcher(b)
    case App(a, b) => for { va <- matcher(a); vb <- matcher(b) } yield App(va, vb)
    case v: Var    => List(v)
  }
}
person Mark    schedule 26.09.2013

arrow_upward
4
arrow_downward

Можете да направите това доста чисто с рекурсивна функция, която пресича дървото и разширява неяснотите:

sealed trait Term
case class App(f: Term, x: Term) extends Term
case class Var(s: String) extends Term
case class Amb(a: Term, b: Term) extends Term

def det(term: Term): Stream[Term] = term match {
  case v: Var    => Stream(v)
  case App(f, x) => det(f).flatMap(detf => det(x).map(App(detf, _)))
  case Amb(a, b) => det(a) ++ det(b)
}

Обърнете внимание, че използвам запечатана характеристика вместо абстрактен клас, за да се възползвам от способността на компилатора да проверява изчерпателността.

Работи според очакванията:

scala> val app = App(Var("f"), Amb(Var("x"), Amb(Var("y"), Var("z"))))
app: App = App(Var(f),Amb(Var(x),Amb(Var(y),Var(z))))

scala> det(app) foreach println
App(Var(f),Var(x))
App(Var(f),Var(y))
App(Var(f),Var(z))

Ако можете да промените Term API, бихте могли повече или по-малко еквивалентно да добавите def det: Stream[Term] метод там.

person Travis Brown    schedule 26.09.2013

arrow_upward
0
arrow_downward

Тъй като моят абстрактен синтаксис е доста голям (и имам няколко) и опитах късмета си с Kiama. И така, ето версията, публикувана от Травис Браун и Марк с Киама.

Не е красиво, но се надявам да работи. Коментари са добре дошли.

  def disambiguateRule: Strategy = rule {
    case Amb(a: Term, b: Term) =>
      rewrite(disambiguateRule)(a).asInstanceOf[List[_]] ++
      rewrite(disambiguateRule)(b).asInstanceOf[List[_]]
    case x => 
      val ch = getChildren(x)
      if(ch.isEmpty) {
        List(x)
      }
      else {
        val chdis = ch.map({ rewrite(disambiguateRule)(_) }) // get all disambiguate children
        //create all combinations of the disambiguated children
        val p = combinations(chdis.asInstanceOf[List[List[AnyRef]]]) 
        //use dup from Kiama to recreate the term with every combination
        val xs = for { newchildren <- p } yield dup(x.asInstanceOf[Product], newchildren.toArray)
        xs
      }
  }

  def combinations(ll: List[List[AnyRef]]): List[List[AnyRef]] = ll match {
    case Nil      => Nil
    case x :: Nil => x.map { List(_) }
    case x :: xs  => combinations(xs).flatMap({ ys => x.map({ xx => xx :: ys }) })
  }

  def getChildren(x: Any): List[Any] = {
    val l = new ListBuffer[Any]()
    all(queryf {
      case a => l += a
    })(x)
    l.toList
  }
person schlicht    schedule 04.10.2013