list - 子列表操作

Question

我目前想知道一种根据给定标准将列表拆分为子列表的方法。由于这项工作的教学目的，我不使用内置函数。 IE，下面的程序应该，给定一个列表，返回一个列表的列表，其中每个子列表没有重复并且按升序排列:

increment [4;4;10;20;5;30;6;10] = [[4;10;20];[5;30];[6;10]]
increment [5;6;4;3;2;1] = [[5;6];[4];[3];[2];[1]]

到目前为止，我最好的尝试是基于我生成的这段代码:

let rec increment li [lo] = 
    match li with
        |[]         ->  [lo]
        |[x]        ->  [x]::[lo]
        |x::y::xs   ->  if x = y then
                            increment (y::xs) [lo]
                        elif x < y then
                            x::(increment (y::xs) [lo])
                        else
                            (x::(increment xs [lo]))::[lo]

不幸的是，我未能创建列表列表。原理是正确的。它基于我构建的函数，如果存在则正确隔离升序列表:

let rec incrementAux li = 
    match li with
        |[]         ->  []
        |[x]        ->  [x]
        |x::y::xs   ->  if x = y then
                            incrementAux (y::xs)
                        elif x < y then
                            x::(incrementAux (y::xs))
                        else
                            x::(incrementAux [])

如有任何建议，我们将不胜感激!

Answer 1

如果你想在不使用 List 模块上的内置函数的情况下执行此操作(纯粹作为学习练习)，那么你只需要了解 map 和fold 以便您可以自己实现它们。我将从 this wikipedia article 开始.方便的是，您可以根据 fold 轻松实现 rev，所以这应该不是问题。了解每个函数的作用后，您可以像这样自己实现它们:

let rec fold f state = function
| [] -> state
| head::tail -> fold f (f state head) tail

let map f list =
    [for item in list -> f item]

let rev list = 
    fold (fun acc cur -> cur::acc) [] list

然后，您可以用自己的函数替换 Szer 解决方案中的内置函数:

let input = [4;4;10;20;5;30;6;10]
let output = [[4;10;20];[5;30];[6;10]]

let increment = 
    fold (fun (last::rest as total) x ->
        match last with
        | [] -> [x] :: rest
        | h::_ as last ->
        if x > h then (x::last)::rest
        else if x = h then total
        else [x]::total) [[]]
    >> map rev
    >> rev

let testOutput = increment input
testOutput = output

请注意，fold 的实现与 F# List 的实现方式不同。这是基于维基百科文章中的简单 Haskell 示例。功能相同，但实现却大不相同，因为 F# 实际上使用可变累加器和 for 循环。