2

特定のペアワイズ条件で分割するコレクション メソッドを探しています。

val x = List("a" -> 1, "a" -> 2, "b" -> 3, "c" -> 4, "c" -> 5)

implicit class RichIterableLike[A, CC[~] <: Iterable[~]](it: CC[A]) {
  def groupWith(fun: (A, A) => Boolean): Iterator[CC[A]] = new Iterator[CC[A]] {
    def hasNext: Boolean = ???

    def next(): CC[A] = ???
  }
}

assert(x.groupWith(_._1 != _._1).toList == 
  List(List("a" -> 1, "a" -> 2), List("b" -> 3), List("c" -> 4, "c" -> 5))
)

したがって、これは一種の再帰spanです。

を実装することはできますが???、

  • 私が監視しているコレクションに何かが既に存在する場合
  • そのメソッドを何と呼ぶべきか; groupWith正しく聞こえません。簡潔にする必要がありますが、関数の引数がペアで動作することを何らかの形で反映しています。groupWhereもう少し近いと思いますが、まだはっきりしていません。
  • 実際には を使用する場合groupWith、述語ロジックを反転する必要があると思いますので、使用しますx.groupWith(_._1 == _._1)
  • タイプについての考え。私には合理Iterator[CC[A]]的に見えます。おそらく、 を取り、 ?CanBuildFromを返す必要があります。Iterator[To]
4

3 に答える 3

1

tailrec/pattern マッチングを使用するバージョンを作成することもできます。

  def groupWith[A](s: Seq[A])(p: (A, A) => Boolean): Seq[Seq[A]] = {
    @tailrec
    def rec(xs: Seq[A], acc: Seq[Seq[A]] = Vector.empty): Seq[Seq[A]] = {
      (xs.headOption, acc.lastOption) match {
        case (None, _) => acc
        case (Some(a), None) => rec(xs.tail, acc :+ Vector(a))
        case (Some(a), Some(group)) if p(a, group.last) => rec(xs.tail, acc.init :+ (acc.last :+ a))
        case (Some(a), Some(_)) => rec(xs.tail, acc :+ Vector(a))
      }
    }

    rec(s)
  }
于 2013-10-14T17:24:40.980 に答える
1

フォールドでも達成できますよね？最適化されていないバージョンは次のとおりです。

  def groupWith[A](ls: List[A])(p: (A, A) => Boolean): List[List[A]] = 
    ls.foldLeft(List[List[A]]()) { (acc, x) => 
      if(acc.isEmpty)
        List(List(x))
      else
        if(p(acc.last.head, x))
          acc.init ++ List(acc.last ++ List(x))
        else 
          acc ++ List(List(x))
    }

  val x = List("a" -> 1, "a" -> 2, "b" -> 3, "c" -> 4, "c" -> 5, "a" -> 4)    
  println(groupWith(x)(_._1 == _._1))
  //List(List((a,1), (a,2)), List((b,3)), List((c,4), (c,5)), List((a,4)))
于 2013-10-14T00:34:48.200 に答える
1

だからここに私の提案があります。私の意見ではあまり説明的ではないgroupWithので、私はに固執しました。が非常に異なるセマンティクスを持っているspansことは事実ですが、似ているものがあります。groupBygrouped(size: Int)

既存のイテレータを組み合わせることだけに基づいてイテレータを作成しようとしましたが、これは面倒なので、より低レベルのバージョンを次に示します。

import scala.collection.generic.CanBuildFrom
import scala.annotation.tailrec
import language.higherKinds

object Extensions {
  private final class GroupWithIterator[A, CC[~] <: Iterable[~], To](
      it: CC[A], p: (A, A) => Boolean)(implicit cbf: CanBuildFrom[CC[A], A, To])
    extends Iterator[To] {

    private val peer      = it.iterator
    private var consumed  = true
    private var elem      = null.asInstanceOf[A]

    def hasNext: Boolean = !consumed || peer.hasNext

    private def pop(): A = {
      if (!consumed) return elem
      if (!peer.hasNext)
        throw new NoSuchElementException("next on empty iterator")

      val res   = peer.next()
      elem      = res
      consumed  = false
      res
    }

 

    def next(): To = {
      val b = cbf()

      @tailrec def loop(pred: A): Unit = {
        b       += pred
        consumed = true
        if (!peer.isEmpty) {
          val succ = pop()
          if (p(pred, succ)) loop(succ)
        }
      }

      loop(pop())
      b.result()
    }
  }

 

  implicit final class RichIterableLike[A, CC[~] <: Iterable[~]](val it: CC[A])
    extends AnyVal {
    /** Clumps the collection into groups based on a predicate which determines
      * if successive elements belong to the same group.
      *
      * For example:
      * {{
      *   val x = List("a", "a", "b", "a", "b", "b")
      *   x.groupWith(_ == _).to[Vector]
      * }}
      *
      * produces `Vector(List("a", "a"), List("b"), List("a"), List("b", "b"))`.
      *
      * @param p    a function which is evaluated with successive pairs of
      *             the input collection. As long as the predicate holds
      *             (the function returns `true`), elements are lumped together.
      *             When the predicate becomes `false`, a new group is started.
      *
      * @param cbf  a builder factory for the group type
      * @tparam To  the group type
      * @return     an iterator over the groups.
      */
    def groupWith[To](p: (A, A) => Boolean)
                     (implicit cbf: CanBuildFrom[CC[A], A, To]): Iterator[To] =
      new GroupWithIterator(it, p)
  }
}

つまり、述語は質問とは逆になります。

import Extensions._
val x = List("a" -> 1, "a" -> 2, "b" -> 3, "c" -> 4, "c" -> 5)
x.groupWith(_._1 == _._1).to[Vector]
// -> Vector(List((a,1), (a,2)), List((b,3)), List((c,4), (c,5)))
于 2013-10-13T19:03:06.733 に答える