函数式编程风格的过滤器列表

Question

我们有一个字符串列表，其中包含 BEGIN 和 END 标记。我们可以用函数式编程风格过滤掉 BEGIN-END 之间的元素吗？我只在 scala 中使用了这种常规（标志）方法。

val list1 =
  """992
  1010
  1005
  1112
  BEGIN
  1086
  1244
  1107
  1121
  END
  1223
  1312
  1319
  1306
  1469""".lines.toList

var flag = false
val filteredList = list1.filter{
  def f(x: String): Boolean = {
    if (x.contains("BEGIN")) {
      flag = true;
      return false
    } else if (x.contains("END")) {
      flag = false
    }
    flag
  }
  f
}

是否可以避免定义标志变量？他们如何用纯函数式语言解决这个问题？

Answer 1

您可以使用 drop/tail、dropWhile、takeWhile 函数：

val filteredList = list1.map(_.trim).dropWhile("BEGIN" !=).tail.takeWhile("END" !=)

编辑

如评论中所述 tail<如果列表为空， /code> 将抛出异常，因此如果您希望安全起见，请使用 drop(1) 而不是 tail：

val filteredList = list1.map(_.trim).dropWhile("BEGIN" !=).drop(1).takeWhile("END" !=)

这是我的版本处理多个 BEGIN 和 END 部分的算法（我的一些疯狂的东西 - 一个小状态机:)

var filteredList1 = list1.map(_.trim).foldLeft(List(None): List[Option[List[String]]]) {
  case (None :: rest, "BEGIN") => Some(Nil) :: rest
  case (Some(list) :: rest, "END") => None :: Some(list) :: rest
  case (Some(current) :: rest, num) => Some(num :: current) :: rest
  case (result, _) => result
}.flatten.reverse map (_.reverse)

它返回 List[List[String]]

Answer 2

首先，列表中的每个字符串都包含从行开头开始的空格。

这是代码中最大的问题，有两种方法可以解决它。

要么修剪线条……

val list1 =
  """992
  1010
  ...
  1306
  1469""".lines.map(_.trim).toList

要么您可以在每行前面加上 | 并使用 stripMargin。

然后，只需应用 takeWhile/dropWhile

list1.takeWhile("BEGIN" !=) ++ list1.dropWhile("END"!=).tail

或更有效地实现即可：

val (begin,middle) = list1.span("BEGIN" !=)
val end = middle.dropWhile("END" !=).tail
begin ++ end

编辑

我将解决方案从后到前，这会下降 (filter out) 介于 BEGIN 和 END 之间的值。要保留它们：

list1.dropWhile("BEGIN" !=).tail.takeWhile("END"!=)

编辑 2

迎接这里的挑战...我将允许使用多个 BEGIN/END 块，但也要考虑输入可能严重畸形。如果有一个 BEGIN 而没有相应的 END 怎么办？也许连续有两个 BEGIN，或者列表在 END 之前就用完了。

定义一些规则：

• 没有相应 BEGIN 的 END 被忽略
• BEGIN/END 块不嵌套
• 已经在块中时遇到的 BEGIN 启动一个新块
• 如果列表在块中用完，则假定隐式 END

无需进一步废话不多说，首先创建一个迭代器来标识输入中的每个 "BEGIN"：

val blocksStarts =
  Iterator.iterate(list1)(_.dropWhile("BEGIN" !=).drop(1)).drop(1).takeWhile(Nil !=)

//This iterator tries to continue forever,
//returning Nils once the sequences are exhausted
//For this reason, we must use drop(1) instead of tail

给出一个列表迭代器，每个列表都从 "BEGIN" 开始

然后从每个列表中获取元素这些列表，直到到达相应的 "END"，或另一个 "BEGIN"，或者列表耗尽：

val blocks = blockStarts map {
  _.takeWhile(x => x != "BEGIN" && x != "END")
} toList

最终的toList 是因为它是那时仍然是一个迭代器。您现在拥有一个列表列表，每个列表对应于“块”中的一批元素，如前面的规则所定义。

Answer 3

我稍微扩展了其他人的答案，以展示列表中有两个 BEGIN...END 块的情况。

val list1 =
  """992
  1010
  1005
  1112
  BEGIN
  1086
  1244
  1107
  1121
  END
  1223
  1312
  BEGIN
  773
  990
  224
  END
  1319
  1306
  1469""".lines.map(_.trim).toList

我们将使用 foldRight 在迭代之间传递状态累加器。
请注意，我们使用 foldRight 来提高构建结果列表的效率，因此我们将在遇到 BEGIN 之前遇到 END。

case class StripStatus(list:List[String], retaincurrent:Boolean)

list1.foldRight(StripStatus(Nil,false)){ (curElem:String, curStatus:StripStatus) =>
   if (curElem == "END")
      StripStatus(curStatus.list,true)
   else if (curElem == "BEGIN")
      StripStatus(curStatus.list,false)
   else if (curStatus.retaincurrent)
      StripStatus(curElem::curStatus.list, true)
   else
      curStatus
}.list

我们可以同样轻松地使用 foldLeft 和 reverse 最后的结果列表：

list1.foldLeft(StripStatus(Nil,false)){ (curStatus:StripStatus, curElem:String) =>
   if (curElem == "BEGIN")
      StripStatus(curStatus.list,true)
   else if (curElem == "END")
      StripStatus(curStatus.list,false)
   else if (curStatus.retaincurrent)
      StripStatus(curElem::curStatus.list, true)
   else
      curStatus
}.list.reverse

Answer 4

嗯嗯。这是我的看法：

def getInside(l: List[String]) = {
    def concat(in: List[String], out: List[String]): List[String] = in ::: off(out)

    def off(l: List[String]): List[String] = 
        if (l.isEmpty) Nil 
        else on(l dropWhile ("BEGIN" !=) drop 1)

    def on(l: List[String]): List[String] = 
        if (l.isEmpty) Nil
        else (concat _).tupled(l span ("END" !=))

    off(l)
}

Answer 5

我不知道 Scala，但您可以定义一个函数，返回与子字符串匹配的下一个元素的列表中的索引，并返回找到子字符串的索引以及在匹配该子字符串之前遇到的元素列表。伪代码标头：findSubstr(list, startIndex)。然后构建表达式（更多伪代码）：

beginIndex, preBeginElems = findSubstr(list, 0)
endIndex, inBetweenElems = findSubstr(list, beginIndex)
restElems = list[endIndex until the end]

如果有帮助，我可以用 Haskell 编写这个...:)

编辑：可能还有其他方法可以做到这一点

Answer 6

同样，处理列表中的多个 BEGIN...END 范围的目标相同。

def getBetweenBeginEnd(l:List[String]) = {
   def internal(l:List[String],accum:List[String]):List[String]={
      val (keep, keepChecking) = l.dropWhile("BEGIN" !=).drop(1).span("END" !=)
      if (keepChecking == Nil)
         accum:::keep
      else
         internal(keepChecking.tail,accum:::keep)
   }
   internal(l,Nil)
}