基于区间边界离散键的比较将序列分组为桶

Question

前几天，这个作业类型的问题(Create a list of custom type in F# and create two sequences of that list)可能已经很容易回答了，因为只有两种可能的结果(想想List.partition)。这让我想知道如何将分组概括为桶，包括或排除相应的边界值。

给定[5; 10; 15; 45; 50; 55]的输入和[10; 20; 50]的区间边界，产生两组

[5；10；15；45；50；55] //小于-和-等于[5；10；15；45；50；55] /大于-和-相等

我可能想得太多了。

type 'a ComparisonResult = Under of 'a | Over of 'a

let internal splitter op standardResult extraResultValue boundaries keySelector arg =
    boundaries |> List.tryFind (op (keySelector arg)) |> function
    | None -> extraResultValue
    | Some x -> standardResult x

let under boundaries =  // under and including
    boundaries |> List.rev |> splitter (>) Over (boundaries |> List.head |> Under)

let over boundaries =   // over and including
    boundaries |> splitter (<) Under (boundaries |> List.rev |> List.head |> Over)

[5; 10; 15; 45; 50; 55]
|> Seq.groupBy (under [10; 20; 50] id)
|> printfn "%A"

[5; 10; 15; 45; 50; 55]
|> Seq.groupBy (over [10; 20; 50] id)
|> printfn "%A"

Answer 1

这是我的解决办法。我想它在很多边界上表现不好。

let chunkByInterval predicate boundaries list =
    list
    |> List.groupBy (fun x -> boundaries |> List.countBy (fun b -> predicate x b))
    |> List.map snd

chunkByInterval (<=) [10; 20; 50] [5; 10; 15; 45; 50; 55] 
// [[5; 10]; [15]; [45; 50]; [55]]

chunkByInterval (>=) [10; 20; 50] [5; 10; 15; 45; 50; 55] 
// [[5]; [10; 15]; [45]; [50; 55]]

Answer 2

下面是一个尾递归解决方案，通过将两个列表放在一起，并积累一个“块”。

let chunkByInterval list intervals compare = 
    let rec chunk list intervals acc = 
        match (acc, list, intervals) with
        | (head::tail), (x::xs as xs'), (y::ys as ys') ->  
            if compare x y then 
                chunk xs ys' ((x::head)::tail) 
            else 
                chunk xs' ys ([]::acc)
        | (_, xs, _) -> xs::acc

    chunk list intervals [[]] |> List.filter (not << List.isEmpty) |> List.map List.rev |> List.rev 

和用法：

chunkByInterval [5; 10; 15; 45; 50; 55] [10; 20; 50] (<=) //[[5; 10]; [15]; [45; 50]; [55]]

有一个轻微的缺点是，由于我们是由反对者积累的，所以我们必须在最后逆转这个列表。这也假设两个列表都已排序，但通常先对它们进行排序比进行O(n ^ 2)搜索或使用查找更快。

对于同样的问题，可以使用序列表达式构建一个优雅的解决方案--使用肯定更容易。