计算阵列的长度而不会炸毁堆栈

Question

如何在不炸毁堆栈的情况下计算阵列的长度？我的两次尝试对我来说都不好看

let rec slowComputeLength xs = match xs with
                               | x::xss -> 1 + slowComputeLength xss
                               | _ -> 0

let computeLength xs = List.fold (fun acc _ -> acc + 1) 0 xs

我可以想到在模式匹配的第一个版本中传递累加器,但这会使API变得丑陋

let rec slowComputeLength xs acc = match xs with
                                   | x::xss -> slowComputeLength xss acc+1
                                   | _ -> 0

List.fold是正确的方式还是创建类似下面的东西,我相信它也会打到堆栈？

(1 + (1 + (1 + (...))))?

PS - 我这样做是为了练习,理想情况下我们应该使用Array.Length.

Answer 1

通常的技巧是定义一个嵌套的递归函数来保持累加器:

let computeLength xs = 
  let rec loop acc xs = 
    match xs with
    | _::xs -> loop (acc+1) xs
    | _ -> acc
  loop 0 xs

这里,该loop函数具有附加的累加器参数,但它不会使外部computeLength函数的API 变得丑陋,因为该loop函数是嵌套的,并且永远不会被用户直接调用.