4

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

私はいくつかの異なるアプローチを試しましたが、S の両方の出現が同じ型を参照するように、Scala で Stream の型をエンコードする方法がわかりません。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 Module/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) => (next, s) }
                    ^
4

1 に答える 1

4

まず、Step私には完璧に見えます。に関してはStream、抽象型で正しい軌道に乗っていると思います。これが私が思いついたものです（クーツ紙のセクション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))
}

注意すべき点がいくつかあります。

  • Myunapplyには依存メソッド タイプがありs.Sます。それがあなたのつまずきだったのではないかと思います。
  • のunfoldメソッドunstreamは末尾再帰ではありません。

私自身まだよくわかっていないのは、S実存的/隠蔽/何でもすることがなぜ重要なのかということです。そうでない場合は、次のように書くことができます。

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

・・・でも、それには理由があると思います。そうは言っても、このアプローチが実際にSあなたが望む方法を隠しているかどうかもわかりません。しかし、これは私の話であり、私はそれに固執しています。

于 2013-04-20T04:18:29.137 に答える