F#：基于相邻元素的比较将列表拆分为子列表

Question

我在hubFS上找到了这个问题，但是它处理的是基于单个元素的分割标准。我想要根据相邻元素的比较来进行分割，所以类型应该是这样的：

val split = ('T -> 'T -> bool) -> 'T list -> 'T list list

目前，我正尝试从Don的命令式解决方案入手，但我无法想出如何初始化并使用“prev”值进行比较。使用fold是一个更好的方法吗？

//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 }

- Benjol

---

注意：这个相关问题询问如何根据谓词将列表拆分并仅保留pred = true元素。 - Benjol

交叉引用：这里是相同的问题，但是针对序列。 - Benjol

Answer 1

如何呢：

let splitOn test lst =
    List.foldBack (fun el lst ->
            match lst with
            | [] -> [[el]]
            | (x::xs)::ys when not (test el x) -> (el::(x::xs))::ys
            | _ -> [el]::lst
         )  lst [] 

折返功能可以避免需要反转列表。

- Shooton

---

欢迎来到 Stack Overflow！它能正常工作了，现在只需要好好理解一下就行了...！ - Benjol

Answer 2

这是一个有意思的问题！最近我需要在C＃中实现这个功能，用于我的关于分组的文章（因为该函数的类型签名与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

现在我们可以使用foldUntilEmpty反复应用splitAt（将某个谓词指定为第一个参数）到输入列表中，这样就得到了我们想要的函数。

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#核心库的函数那样通用。

- Tomas Petricek

---

@Tomas，好的。空列表会导致值限制错误（对于我的解决方案也是如此）。我从来不确定该怎么做->我是否需要强制指定空列表的类型？同时，您对我最初问题的另一半有什么想法——即在以命令方式执行时如何初始化“prev”值以进行比较。 - Benjol

要初始化prev值，您需要在循环结束时调用MoveNext（请参阅我的C#文章中的操作）。F#不支持do .. while循环，因此您需要使用显式递归来实现此功能。 - Tomas Petricek

Answer 3

“相邻”这个词让我想起了Seq.pairwise。

let splitAt pred xs =
    if Seq.isEmpty xs then
        []
    else
        xs
        |> Seq.pairwise
        |> Seq.fold (fun (curr :: rest as lists) (i, j) -> if pred i j then [j] :: lists else (j :: curr) :: rest) [[Seq.head xs]]
        |> List.rev
        |> List.map List.rev

例子：

[1;1;2;3;3;3;2;1;2;2]
|> splitAt (>)

提供：

[[1; 1; 2; 3; 3; 3]; [2]; [1; 2; 2]]

- Joh

Answer 4

经过进一步思考，我想出了这个解决方案。我不确定它是否很易读（除了我写的人）。

更新 基于Tomas答案中更好的匹配示例，这是一个改进版本，它删除了“代码味道”（请参见以前版本的编辑），并且稍微更易读（我这么说）。

它仍然会在这个地方 (splitOn (<>) []) 失败，因为可怕的值约束错误，但我认为这可能是不可避免的。

（编辑：Johan Kullbom发现的错误已经被纠正，现在对于[1;1;2;3]可以正确工作。问题是在第一个匹配中直接吃掉了两个元素，这意味着我错过了一个比较/检查。）

//Function for splitting list into list of lists based on comparison of adjacent elements
let splitOn test lst = 
    let rec loop lst inner outer = //inner=current sublist, outer=list of sublists
        match lst with 
        | x::y::ys when test x y -> loop (y::ys) [] (List.rev (x::inner) :: outer)
        | x::xs ->                  loop xs (x::inner) outer
        | _ ->                      List.rev ((List.rev inner) :: outer)
    loop lst [] []

splitOn (fun a b -> b - a > 1) [1]
> val it : [[1]]

splitOn (fun a b -> b - a > 1) [1;3]
> val it : [[1]; [3]]

splitOn (fun a b -> b - a > 1) [1;2;3;4;6;7;8;9;11;12;13;14;15;16;18;19;21]
> val it : [[1; 2; 3; 4]; [6; 7; 8; 9]; [11; 12; 13; 14; 15; 16]; [18; 19]; [21]]

有没有对此有什么想法，或者对我问题中的部分解决方案有什么看法？

- Benjol

---

这段代码比我写的函数更易读，但是我会将 loop (List.head ...etc 替换为 match lst with | [] -> [[]] | hd::tl -> loop hd tl [] []，这样它就不会在输入为空时出现问题。 - cfern

@cfern，无论如何都会在空列表上中断（正如Tomas的解决方案一样），因为存在#£$£~"!值限制错误。 - Benjol

@Benjol：你的解决方案在空列表上有什么问题？splitOn (fun a b -> b - a > 1) [] 给我返回 [[]]... - Johan Kullbom

@Benjol：你目前的解决方案在“边角情况”下存在问题——对于像[1; 3; 5;]这样的输入，它不能给出正确的结果（应该是[[1]; [3]; [5]]而不是[[1]; [3; 5]]）。 - Johan Kullbom

@Johan Kullbom，发现得好！我已经修复了。另外针对您的第一个评论，我已经更新了我的答案。 - Benjol

Answer 5

我更喜欢使用List.fold而不是显式递归。

let splitOn pred = function
    | []       -> []
    | hd :: tl -> 
        let (outer, inner, _) =
            List.fold (fun (outer, inner, prev) curr ->
                            if pred prev curr 
                            then (List.rev inner) :: outer, [curr], curr
                            else outer, curr :: inner, curr)
                      ([], [hd], hd)
                      tl
        List.rev ((List.rev inner) :: outer)

- Johan Kullbom

---

你的解决方案比我的难以阅读。因为我没有写它！ :) - Benjol

Answer 6

我喜欢@Joh和@Johan提供的答案，因为这些解决方案似乎最符合惯用法和直接。我也喜欢@Shooton提出的想法。然而，每个解决方案都有自己的缺点。
我试图避免以下情况：

• 反转列表
• 取消拆分并重新连接临时结果
• 复杂的match指令
• 即使Seq.pairwise似乎是多余的
• 检查列表是否为空可以在使用下面的Unchecked.defaultof<_>的代价下被删除

这是我的版本：

let splitWhen f src =
    if List.isEmpty src then [] else
    src
    |> List.foldBack
        (fun el (prev, current, rest) ->
            if f el prev
            then el , [el]          , current :: rest
            else el , el :: current , rest
        )
        <| (List.head src, [], [])               // Initial value does not matter, dislike using Unchecked.defaultof<_>
    |> fun (_, current, rest) -> current :: rest // Merge temporary lists
    |> List.filter (not << List.isEmpty)         // Drop tail element

- Be Brave Be Like Ukraine