Scala:突破foldLeft

Question

假设我们有Seq val ourSeq = Seq(10,5,3,5,4)。

我想返回一个新的列表，它从左边读取，当它看到一个重复的数字时就停止(例如，Seq(10,5,3)，因为5是重复的)。

我想用左边的折叠

ourSeq.foldLeft(Seq())(op = (temp, curr) => {

  if (!temp.contains(curr)) {
    temp :+ curr 
  } else break

})

但据我所知，没有办法突破foldLeft

Answer 1

你是正确的，它是不可能突破foldLeft。理论上，用foldLeft获得正确的结果是可能的，但是您仍然要迭代整个数据结构。最好使用一种已经知道如何提前终止的算法，而且由于您想要使用前缀，takeWhile就足够了。

import scala.collection.mutable.Set

val ourSeq = Seq(10, 5, 3, 5, 4)

val seen: Set[Int] = Set()
val untilDups = ourSeq.takeWhile((x) => {
  if (seen contains x) {
    false
  } else {
    seen += x
    true
  }
})
print(untilDups)

如果您想在这方面完全不可变，可以将整个过程封装在某种懒散的折叠中，使用不变的Set来保存其数据。我在哈斯克尔肯定也是这么做的。但这是Scala；我们有可变性，我们也可以在适合我们的地方使用它。

Answer 2

虽然它可以在没有任何突破的情况下用foldLeft()实现，但我认为fold是一个错误的工作工具。

我非常喜欢unfold()，它是在Scala2.13.0中引入的。

val ourSeq = Seq(10,5,3,5,4)
Seq.unfold((Set.empty[Int],ourSeq)){ case (seen,ns) =>
  Option.when(ns.nonEmpty && !seen(ns.head)) {
    (ns.head, (seen+ns.head, ns.tail))
  }
}
//res0: Seq[Int] = Seq(10, 5, 3)

Answer 3

这可以使用递归函数来完成：

def uniquePrefix[T](ourSeq: Seq[T]): List[T] = {
  @annotation.tailrec
  def loop(rem: List[T], res: List[T]): List[T] = 
    rem match {
      case hd::tail if !res.contains(hd) =>
        loop(tail, res :+ hd)
      case _ =>
        res
    }

  loop(ourSeq.toList, Nil)
}

这看起来更复杂，但是一旦您熟悉了通用模式，递归函数就会比fold操作更简单、更强大。

如果您正在处理大型集合，则此版本更有效，因为它是O(n)。

def distinctPrefix[T](ourSeq: Seq[T]): List[T] = {
  @annotation.tailrec
  def loop(rem: List[T], found: Set[T], res: List[T]): List[T] = 
    rem match {
      case hd::tail if !found.contains(hd) =>
        loop(tail, found + hd, hd +: res)
      case _ =>
        res.reverse
    }

  loop(ourSeq.toList, Set.empty, Nil)
}

此版本适用于任何Seq，还有使用Iterator等的其他选项，如注释中所述。为了创建一个优化的算法，您需要更具体地说明集合的类型。

def uniquePrefix[T](ourSeq: Seq[T]): List[T] = {
  @annotation.tailrec
  def loop(rem: Seq[T], res: List[T]): List[T] = 
    rem.take(1) match {
      case Seq(hd) if !res.contains(hd) =>
        loop(rem.drop(1), res :+ hd)
      case _ =>
        res
    }

  loop(ourSeq, Nil)
}