在Scala中正确编码这种存在类型？

发布时间：2020-12-16 10:02:53 所属栏目：安全来源：网络整理

导读：我有兴趣从Coutts等人的Stream Fusion论文中编码这种Stream类型.我在 Scala中探索流融合,尝试使用宏来代替GHC的重写规则. data Stream a = ?s. Stream (s → Step a s) sdata Step a s = Done | Yield a s | Skip s 我尝试了几种不同的方法,但我不确定如何在

我有兴趣从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]

到目前为止这种类型似乎是正确我使用了协方差,因此类型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)

其中每个成员可以是单独的字段.

我也可以在SML模块/ Functor样式中对此进行编码,如下所示：

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) }
                    ^

解决方法

首先,Step看起来很完美.至于Stream,我认为你在抽象类型上走在正确的轨道上.以下是我提出的内容(包括Coutts论文2.1节中其余方法的实现)：

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))
}

有几点需要注意：

>我的unapply有一个依赖方法类型：它取决于s.S.我想这可能是你的绊脚石.
> unstream中的展开方法不是尾递归的.

我对自己还不是很清楚的事情是,为什么S对于存在/隐藏/什么是重要的.如果不是,你可以写：

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

……但我认为这是有道理的.话虽这么说,我也不确定这种方法是否真的以你想要的方式隐藏了S.但这是我的故事,我坚持下去.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!