4

次のコードは論文 (RO Bjarnason, Stackless Scala With Free Monads) から改作されています。

この論文のタイトルは、提案されたデータ構造の一般的な目的を示しています。それは、一定のスタック空間で再帰処理を可能にし、ユーザーが明確な方法で再帰を表現できるようにすることです。

具体的には、私の目標は、昇順の定数スタック空間での単純なパターン マッチングに基づいて、ペアの不変ツリー (バイナリ ツリー) またはリスト (n-ary-tree) の構造的書き換えを可能にするモナド構造を持つことです。

sealed trait Free[S[+_], +A]{
  private case class FlatMap[S[+_], A, +B](
    a: Free[S, A],
    f: A => Free[S, B]
  ) extends Free[S, B]

  def map[B](f: A => B): Free[S, B] = this.flatMap((a:A) => Done[S, B](f(a))) 

  def flatMap[B](f: A => Free[S, B]): Free[S, B] = this match { 
    case FlatMap(a, g) => FlatMap(a, (x: Any) => g(x).flatMap(f))
    case x => FlatMap(x, f)
  } 

  @tailrec
  final def resume(implicit S: Functor[S]): Either[S[Free[S, A]], A] = {
    this match {
      case Done(a) => Right(a)
      case More(k) => Left(k)
      case FlatMap(a, f) => a match {
        case Done(a) => f(a).resume
        case More(k) => Left(S.map(k)((x)=>x.flatMap(f)))
        case FlatMap(b, g) => b.flatMap((x: Any) => g(x).flatMap(f)).resume
      }
    }
  }
}

case class Done[S[+_], +A](a: A) extends Free[S, A]

case class More[S[+_], +A](k: S[Free[S, A]]) extends Free[S,A]

trait Functor[F[+_]] {
  def map[A, B](m: F[A])(f: A => B): F[B]
}

type RoseTree[+A] = Free[List, A] 

implicit object listFunctor extends Functor[List] {
  def map[A, B](a: List[A])(f: A => B) = a.map(f)
}
var tree :  Free[List, Int]=  More(List(More(List(More(List(Done(1), Done(2))), More(List(Done(3), Done(4))))), More(List(More(List(Done(5), Done(6))), More(List(Done(7), Done(8)))))))

Free を使用した書き換えはどのように行われますか?

パターンマッチャーのフックはどこにありますか? - パターン マッチャーは、昇順で各サブツリー全体に公開する必要があります。

これは for ブロック内で実行できますか?

【質問を編集しました。】

4

1 に答える 1

7

更新: 以下の回答は、以前のバージョンの質問に対応していますが、ほとんどの場合まだ関連しています。

まず第一に、あなたのコードはそのままでは機能しません。すべてを不変にするか、元の論文の分散注釈を使用することができます。簡単にするために、不変のルートを使用します (完全な例については、こちらを参照してください) が、論文のバージョンが 2.10.2 で動作することも確認しました。

最初の質問に最初に答えるには: 二分木の型は に同形BinTree[Int]です。ただし、これを示す前に、ペア型のファンクターが必要です。

implicit object pairFunctor extends Functor[Pair] {
  def map[A, B](a: Pair[A])(f: A => B) = (f(a._1), f(a._2))
}

これで、 からへresumeの変換に必要になります。BinTreeT

def from(tree: T): BinTree[Int] = tree match {
  case L(i) => Done(i)
  case F((l, r)) => More[Pair, Int]((from(l), from(r)))
}

def to(tree: BinTree[Int]): T = tree.resume match {
  case Left((l, r)) => F((to(l), to(r)))
  case Right(i) => L(i)
}

これで、サンプル ツリーを定義できます。

var z = 0
def f(i: Int): T = if (i > 0) F((f(i - 1), f(i - 1))) else { z = z + 1; L(z) }
val tree = f(3)

BinTreeすべてのリーフ値をその前任者と後任者を含むツリーに置き換えることにより、同型と for のモナドを示しましょう。

val newTree = to(
  from(tree).flatMap(i => More[Pair, Int]((Done(i - 1), Done(i + 1))))
)

いくつかの再フォーマットの後、結果は次のようになります。

F((
  F((
    F((
      F((L(0), L(2))),
      F((L(1), L(3)))
    )),
    F((
      F((L(2), L(4))),
      F((L(3), L(5)))
    )),
    ...

などなど、予想通り。

2 番目の質問: バラの木に対して同じようなことをしたい場合は、ペアをリスト (またはストリーム) に置き換えるだけです。上でペアに対して行ったように、リストに対してファンクター インスタンスを提供する必要があります。これにより、Done(x)葉とMore(xs)枝を表すツリーが得られます。

-comprehension 構文が機能するには、型が必要mapです。for幸いなことに、 and を使って書くことができmapますflatMap—Doneの定義に以下を追加するだけですFree:

def map[B](f: A => B): Free[S, B] = this.flatMap(f andThen Done.apply)

現在、以下はnewTree上記とまったく同じです。

val newTree = to(
  for {
    i <- from(tree)
    m <- More[Pair, Int]((Done(i - 1), Done(i + 1)))
  } yield m
)

Free[List, _]バラの木でも同じことができます。

于 2013-08-25T14:01:42.267 に答える