F#根据相邻元素的比较将列表拆分为子列表 [英] F# Split list into sublists based on comparison of adjacent elements

问题描述

我在hubFS上发现了这个问题，但这可以解决拆分问题基于各个元素的标准.我想根据相邻元素的比较进行拆分，因此类型应如下所示:

I've found this question on hubFS, but that handles a splitting criteria based on individual elements. I'd like to split based on a comparison of adjacent elements, so the type would look like this:

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

当前，我尝试从Don的命令性解决方案开始，但是我无法弄清楚如何初始化和使用"prev"值进行比较.折叠是更好的选择吗?

Currently, I am trying to start from Don's imperative solution, but I can't work out how to initialize and use a 'prev' value for comparison. Is fold a better way to go?

//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#中针对我的有关分组的文章实施此操作(因为该函数的类型签名与groupBy非常相似，因此可以在LINQ查询中用作group by子句).但是C#的实现非常难看.

This is an interesting problem! I needed to implement exactly this in C# just recently for my article about grouping (because the type signature of the function is pretty similar to groupBy, so it can be used in LINQ query as the group by clause). The C# implementation was quite ugly though.

无论如何，必须有一种使用一些简单基元来表达此功能的方法.似乎F#库没有提供适合此目的的任何功能.我能够提出两个似乎普遍有用的函数，可以将它们组合在一起以解决此问题，因此它们是:

Anyway, there must be a way to express this function using some simple primitives. It just seems that the F# library doesn't provide any functions that fit for this purpose. I was able to come up with two functions that seem to be generally useful and can be combined together to solve this problem, so here they are:

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

这与我们要实现的目标类似，但是它仅将列表分为两部分(这比多次拆分列表更为简单).然后，我们需要重复此操作，可以使用以下功能完成此操作:

This is similar to what we want to achieve, but it splits the list only in two pieces (which is a simpler case than splitting the list multiple times). Then we'll need to repeat this operation, which can be done using this function:

// 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(将某些谓词指定为第一个参数)，这将为我们提供所需的功能:

Now we can repeatedly apply splitAt (with some predicate specified as the first argument) on the input list using foldUntilEmpty, which gives us the function we wanted:

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#核心库中的函数那么通用，但它们可能对其他方面有用.

I think that the last step is really nice :-). The first two functions are quite straightforward and may be useful for other things, although they are not as general as functions from the F# core library.

这篇关于F#根据相邻元素的比较将列表拆分为子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！