list - 函数式编程中的计数器

Question

我构建了一个简单的函数，给定一个列表，返回一个列表列表。每个列表都必须排序。例如:

 subOrd [4;4;10;20;5;30;6;10]      --> [[4;4;10;20];[5;30];[6;10]]
 subOrd [5;6;4;3;2;1]              --> [[5;6];[4];[3];[2];[1]]

这是我目前的解决方案，除了一个细节，它工作得很好:

let rec subOrd (l1: int list) :int list list =
    let rec aux2 (l2: int list) (l3: int list) :int list=
        match l2 with
        | []                                ->  []
        | [x]                               ->  [x]
        | x0::(x1::_ as xs) when x0 > x1    ->  x0::l3
        | x0::(x1::_ as xs) when x0 <= x1   ->  (x0::l3)@(aux xs l3)
    match l1 with
    | []                ->  []
    | x::xs             ->  (aux2 l1 [])::subOrd xs

它对最后一场比赛中的每个 xs 重复该操作。通过将列表 a4 提供给函数，我得到:

let a4 = [1; 3; 4; 7; 5; 6]
val it : int list list = [[1; 3; 4; 7]; [3; 4; 7]; [4; 7]; [7]; [5; 6]; [6]]

对于 C，我想我会用一个递增的计数器来索引数组。从概念上讲，例如 xs.[i]。我找到了有关如何 Increment value in F# 的信息，但我不确定从功能上解决这个问题的最佳方法。

非常感谢任何建议。

Answer 1

您可以使用 List.foldBack 从右到左处理列表，而不是使用计数器并从左到右处理列表

let subOrd l =
    let acc x = function
    | [] -> [[x]]
    | (((y::_) as ys) :: ls) -> 
        if x <= y then ((x::ys)::ls)
        else [x]::ys::ls
    | _ -> failwith "Should never happen!"

    List.foldBack acc l []