5

2 つの scalaz ストリームを、いずれかのストリームから次の要素を選択する述語と結合したいと考えています。たとえば、このテストに合格したいと思います。

val a = Process(1, 2, 5, 8)
val b = Process(3, 4, 5, 7)

choose(a, b)(_ < _).toList shouldEqual List(1, 2, 3, 4, 5, 5, 7, 8)

ご覧のとおりzip、プロセスの 1 つが連続して選択される場合があるため、2 つの要素を順序付けするような巧妙なことはできません。

私はうまくいくと思った解決策を突き刺しました。まとめました！しかし、それが何もしないなら、くそー。JVMがハングするだけです:(

import scalaz.stream.Process._
import scalaz.stream._

object StreamStuff {
  def choose[F[_], I](a:Process[F, I], b:Process[F, I])(p: (I, I) => Boolean): Process[F, I] =
    (a.awaitOption zip b.awaitOption).flatMap {
      case (Some(ai), Some(bi)) =>
        if(p(ai, bi)) emit(ai) ++ choose(a, emit(bi) ++ b)(p)
        else emit(bi) ++ choose(emit(ai) ++ a, b)(p)
      case (None, Some(bi)) => emit(bi) ++ b
      case (Some(ai), None) => emit(ai) ++ a
      case _ => halt
    }
}

上記は私の2回目の試みであることに注意してください。最初の試みで を作成しようとしましたTeeが、敗者要素を消費しない方法がわかりませんでした。ここにあるような再帰的なものが必要だと感じました。

ストリーム バージョンを使用しています0.7.3a。

任意のヒント (これらのことを自分で理解する方法を単純に学びたいため、増分ヒントを含む) は大歓迎です!!

4

2 に答える 2

5

以下にいくつかのヒントと実装を示します。自分で解決策を見つけたい場合は、画面を隠してください。

免責事項: これは頭に浮かんだ最初のアプローチに過ぎず、scalaz-stream API に慣れていないので、この操作を実装するためのより良い方法があるかもしれません。これは恐ろしい方法で完全に間違っている可能性があります。 .

ヒント1

失われた要素を「消費しない」ようにする代わりに、次の再帰呼び出しでそれらを渡すことができます。

ヒント2

どちらの側が最後に負けたかを示すことで、複数の負け要素を蓄積する必要がなくなります。

ヒント3

Scalaz ストリームを扱うときは、最初に通常のコレクションを使用して実装をスケッチする方が簡単であることがよくあります。リストに必要なヘルパー メソッドは次のとおりです。

/**
 * @param p if true, the first of the pair wins
 */
def mergeListsWithHeld[A](p: (A, A) => Boolean)(held: Either[A, A])(
  ls: List[A],
  rs: List[A]
): List[A] = held match {
  // Right is the current winner.
  case Left(l) => rs match {
    // ...but it's empty.
    case Nil => l :: ls
    // ...and it's still winning.
    case r :: rt if p(r, l) => r :: mergeListsWithHeld(p)(held)(ls, rt)
    // ...upset!
    case r :: rt => l :: mergeListsWithHeld(p)(Right(r))(ls, rt)
  }
  // Left is the current winner.
  case Right(r) => ls match {
    case Nil => r :: rs
    case l :: lt if p(l, r) => l :: mergeListsWithHeld(p)(held)(lt, rs)
    case l :: lt => r :: mergeListsWithHeld(p)(Left(l))(lt, rs)
  }
}

これは、すでに負けている要素が手元にあることを前提としていますが、実際に使用したいメソッドを書くことができます:

def mergeListsWith[A](p: (A, A) => Boolean)(ls: List[A], rs: List[A]): List[A] =
  ls match {
    case Nil => rs
    case l :: lt => rs match {
      case Nil => ls
      case r :: rt if p(l, r) => l :: mergeListsWithHeld(p)(Right(r))(lt, rt)
      case r :: rt            => r :: mergeListsWithHeld(p)(Left(l))(lt, rt)
    }
  }

その後：

scala> org.scalacheck.Prop.forAll { (ls: List[Int], rs: List[Int]) =>
     |   mergeListsWith[Int](_ < _)(ls.sorted, rs.sorted) == (ls ++ rs).sorted
     | }.check
+ OK, passed 100 tests.

よし、よさそうだ。リストに対してこれを書くもっと良い方法がありますが、この実装は、 に対して行う必要があるものの形状と一致しますProcess。

実装

そして、これは多かれ少なかれ scalaz-stream と同等です:

import scalaz.{ -\/, \/, \/- }
import scalaz.stream.Process.{ awaitL, awaitR, emit }
import scalaz.stream.{ Process, Tee, tee }

def mergeWithHeld[A](p: (A, A) => Boolean)(held: A \/ A): Tee[A, A, A] =
  held.fold(_ => awaitR[A], _ => awaitL[A]).awaitOption.flatMap {
    case None =>
      emit(held.merge) ++ held.fold(_ => tee.passL, _ => tee.passR)
    case Some(next) if p(next, held.merge) =>
      emit(next) ++ mergeWithHeld(p)(held)
    case Some(next) =>
      emit(held.merge) ++ mergeWithHeld(p)(
        held.fold(_ => \/-(next), _ => -\/(next))
      )
  }

def mergeWith[A](p: (A, A) => Boolean): Tee[A, A, A] =
  awaitL[A].awaitOption.flatMap {
    case None => tee.passR
    case Some(l) => awaitR[A].awaitOption.flatMap {
      case None =>               emit(l) ++ tee.passL
      case Some(r) if p(l, r) => emit(l) ++ mergeWithHeld(p)(\/-(r))
      case Some(r)            => emit(r) ++ mergeWithHeld(p)(-\/(l))
    }
  }

そして、もう一度確認しましょう：

scala> org.scalacheck.Prop.forAll { (ls: List[Int], rs: List[Int]) =>
     |   Process.emitAll(ls.sorted).tee(Process.emitAll(rs.sorted))(
     |     mergeWith(_ < _)
     |   ).toList == (ls ++ rs).sorted
     | }.check
+ OK, passed 100 tests.

もう少しテストしないとこれを本番環境に入れることはできませんが、うまくいくようです。

于 2016-07-13T17:29:46.930 に答える