logo标签列表

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

scalafunctional-programming
3

我们有一个字符串列表，其中包含BEGIN和END标记作为列表的一部分。在函数式编程风格中，我们能否过滤掉BEGIN-END之间的元素？我只能想到使用scala中的正则表达式（flag）方法。

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
}

有没有可能避免定义标志变量？在纯函数式编程语言中，他们是如何解决这个问题的？

你可以将var flag = false放在filter块内部。这样就不会那么糟糕了。 - Debilski
在这个列表中是否可能有多个 BEGIN...END 序列？ - Ken Bloom
如果你想要筛选出 BEGIN 和 END 之间的元素，那么“filter out”这个措辞真的很糟糕。 - Daniel C. Sobral
明白了，我的意思是相反的。获取 BEGIN 和 END 之间的元素。 - dmitry747
6个回答
7
你可以使用 drop / tail ， dropWhile 和 takeWhile 函数来处理这个问题：
val filteredList = list1.map(_.trim).dropWhile("BEGIN" !=).tail.takeWhile("END" !=)

编辑

如评论中所提到的，如果列表为空，tail将会抛出异常，因此如果你更喜欢保险一些，可以使用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]]。
1
糟糕！你打字的速度比我快，抢先一步了 :) - Kevin Wright
你有偏向 drop(1) 而非 tail 的任何理由吗？ - Kevin Wright
没错，你说得对 - 尾递归看起来更好（将更改添加到答案中）。谢谢！ - tenshi
2
drop(1)在空列表上不会失败；而tail会。因此，哪个是正确的取决于所需的行为，如果输入有误。 - Rex Kerr
@Rex 这就是我想要的答案 :) 这完全取决于输入列表中是否保证有一个 BEGIN。 - Kevin Wright
3

首先，你的列表中每个字符串都包含了行首的空格。

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

要么修剪行（即去除行首和行尾的空格）...

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

编辑

我的解决方案本末倒置，会筛选掉（过滤掉）在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是因为此时它仍然是一个Iterator。现在您有了一个列表，每个列表对应于“块”中的一批元素，如先前规定的那样。
我知道“filter out”这个词不太清楚，但我认为你正在做的是dmitry的代码的完全相反，以及Easy Angel的代码的完全相反 -- 你正在删除BEGIN和END之间的内容，而他们仅保留BEGIN和END之间的内容。 - Ken Bloom
我的问题得到了很好的答案，我觉得我的两个解决方案都非常笨拙。我需要学习更多使用Iterator.iterate的方法。不过我注意到了一个 bug，那就是Iterator.iterate返回的第一个元素将会是list1，所以你需要在takeWhile之前添加 drop(1)。 - Ken Bloom
确实，现在已经解决了。那么我就不会再在SO上深夜发帖了！（让我们看看这个决心能持续多久...） - Kevin Wright
2

我稍微扩展其他人的答案，以呈现一个列表中有两个 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并在最后反转结果列表：

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
我有一个想法 - 通过传递结果列表和标志来迭代集合。 - dmitry747
1

嗯，这是我的看法：

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)
}
请注意，这不是尾递归。 - Ken Bloom
@Ken True，确实如此，但是列表中有多少对BEGIN END才会成为问题呢？我喜欢使事情成为尾递归，但这里却相当困难。相互递归没问题——我甚至开始编写了一个带有库的跳板代码版本，但是列表连接... - Daniel C. Sobral
0
我不懂Scala，但你可以定义一个函数，返回列表中下一个与子字符串匹配的元素的索引，并返回找到子字符串的索引以及在匹配子字符串之前遇到的所有元素的列表。伪代码头：findSubstr(list, startIndex)。然后构建表达式（更多伪代码）：
beginIndex, preBeginElems = findSubstr(list, 0)
endIndex, inBetweenElems = findSubstr(list, beginIndex)
restElems = list[endIndex until the end]

如果有帮助的话，我可以用Haskell写这个... :)
编辑：可能还有其他方法可以做到。
0
再次，以处理列表中的多个 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)
}
这里不能用tail替换drop(1)，因为Nil.drop(1)==Nil，但是Nil.tail会抛出异常。 - Ken Bloom
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接