3

给定一个元素序列和一个谓词p，我想生成一个序列序列，使得在每个子序列中，所有元素都满足p或序列具有长度1。此外，调用.flatten结果应该会返回我的原始序列（因此不会重新排序元素）。

例如，给定：

val l = List(2, 4, -6, 3, 1, 8, 7, 10, 0)
val p = (i : Int) => i % 2 == 0

我想magic(l,p)制作：

List(List(2, 4, -6), List(3), List(1), List(8), List(7), List(10, 0))

我知道.span，但是该方法在第一次遇到不满足的值时停止p并仅返回一对。

下面是一个候选实现。它做了我想要的，但是，好吧，让我们想哭。我希望有人能想出一些更惯用的东西。

def magic[T](elems : Seq[T], p : T=>Boolean) : Seq[Seq[T]] = {
  val loop = elems.foldLeft[(Boolean,Seq[Seq[T]])]((false,Seq.empty)) { (pr,e) =>
    val (lastOK,s) = pr
    if(lastOK && p(e)) {
      (true, s.init :+ (s.last :+ e))
    } else {
      (p(e), s :+ Seq(e))
    }
  }
  loop._2
}

（请注意，我并不特别关心保留 . 的实际类型Seq。）

4

3 回答 3

3

对于这个任务，您可以使用takeWhile并drop结合一个匹配递归的小模式：

def magic[T](elems : Seq[T], p : T=>Boolean) : Seq[Seq[T]] = {
  def magic(elems: Seq[T], result: Seq[Seq[T]]): Seq[Seq[T]] = elems.takeWhile(p) match {
    // if elems is Nil, we have a result
    case Nil if elems.isEmpty => result

    // if it's not, but we don't get any values from takeWhile, we take a single elem
    case Nil => magic(elems.tail, result :+ Seq(elems.head))

    // takeWhile gave us something, so we add it to the result
    // and drop as many elements from elems, as takeWhile gave us
    case xs => magic(elems.drop(xs.size), result :+ xs)
  }

  magic(elems, Seq())
}
于 2013-01-10T16:36:29.983 回答
3

我不会使用foldLeft. span如果头部与谓词不匹配，这只是一个带有特殊规则的简单递归：

def magic[T](elems: Seq[T], p: T => Boolean): Seq[Seq[T]] = 
  elems match {
    case Seq() => Seq()
    case Seq(head, tail @ _*) if !p(head) => Seq(head) +: magic(tail, p)
    case xs => 
      val (prefix, rest) = xs span p
      prefix +: magic(rest, p)
  }

您也可以进行尾递归，但是如果您要预先添加，则需要记住反转输出（这是明智的）：

def magic[T](elems: Seq[T], p: T => Boolean): Seq[Seq[T]] = {
  def iter(elems: Seq[T], out: Seq[Seq[T]]) : Seq[Seq[T]] = 
    elems match {
      case Seq() => out.reverse
      case Seq(head, tail @ _*) if !p(head) => iter(tail, Seq(head) +: out)
      case xs => 
        val (prefix, rest) = xs span p
        iter(rest, prefix +: out)
    }
  iter(elems, Seq())
}
于 2013-01-10T19:32:06.380 回答
0

使用折叠的另一种解决方案：

def magicFilter[T](seq: Seq[T], p: T => Boolean): Seq[Seq[T]] = {
  val (filtered, current) = (seq foldLeft (Seq[Seq[T]](), Seq[T]())) {
    case ((filtered, current), element) if p(element)       => (filtered, current :+ element)
    case ((filtered, current), element) if !current.isEmpty => (filtered :+ current :+ Seq(element), Seq())
    case ((filtered, current), element)                     => (filtered :+ Seq(element), Seq())
  }
  if (!current.isEmpty) filtered :+ current else filtered
}
于 2013-01-10T17:14:28.657 回答