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

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 }

Answer 1

这是一个有趣的问题!我最近需要在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

现在我们可以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#核心库中的函数那样通用.

Answer 2

怎么样:

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 [] 

foldBack消除了反转列表的需要.