Correct encoding of this existential type in Scala?

Question

I'm interested in encoding this Stream type from the Stream Fusion paper from Coutts et al. I'm exploring stream fusion in Scala, attempting to use macros in place of GHC's rewrite rules.

data Stream a = ∃s. Stream (s → Step a s) s
data Step a s = Done
              | Yield a s 
              | Skip s

I've tried a few different approaches but I'm not sure how to encode the type of Stream in Scala such that both occurrences of S refer to the same type. I've written the Step type easily as.

sealed abstract class Step[+A, +S]
case object Done extends Step[Nothing, Nothing]
case class Yield[A, S](a: A, s: S) extends Step[A, S]
case class Skip[S](s: S) extends Step[Nothing, S]

So far this type seems correct. I've used covariance so that a function of type A => A will work even if we receive a Yield and return a Done or Step. Just like in Haskell.

My sticking point has been the signature of Stream. I've been attempting to define it as just a case class. The only signature that has worked so far is using an Exists type operator and Tuple to perserve the equality of type S in both components as below.

type Exists[P[_]] = P[T] forSome { type T }

case class Stream[A](t: Exists[({ type L[S] = (S => Step[A, S], S)})#L])

Is there a way to encode it such that the tuple is not needed? Something closer to Haskell's (assuming existential operator) this:

case class Stream(∃ S. f: S => Step[A, S], s: S)

where each member can be separate field.

It also occurs to me that I could encode this in an SML Module/Functor style like so:

trait Stream[A] {
  type S <: AnyRef
  val f: S => Step[A, S]
  val s: S
}

object Stream {
  def apply[A, S1 <: AnyRef](next: S1 => Step[A, S1], st: S1): Stream[A] = new Stream[A] {
    type S = S1
    val f = next
    val s = st
  }

  def unapply[A](s: Stream[A]): Option[(s.f.type, s.s.type)] = Some(s.f, s.s)
}

but this is a little more complicated. I was hoping there exists a clearer way, that I am ignorant of. Also as I attempted to explore this path, I had to do a few things to satisfy the compiler such as add the AnyRef bound, and the unapply method doesn't work. With this error message from scalac:

scala> res2 match { case Stream(next, s) => (next, s) }
<console>:12: error: error during expansion of this match (this is a scalac bug).
The underlying error was: type mismatch;
 found   : Option[(<unapply-selector>.f.type, <unapply-selector>.s.type)]
 required: Option[(s.f.type, s.s.type)]
               res2 match { case Stream(next, s) => (next, s) }
                    ^

Does case class Stream[A](t: (S => Step[A, S], S) forSome { type S }) not work? — Travis Brown
@TravisBrown yes, but jroesch is trying to eliminate the tuple. — mergeconflict
The "unapply-selector" bug is issues.scala-lang.org/browse/SI-6130 . — psp
Is the "unapply-selector" bug something someone is actively working on(the only thing I saw was Adriaan's branch from many months ago)? — jroesch
Why did you put an existential symbol into the Haskell where a universal one belongs? — copumpkin

mergeconflict mergeconflict · Accepted Answer · 2013-04-20T04:18:29

First off, Step looks perfect to me. As for Stream, I think you're on the right track with the abstract type. Here's what I came up with (including implementations of the remaining methods in section 2.1 of the Coutts paper):

abstract class Stream[A] {
  protected type S
  def next: S => Step[A, S]
  def state: S

  def map[B](f: A => B): Stream[B] = {
    val next: S => Step[B, S] = this.next(_) match {
      case Done        => Done
      case Skip(s)     => Skip(s)
      case Yield(a, s) => Yield(f(a), s)
    }
    Stream(next, state)
  }

  def unstream: List[A] = {
    def unfold(s: S): List[A] = next(s) match {
      case Done        => List.empty
      case Skip(s)     => unfold(s)
      case Yield(a, s) => a :: unfold(s)
    }
    unfold(state)
  }
}

object Stream {
  def apply[A, S0](n: S0 => Step[A, S0], s: S0) = new Stream[A] {
    type S = S0
    val next = n
    val state = s
  }

  def apply[A](as: List[A]): Stream[A] = {
    val next: List[A] => Step[A, List[A]] = {
      case a :: as => Yield(a, as)
      case Nil     => Done
    }
    Stream(next, as)
  }

  def unapply[A](s: Stream[A]): Option[(s.S => Step[A, s.S], s.S)] =
    Some((s.next, s.state))
}

A couple things to note:

My unapply has a dependent method type: it depends on the s.S. I think that might have been your stumbling block.
The unfold method in unstream is not tail-recursive.

The thing I'm still not really clear on myself is why it's important for S to be existential / hidden / whatever. If it's not, you could just write:

case class Stream[A, S](next: S => Step[A, S], state: S)

... but I assume there's a reason for it. That being said, I'm also not sure this approach actually hides S the way you want. But this is my story and I'm sticking to it.

Correct encoding of this existential type in Scala?

1 Answers