Scala的Seq.Span方法在F#中的等效实现是什么？

如果你用过Scala，肯定知道它的span方法有多实用——它能帮你把一个可迭代集合按谓词拆分成最长的满足条件前缀和剩余后缀的元组。先看看Scala官方给出的定义：

def span(p: (A) => Boolean): (Seq[A], Seq[A])

简单说，这个方法的逻辑是：从集合开头开始，一直取元素直到遇到第一个不满足谓词的元素，把之前取到的作为第一个返回值，剩下的所有元素作为第二个返回值。

关于它有几个关键细节要注意：

• 如果你的谓词函数没有副作用，c span p和(c takeWhile p, c dropWhile p)效果完全一样，但span只需要遍历一次集合，效率更高
• 要是底层集合是无序的，每次运行span可能得到不同的结果
• 对迭代器使用这个方法后，原迭代器就不能再用了，只能用返回的迭代器，不然行为是未定义的

回到F#这边，我查了Seq模块的所有方法，发现没有直接对应的功能：

• groupBy是按谓词把所有元素分组，不管顺序，和span的"最长前缀"逻辑完全不同
• partition也是拆分满足和不满足的元素，但同样不区分前后顺序，只要满足就归到一组
• splitAt是按固定索引拆分，不是按谓词条件判断

我们需要的是一个能同时完成takeWhile和skipWhile的功能，但只遍历一次序列的函数——毕竟如果是无限序列的话，两次遍历根本行不通。

先看一个简单的List版本（但这个是两次遍历，只适合有限列表）：

module List 
let span (predicate: 'a -> bool) (list: 'a list): ('a list * 'a list) = 
    (list |> List.takeWhile predicate, list |> List.skipWhile predicate)

比如用这个处理示例：

[1;2;3;4] |> List.span (fun i -> i % 2 = 1) // 结果是 ([1], [2;3;4])

但要支持无限序列，必须改成一次遍历的实现。这里我写了一个基于枚举器的版本：

module Seq =
    let span predicate (source: seq<'a>) =
        use enumerator = source.GetEnumerator()
        let rec takePrefix acc =
            if enumerator.MoveNext() then
                let current = enumerator.Current
                if predicate current then
                    takePrefix (current :: acc)
                else
                    // 把当前不满足的元素放回，生成后缀序列
                    let suffix = 
                        seq {
                            yield current
                            while enumerator.MoveNext() do
                                yield enumerator.Current
                        }
                    (List.rev acc, suffix)
            else
                (List.rev acc, Seq.empty)
        takePrefix []

这个实现的思路很简单：

1. 用一个枚举器遍历输入序列
2. 递归收集所有满足谓词的元素到前缀列表
3. 遇到第一个不满足的元素时，把它和剩下的元素组成后缀序列
4. 前缀列表因为是递归收集的，最后要反转回来保持原顺序

这样整个过程只遍历一次序列，完美支持无限序列的场景。比如用它处理无限序列：

let infiniteSeq = Seq.initInfinite id
let (prefix, suffix) = infiniteSeq |> Seq.span (fun x -> x < 5)
// prefix 是 [0;1;2;3;4]，suffix 是从5开始的无限序列

内容的提问来源于stack exchange，提问作者Aaron Stainback