我找到了 this question在 hubFS 上,但它处理基于单个元素的拆分标准。我想根据相邻元素的比较进行拆分,因此类型如下所示:
val split = ('T -> 'T -> bool) -> 'T list -> 'T list list
目前,我试图从 Don 的命令式解决方案开始,但我无法弄清楚如何初始化和使用“prev”值进行比较。折叠是更好的方法吗?
//Don's solution for single criteria, copied from hubFS
let SequencesStartingWith n (s:seq<_>) =
seq { use ie = s.GetEnumerator()
let acc = new ResizeArray<_>()
while ie.MoveNext() do
let x = ie.Current
if x = n && acc.Count > 0 then
yield ResizeArray.to_list acc
acc.Clear()
acc.Add x
if acc.Count > 0 then
yield ResizeArray.to_list acc }
最佳答案
这是一个有趣的问题!我最近需要在 C# 中为我的 article about grouping 完全实现这个(因为函数的类型签名与 groupBy
非常相似,所以它可以在 LINQ 查询中用作 group by
子句)。 C# 实现虽然很丑陋。
无论如何,必须有一种方法可以使用一些简单的原语来表达此功能。 F# 库似乎没有提供任何适合此目的的函数。我能够想出两个似乎普遍有用的函数,可以组合在一起来解决这个问题,所以它们是:
// Splits a list into two lists using the specified function
// The list is split between two elements for which 'f' returns 'true'
let splitAt f list =
let rec splitAtAux acc list =
match list with
| x::y::ys when f x y -> List.rev (x::acc), y::ys
| x::xs -> splitAtAux (x::acc) xs
| [] -> (List.rev acc), []
splitAtAux [] list
val splitAt : ('a -> 'a -> bool) -> 'a list -> 'a list * 'a list
这与我们想要实现的类似,但它仅将列表拆分为两部分(这比多次拆分列表更简单)。然后我们需要重复这个操作,这可以使用这个函数来完成:
// Repeatedly uses 'f' to take several elements of the input list and
// aggregate them into value of type 'b until the remaining list
// (second value returned by 'f') is empty
let foldUntilEmpty f list =
let rec foldUntilEmptyAux acc list =
match f list with
| l, [] -> l::acc |> List.rev
| l, rest -> foldUntilEmptyAux (l::acc) rest
foldUntilEmptyAux [] list
val foldUntilEmpty : ('a list -> 'b * 'a list) -> 'a list -> 'b list
现在我们可以重复申请
splitAt
(将某些谓词指定为第一个参数)在输入列表上使用 foldUntilEmpty
,这为我们提供了我们想要的功能:let splitAtEvery f list = foldUntilEmpty (splitAt f) list
splitAtEvery (<>) [ 1; 1; 1; 2; 2; 3; 3; 3; 3 ];;
val it : int list list = [[1; 1; 1]; [2; 2]; [3; 3; 3; 3]]
我认为最后一步真的很好:-)。前两个函数非常简单,可能对其他事情有用,尽管它们不像 F# 核心库中的函数那样通用。
关于F#根据相邻元素的比较将列表拆分为子列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2279095/