self annotation using abstract type

Question

I would like to define an abstract recursive data structure with an abstract type. Something like this :

case class ParentA( name : String, children : List[ParentA] ) extends Parent {
    type PARENT = ParentA
}

case class ParentB( name : String, children : List[ParentB] ) extends Parent {
    type PARENT = ParentB
}

sealed abstract class Parent {
    // we'd like to Define Parent as a PARENT
    // something like: 
    // this : PARENT =>

    type PARENT <: Parent

    val name : String

    val children : List[PARENT]

    def findParent(name:String) : Option[PARENT] = {
        if( name == this.name ) {
            Some(this) // ouch
        } else {
            // re-ouch
            children.flatMap( f => f.findParent(name) )
        }
    }
}

val a2a : ParentA = ParentA("a",List(ParentA("a1",Nil),ParentA("a2",List(ParentA("a2a",Nil))))).findParent("a2a").get

Of course this won't compile, because the compiler cannot guess that Parent.this is a PARENT .

error: type mismatch;
found   : Parent.this.type (with underlying type this.Parent)
required: Parent.this.PARENT
        Some(this)

And also

error: type mismatch;
found   : List[Parent.this.PARENT#PARENT]
required: Option[Parent.this.PARENT]
        children.flatMap( f => f.findParent(name) )

I can get around it by casting here and there but it would be better to be able to tell the compiler that Parent is a PARENT. Or maybe i'm missing something :)

Edit - Generics

I forgot to mention that Generics are not an option. This example is actually a simplified version of a more subtle problem. Using generics will lead to a quadratic growth of the program. Here is a link explaining why generics are not always a viable alternative : Scala: Abstract types vs generics.

Basically i'm better off using abstract types - or even neither abstract types nor generics - and casting.

kiritsuku · Answer 1 · 2012-07-17T22:27:34.460

4

The same idea as mentioned by @Debilski, but no extra type parameter:

case class ParentA(name: String, children: List[ParentA]) extends Parent[ParentA]

case class ParentB(name: String, children: List[ParentB]) extends Parent[ParentB]

sealed abstract class Parent[P <: Parent[P]] { this: P =>

  def name: String

  def children: List[P]

  def findParent(name: String): Option[P] =
    if (name == this.name) Some(this)
    else children.flatMap(_.findParent(name)).headOption
}

By the way, use defs instead of vals for abstract members. They allow more flexibility while implementing them in subclasses.

edited Jul 17 '12 at 22:27

answered Jul 17 '12 at 22:20

kiritsuku

52,967
18
114
136

I’d forgotten about the `P <: Parent[P]` trick. No wonder it wasn’t 100% working as I thought it should. – Debilski Jul 17 '12 at 22:24
Ah sorry guys I forgot to mention that using generics is not an option. I'll edit my question to explain why. – Bruno Bieth Jul 18 '12 at 17:48

score 1 · Answer 2 · edited May 23 '17 at 12:06

Only for reference. sschaef has a better way to do it.

This compiles using the Scala CRTP and self-types.

case class ParentA(name : String, children : List[ParentA]) extends Parent[ParentA]

case class ParentB(name : String, children : List[ParentB]) extends Parent[ParentB]

sealed abstract class Parent[T] { this : T =>
    type PARENT = Parent[T] with T

    val name : String

    val children : List[PARENT]

    def findParent(name:String) : Option[PARENT] = {
        if( name == this.name ) {
            Some(this)
        } else {
            children.flatMap( f => f.findParent(name) ).headOption
        }
    }
}
val a2a : ParentA = ParentA("a",List(ParentA("a1",Nil),ParentA("a2",List(ParentA("a2a",Nil))))).findParent("a2a").get

self annotation using abstract type

Edit - Generics

2 Answers2