函数式 (Scala) 编程：在令牌上拆分 List[Char]

Question

递归按标记拆分函数的普遍接受实现是什么？

例如：

val s: List[Char] = 'F' :: 'o' :: 'o' :: ' ' :: 'b' :: 'a' :: 'r' :: ' ' :: 'f' :: 'o':: 'o':: ' ' :: 'b' :: 'a' :: 'r' :: Nil
fooSplit(s) // -> List(List('F','o','o'), List('b', 'a', 'r'), List('f', 'o', 'o'), List('b','a','r'))

以下是我在对参数进行模式匹配时提出的基本情况：

def fooSplit(text: List[Char]): List[List[Char]] = text match {
  case x :: ' ' :: xs =>
    // Somehow append old list to fooSplit(xs) <?>
    println(x + "_")
    fooSplit(xs)

  case x :: xs =>
    println(x + "")
    fooSplit(xs)

  case Nil => Nil
}

我按照上述结构进行的大部分尝试几乎总是导致 List('F', List('O', List('O'), ...)...)。如果没有想出一些非常险恶的双重模式匹配，我似乎无法集中精力扩展而不是附加到内部列表。

我还想引用 Scala Cookbook：

Use flatMap in situations where you run map followed by flatten. The specific situation is this:

• You’re using map (or a for/yield expression) to create a new collection from an existing collection.
• The resulting collection is a list of lists.
• You call flatten immediately after map (or a for/yield expression)

这似乎是使用 flatMap 的一个非常可能的情况，有人可以对此提供见解吗？

Answer 1

仅仅因为您要返回 List[List[String]] 的实例并不意味着您需要展平它，有时您可能需要这些值。我建议这样做：

def fooSplit(text: List[Char]): List[List[Char]] = {
  @tailrec
  def fooSplitHelper(currentListBeforeToken: List[Char] = List.empty, list: List[Char], acc: List[List[Char]] = List.empty): List[List[Char]] = {
    if (list.isEmpty) {
      currentListBeforeToken.reverse :: acc
    } else {
      list.head match {
        case ' ' => fooSplitHelper(List.empty[Char], list.tail, currentListBeforeToken.reverse :: acc)
        case otherChar => fooSplitHelper(otherChar :: currentListBeforeToken, list.tail, acc)
      }
    }
  }
  fooSplitHelper(list = text).reverse
}

Answer 2

防止此函数变得“险恶”的一个重要实现是，您可以将正在构建的当前子列表保存为它自己的变量，并且仅在完成时将其添加到结果中。

从那里开始，它非常简单。

基本上有三种情况：列表末尾（完成！），当前元素是 space（将中间添加到结果，并再次从空开始），其他一切（继续添加到中间），所以你只需拼写出来：

   @tailrec
   def split(
     in: List[Char], 
     next: List[Char] = Nil, 
     out: List[List[Char]] = Nil
   ): List[List[Char]] = in match { 
       case Nil => out.map(_.reverse).reverse
       case ' ' :: tail  => split(tail,  Nil, next :: out)
       case head :: tail => split(tail, head :: next, out)
     }

这里有几个常见的技巧是将构建的实际结果传递给递归调用，而不是仅仅返回它（这样函数可以优化为 tail-recursive - 不会需要 space 在堆栈上），而且，你以相反的方向构建你的列表，将元素添加到它们之前，而不是追加，然后在列表完成时在最后反转（这允许实现保持线性，因为添加到列表之前是常数时间，不像追加，它是 O(N)，使整个事情成为二次的（讨厌！））。

函数式 (Scala) 编程：在令牌上拆分 List[Char]

Functional (Scala) programming: Split a List[Char] on a token

scala

recursion

functional-programming

pattern-matching