我有兴趣从 Coutts 等人的 Stream Fusion 论文中对这种 Stream 类型进行编码。我正在探索 Scala 中的流融合,尝试使用宏代替 GHC 的重写规则。
data Stream a = ∃s. Stream (s → Step a s) s
data Step a s = Done
| Yield a s
| Skip s
我尝试了几种不同的方法,但我不确定如何在 Scala 中编码 Stream 的类型,以便 S 的两个出现都引用相同的类型。我已经轻松地编写了 Step 类型。
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]
到目前为止,这种类型似乎是正确的。我使用了协方差,因此即使我们收到 Yield 并返回 Done 或 Step,A => A 类型的函数也可以工作。就像在 Haskell 中一样。
我的症结是 Stream 的签名。我一直试图将它定义为一个案例类。到目前为止唯一有效的签名是使用 Exists 类型运算符和 Tuple 来保持两个组件中类型 S 的相等性,如下所示。
type Exists[P[_]] = P[T] forSome { type T }
case class Stream[A](t: Exists[({ type L[S] = (S => Step[A, S], S)})#L])
有没有办法对其进行编码以使不需要元组?更接近Haskell(假设存在运算符)的东西:
case class Stream(∃ S. f: S => Step[A, S], s: S)
其中每个成员都可以是单独的字段。
我还想到,我可以像这样以 SML 模块/函子风格对其进行编码:
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)
}
但这有点复杂。我希望有一个更清晰的方法,我不知道。此外,当我尝试探索这条路径时,我必须做一些事情来满足编译器的要求,例如添加 AnyRef 绑定,而 unapply 方法不起作用。使用来自 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) }
^