forall in Scala

Question

As shown below, in Haskell, it's possible to store in a list values with heterogeneous types with certain context bounds on them:

data ShowBox = forall s. Show s => ShowBox s

heteroList :: [ShowBox]
heteroList = [ShowBox (), ShowBox 5, ShowBox True]

How can I achieve the same in Scala, preferably without subtyping?

Answer 1

The ShowBox example you gave involves an existential type. I'm renaming the ShowBox data constructor to SB to distinguish it from the type:

data ShowBox = forall s. Show s => SB s

We say s is "existential", but the forall here is a universal quantifier that pertains to the SB data constructor. If we ask for the type of the SB constructor with explicit forall turned on, this becomes much clearer:

SB :: forall s. Show s => s -> ShowBox

That is, a ShowBox is actually constructed from three things:

1. A type s
2. A value of type s
3. An instance of Show s.

Because the type s becomes part of the constructed ShowBox, it is existentially quantified. If Haskell supported a syntax for existential quantification, we could write ShowBox as a type alias:

type ShowBox = exists s. Show s => s

Scala does support this kind of existential quantification and Miles's answer gives the details using a trait that consists of exactly those three things above. But since this is a question about "forall in Scala", let's do it exactly like Haskell does.

Data constructors in Scala cannot be explicitly quantified with forall. However, every method on a module can be. So you can effectively use type constructor polymorphism as universal quantification. Example:

trait Forall[F[_]] {
  def apply[A]: F[A]
}

A Scala type Forall[F], given some F, is then equivalent to a Haskell type forall a. F a.

We can use this technique to add constraints to the type argument.

trait SuchThat[F[_], G[_]] {
  def apply[A:G]: F[A]
}

A value of type F SuchThat G is like a value of the Haskell type forall a. G a => F a. The instance of G[A] is implicitly looked up by Scala if it exists.

Now, we can use this to encode your ShowBox ...

import scalaz._; import Scalaz._ // to get the Show typeclass and instances

type ShowUnbox[A] = ({type f[S] = S => A})#f SuchThat Show

sealed trait ShowBox {
  def apply[B](f: ShowUnbox[B]): B  
}

object ShowBox {
  def apply[S: Show](s: => S): ShowBox = new ShowBox {
    def apply[B](f: ShowUnbox[B]) = f[S].apply(s)
  }
  def unapply(b: ShowBox): Option[String] =
    b(new ShowUnbox[Option[String]] {
      def apply[S:Show] = s => some(s.shows)
  })
}

val heteroList: List[ShowBox] = List(ShowBox(()), ShowBox(5), ShowBox(true))

The ShowBox.apply method is the universally quantified data constructor. You can see that it takes a type S, an instance of Show[S], and a value of type S, just like the Haskell version.

Here's an example usage:

scala> heteroList map { case ShowBox(x) => x }
res6: List[String] = List((), 5, true)

A more direct encoding in Scala might be to use a case class:

sealed trait ShowBox
case class SB[S:Show](s: S) extends ShowBox {
  override def toString = Show[S].shows(s)
}

Then:

scala> val heteroList = List(ShowBox(()), ShowBox(5), ShowBox(true))
heteroList: List[ShowBox] = List((), 5, true)

In this case, a List[ShowBox] is basically equivalent to a List[String], but you can use this technique with traits other than Show to get something more interesting.

This is all using the Show typeclass from Scalaz.

Answer 2

Why not:

trait ShowBox {
    def show: String
}

object ShowBox {
    def apply[s](x: s)(implicit i: Show[s]): ShowBox = new ShowBox {
        override def show: String = i.show(x)
    }
}

As the authorities' answers suggested, I'm often surprised that Scala can translate "Haskell type monsters" into very simple one.

Answer 3

I don't think a 1-to-1 translation from Haskell to Scala is possible here. But why don't you want to use subtyping? If the types you want to use (such as Int) lack a show method, you can still add this via implicit conversions.

scala> trait Showable { def show:String }
defined trait Showable

scala> implicit def showableInt(i:Int) = new Showable{ def show = i.toString }
showableInt: (i: Int)java.lang.Object with Showable

scala> val l:List[Showable] = 1::Nil
l: List[Showable] = List($anon$1@179c0a7)

scala> l.map(_.show)
res0: List[String] = List(1)

Answer 4

( Edit: Adding methods to show, to answer comment. )

I think you can get the same using implicit methods with context bounds:

trait Show[T] {
  def apply(t:T): String
}
implicit object ShowInt extends Show[Int] {
  def apply(t:Int) = "Int("+t+")"
}
implicit object ShowBoolean extends Show[Boolean] {
  def apply(t:Boolean) = "Boolean("+t+")"
}

case class ShowBox[T: Show](t:T) {
  def show = implicitly[Show[T]].apply(t)
}

implicit def box[T: Show]( t: T ) =
  new ShowBox(t)

val lst: List[ShowBox[_]] = List( 2, true )

println( lst ) // => List(ShowBox(2), ShowBox(true))

val lst2 = lst.map( _.show )

println( lst2 ) // => List(Int(2), Boolean(true))

Answer 5

As @Michael Kohl commented, this use of forall in Haskell is an existential type and can be exactly replicted in Scala using either the forSome construct or a wildcard. That means that @paradigmatic's answer is largely correct.

Nevertheless there's something missing there relative to the Haskell original which is that instances of its ShowBox type also capture the corresponding Show type class instances in a way which makes them available for use on the list elements even when the exact underlying type has been existentially quantified out. Your comment on @paradigmatic's answer suggests that you want to be able to write something equivalent to the following Haskell,

data ShowBox = forall s. Show s => ShowBox s

heteroList :: [ShowBox]
heteroList = [ShowBox (), ShowBox 5, ShowBox True]

useShowBox :: ShowBox -> String
useShowBox (ShowBox s) = show s

-- Then in ghci ...

*Main> map useShowBox heteroList
["()","5","True"]

@Kim Stebel's answer shows the canonical way of doing that in an object-oriented language by exploiting subtyping. Other things being equal, that's the right way to go in Scala. I'm sure you know that, and have good reasons for wanting to avoid subtyping and replicate Haskell's type class based approach in Scala. Here goes ...

Note that in the Haskell above the Show type class instances for Unit, Int and Bool are available in the implementation of the useShowBox function. If we attempt to directly translate this into Scala we'll get something like,

trait Show[T] { def show(t : T) : String }

// Show instance for Unit
implicit object ShowUnit extends Show[Unit] {
  def show(u : Unit) : String = u.toString
}

// Show instance for Int
implicit object ShowInt extends Show[Int] {
  def show(i : Int) : String = i.toString
}

// Show instance for Boolean
implicit object ShowBoolean extends Show[Boolean] {
  def show(b : Boolean) : String = b.toString
}

case class ShowBox[T: Show](t:T)

def useShowBox[T](sb : ShowBox[T]) = sb match {
  case ShowBox(t) => implicitly[Show[T]].show(t)
  // error here      ^^^^^^^^^^^^^^^^^^^
} 

val heteroList: List[ShowBox[_]] = List(ShowBox(()), ShowBox(5), ShowBox(true))

heteroList map useShowBox

and this fails to compile in useShowBox as follows,

<console>:14: error: could not find implicit value for parameter e: Show[T]
         case ShowBox(t) => implicitly[Show[T]].show(t)
                                      ^

The problem here is that, unlike in the Haskell case, the Show type class instances aren't propagated from the ShowBox argument to the body of the useShowBox function, and hence aren't available for use. If we try to fix that by adding an additional context bound on the useShowBox function,

def useShowBox[T : Show](sb : ShowBox[T]) = sb match {
  case ShowBox(t) => implicitly[Show[T]].show(t) // Now compiles ...
} 

this fixes the problem within useShowBox, but now we can't use it in conjunction with map on our existentially quantified List,

scala> heteroList map useShowBox
<console>:21: error: could not find implicit value for evidence parameter
                     of type Show[T]
              heteroList map useShowBox
                             ^

This is because when useShowBox is supplied as an argument to the map function we have to choose a Show instance based on the type information we have at that point. Clearly there isn't just one Show instance which will do the job for all of the elements of this list and so this fails to compile (if we had defined a Show instance for Any then there would be, but that's not what we're after here ... we want to select a type class instance based on the most specific type of each list element).

To get this to work in the same way that it does in Haskell, we have to explicitly propagate the Show instances within the body of useShowBox. That might go like this,

case class ShowBox[T](t:T)(implicit val showInst : Show[T])

val heteroList: List[ShowBox[_]] = List(ShowBox(()), ShowBox(5), ShowBox(true))

def useShowBox(sb : ShowBox[_]) = sb match {
  case sb@ShowBox(t) => sb.showInst.show(t)
}

then in the REPL,

scala> heteroList map useShowBox
res7: List[String] = List((), 5, true)

Note that we've desugared the context bound on ShowBox so that we have an explicit name (showInst) for the Show instance for the contained value. Then in the body of useShowBox we can explicitly apply it. Also note that the pattern match is essential to ensure that we only open the existential type once in the body of the function.

As should be obvious, this is a lot more vebose than the equivalent Haskell, and I would strongly recommend using the subtype based solution in Scala unless you have extremely good reasons for doing otherwise.

Edit

As pointed out in the comments, the Scala definition of ShowBox above has a visible type parameter which isn't present in the Haskell original. I think it's actually quite instructive to see how we can rectify that using abstract types.

First we replace the type parameter with an abstract type member and replace the constructor parameters with abstract vals,

trait ShowBox {
  type T
  val t : T
  val showInst : Show[T]
}

We now need to add the factory method that case classes would otherwise give us for free,

object ShowBox {
  def apply[T0 : Show](t0 : T0) = new ShowBox {
    type T = T0
    val t = t0
    val showInst = implicitly[Show[T]]
  } 
}

We can now use plain ShowBox whereever we previously used ShowBox[_] ... the abstract type member is playing the role of the existential quantifier for us now,

val heteroList: List[ShowBox] = List(ShowBox(()), ShowBox(5), ShowBox(true))

def useShowBox(sb : ShowBox) = {
  import sb._
  showInst.show(t)
}

heteroList map useShowBox

(It's worth noting that prior to the introduction of explict forSome and wildcards in Scala this was exactly how you would represent existential types.)

We now have the existential in exactly the same place as it is in the original Haskell. I think this is as close to a faithful rendition as you can get in Scala.