没有 var 或 breakable：如何在数组遍历中满足谓词时 "break"？

Question

如何将此编程逻辑写入功能方法签名？我正在尝试 loop/traverse 数组直到满足条件，然后打破该条件。我主要是尽力避免 var 和 breakable 来自 scala.util.control.Breaks。它使用闭包（在本例中为 dictionary）来检查是否满足 condition/predicate。这个想法是我循环遍历一个数组，直到满足谓词。我也避免将数组转换为列表。使用数组是否不允许我拼接数组，例如，进行模式匹配？

val dictionary = Array.fill(128)(false)

def isUnique(array: Array[Char]): Option[Char] = {

  // traverse each element of the array {
  //     if a character.toInt is in the dictionary, insert into dictionary 
  //        exit loop, with the character which broke the loop
  //     else
  //        set dictionary(character.toInt) to true and continue looping
  // }
}

这是一个示例用例：

val word = "abcdefggghijklmnopqrstuvqxyz".toArray
val charThatBrokeIt = isUnique(word)

编辑：请随意建议或推荐其他 return 类型，例如布尔值、元组、大小写 Class 或任何其他类型. Option[Char] 对我来说可能不是一个好的结果值。例如。我可能已经 returned false 以防循环提前（短路）或不中断。

Answer 1

早期突破总是暗示递归。

def isUnique(array: Array[Char]): Option[Char] = {
  def getDup(index: Int, acc: Set[Char]): Option[Char] =
    if (array.isDefinedAt(index))
      if (acc(array(index))) Some(array(index))
      else getDup(index+1, acc + array(index))
    else None
  getDup(0, Set.empty[Char])
}

用法：

val word = "abcdefggghijklmnopqrstuvqxyz".toArray
val charThatBrokeIt = isUnique(word)
//charThatBrokeIt: Option[Char] = Some(g)

Answer 2

首先，String 已经像一个集合，所以您应该只使用 String 而不是 Array[Char]。其次，您可以利用懒惰来允许短路，同时仍将算法拆分为多个部分，使用 .view.

def breaksUnique(word: String): Option[Char] = {
  val cumulativeSets = word.view.scanLeft(Set.empty[Char]){_ + _}
  val zipped = cumulativeSets zip word
  val nonDupsDropped = zipped dropWhile {case (set, char) => !(set contains char)}
  nonDupsDropped.map{_._2}.headOption
}

前两行写的好像是对整个word进行处理，但是因为是对view进行操作，所以只是按需计算。

cumulativeSets 是到目前为止已看到的每个字符的集合序列。如果你运行它在 "abb"，你会得到 Set(), Set(a), Set(a,b), Set(a,b)。使用 zip 与原始单词组合，得到 (Set(),a), (Set(a),b), (Set(a,b),b)。然后我们只需要删除字符未出现在集合中的所有对，然后 return 未删除的第一个元素。

没有 var 或 breakable：如何在数组遍历中满足谓词时 "break"？

No var or breakable: How to "break" when a predicate is met, in an array traversal?

arrays

scala

functional-programming

scala-collections

iterable