CODEWITHSUNDEEP
scaladata-structurestreescalaz
NightWolf
NightWolf

Reputation: 7794

Covariant Trees in Scala

Looking at scalaz.Tree[A], it is invariant in A. I'm looking for a multi-way tree which I can dump values of a hierarchy in

E.g. if I have an ADT of

trait MyThing
case object Thing1 extends MyThing
case object Thing2 extends MyThing

And I want a Tree of MyThings, I cant use this without doing a cast to MyThing in scalaz;

import scalaz.{Scalaz, Tree}
import Scalaz._
val tree = Thing1.asInstanceOf[MyThing].
               node(Thing2.asInstanceOf[MyThing].leaf)

Which is a bit of a pain.

Upvotes: 4

Views: 270

Answers (1)

Travis Brown
Travis Brown

Reputation: 139038

First of all, I want to second Huw's recommendation that you use a type ascription instead of downcasting with asInstanceOf. As Huw says, using a type ascription will fail at compile time instead of runtime if something changes in your type hierarchy that makes the cast invalid. It's also just a good practice to avoid asInstanceOf for any upcasts. You can use asInstanceOf for either upcasting or downcasting, but only using it for downcasting makes it easy to identify unsafe casting in your code.

To answer your two questions—no, there's not a covariant tree type in Scalaz, for reasons discussed in detail in the pull request linked by Huw above. At first this may seem like a huge inconvenience, but the decision to avoid non-invariant structures in Scalaz is related to a similar design decision—avoiding the use of subtyping in ADTs—that makes invariant trees, etc. less painful.

In other languages with good support for ADTs (like Haskell and OCaml, for example), the leaves of an ADT aren't subtypes of the ADT type, and Scala's somewhat unusual subtyping-based implementation can make type inference messy. The following is a common example of this problem:

scala> List(1, 2, 3).foldLeft(None)((_, i) => Some(i))
<console>:14: error: type mismatch;
 found   : Some[Int]
 required: None.type
              List(1, 2, 3).foldLeft(None)((_, i) => Some(i))
                                                     ^

Because the type of the accumulator is inferred from the first argument to foldLeft, it ends up as None.type, which is pretty much useless. You have to provide a type ascription (or explicit type parameters for foldLeft), which can be pretty inconvenient.

Scalaz attempts to address this issue by promoting the use of ADT constructors that don't return the most specific subtype for the ADT leaf. For example, it includes none[A] and some[A](a: A) constructors for Option that return an Option[A].

(For more discussion of these issues, see my answer here and this related question).

In your case, implementing this approach could be as simple as writing the following:

val thing1: MyThing = Thing1
val thing2: MyThing = Thing2

Which allows you to write thing1.node(thing2.leaf). If you want to go further down this path, I'd highly recommend looking at Argonaut's Json ADT as a good example of ADT design that downplays the role of subtyping.

Upvotes: 2

Related Questions