函数式编程中的计数器

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].我找到了有关如何在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 []