Correct encoding of this existential type in Scala? -

i'm interested in encoding stream type stream fusion paper coutts et al. i'm exploring stream fusion in scala, attempting use macros in place of ghc's rewrite rules.

data stream = ∃s. stream (s → step s) s data step s = done               | yield s                | skip s 

i've tried few different approaches i'm not sure how encode type of stream in scala such both occurrences of s refer same type. i've written step type 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 type seems correct. i've used covariance function of type => work if receive yield , return done or step. in haskell.

my sticking point has been signature of stream. i've been attempting define case class. signature has worked far using exists type operator , tuple perserve equality of type s in both components 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 way encode such tuple not needed? closer haskell's (assuming existential operator) this:

case class stream(∃ s. f: s => step[a, s], s: s) 

where each member can separate field.

it occurs me encode in sml module/functor style 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 little more complicated. hoping there exists clearer way, ignorant of. attempted explore path, had few things satisfy compiler such add anyref bound, , unapply method doesn't work. error message scalac:

scala> res2 match { case stream(next, s) => (next, s) } <console>:12: error: error during expansion of match (this scalac bug). 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) }                     ^ 

first off, step looks perfect me. stream, think you're on right track abstract type. here's came (including implementations of remaining methods in section 2.1 of coutts paper):

abstract class stream[a] {   protected type s   def next: s => step[a, s]   def state: s    def map[b](f: => 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) => :: 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 :: => 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 note:

• my unapply has dependent method type: depends on s.s. think might have been stumbling block.
• the unfold method in unstream not tail-recursive.

the thing i'm still not clear on myself why it's important s existential / hidden / whatever. if it's not, write:

case class stream[a, s](next: s => step[a, s], state: s) 

... assume there's reason it. being said, i'm not sure approach hides s way want. story , i'm sticking it.