scala définir correctement une valeur vide pour un type de données abstrait

Question

J'ai un ADT comme suit:

sealed trait Tree[A] 
case object EmptyTree extends Tree[Nothing] 
case class Leaf[A](value: A) extends Tree[A] 
case class Node[A](op: Seq[A] => A, branches: Tree[A]*) extends Tree[A] 

Lorsque je tente de construire une fonction pour créer au hasard des arbres que je reçois un problème avec le EmptyTree, le système de type ne laissez pas passer par

def create(acc: Tree[A], currentDepth: Int): Tree[A] = currentDepth match { 
    case maxDepth => Leaf(terminalSet(r.nextInt(terminalSet.length))) 
    case 0 => { 
     val op_pos = r.nextInt(fSetLength) 
     val branches: Seq[Tree[A]] = for (i <- 0 to r.nextInt(fSetLength)) yield create(EmptyTree, currentDepth+1) 
     Node(functionSet(op_pos)._1, branches:_*) 
    } 
    case _ => { 
     if (r.nextFloat() <= probF) { 
     val op_pos = r.nextInt(fSetLength) 
     val branches = for (i <- 0 to r.nextInt(fSetLength)) yield create(EmptyTree, currentDepth + 1) 
     Node(functionSet(op_pos)._1, branches:_*) 
     } 
     else 
     Leaf(terminalSet(r.nextInt(terminalSet.length))) 
    } 
    } 
    create(EmptyTree, 0) 

essentiellement en create(EmptyTree, currentDepth + 1) il se plaint qu'il attend un Tree[A] et reçoit un EmptyTree.type

Answer 1

Les objections du compilateur sont justifiées. Le compilateur attend Tree[A] et vous passez EmptyTree, dont le super type est Tree[Nothing]. A priori, il n'y a pas de relation de sous-typage entre ces deux types.

Ce que vous voulez est Tree être covariant: si X <: Y puis Tree[X] <: Tree[Y]. Puis, comme Nothing <: A pour toutA vous obtenez EmptyTree.type <: Tree[A] et vous pouvez toujours passer EmptyTree chaque fois que vous avez besoin d'un Tree[A].

La syntaxe pour déclarer le paramètre A dans Tree covariant est Tree[+A]; changer cela et votre code devrait compiler.

Ceci est un bon poste sur covariance et contravariance à Scala: Be friend with covariance and contravariance

MISE À JOUR Après votre questioning answer je l'ai fait regardé vos constructeurs pour Tree et, tel que défini, vous ne pouvez pas faire Tree covariant. Malheureusement, le compilateur ne se plaindra pas (vous voyez, il devrait en fait se plaindre plus). Votre op dans Node est contravariant sur Seq[A], et donc vous ne pouvez pas faire Node covariant. À ce stade, vous pourriez penser:

Qui se soucie de Node? Je veux juste que Tree soit covariant!

bien, en faisant son nœud covariant supertype Tree devient en pratique. scalac devrait réellement vérifier que tous les constructeurs de sous-types d'un covariant sont (ou pourraient être faits) covariants. Quoi qu'il en soit, le code montrant ce qui suit:

// you need a value for EmptyTree! thus default 
def evaluateTree[Z](tree: Tree[Z], default: Z): Z = 
    tree match { 
    case EmptyTree => default 
    case Leaf(value) => value 
    // note how you need to essentially cast here 
    case Node(op: (Seq[Z] => Z), args @ _*) => 
     op(args map { branches => evaluateTree(branches, default) }) 
    } 

trait A 
trait B extends A 

val notNice: Tree[A] = Node[B]({ bs: Seq[B] => bs.head }, EmptyTree) 
// ClassCastException! 
val uhoh = evaluateTree(notNice, new A {}) 

MISE À JOUR 2 Retour à votre question initiale :) Je laisserais votre type Tree invariant, et ont une classe EmptyTree[A]() de cas; il est dommage qu'il n'y ait pas de classes de valeur sans paramètre.

sealed trait Tree[A] 
case class EmptyTree[A]() extends Tree[A] 
case class Leaf[A](value: A) extends Tree[A] 
// I wouldn't use varargs here, make a method for that if you want 
case class Node[A](op: Seq[A] => A, branches: Tree[A]*) extends Tree[A] 
// for convenience, it could be inside `Tree` companion 
def emptyTree[A]: EmptyTree[A] = EmptyTree() 

def evaluateTree[Z](tree: Tree[Z], default: Z): Z = 
    tree match { 
    case EmptyTree() => 
     default 
    case Leaf(value) => 
     value 
    // no need to match generic types or anything here 
    case Node(op, args @ _*) => 
     op(args map { branches => evaluateTree(branches, default) }) 
    } 

trait A 
trait B extends A 

// doesn't work now 
// val notNice: Tree[A] = Node[B]({ bs: Seq[B] => bs.head }, emptyTree) 
val notNice: Tree[B] = Node[B]({ bs: Seq[B] => bs.head }, emptyTree) 

// doesn't compile, no class cast exception 
// val uhoh = evaluateTree(notNice, new A {})