F# :: 遍历列表并再次返回

Question

编写一个函数来计算列表中大于或等于平均值​​的元素数量（为简单起见，使用整数除法）。
仅使用列表结构的单次遍历！

---

我已经有一个解决方案，但它涉及ref变量从闭包 foo' 更改。

我对如何功能在满足[]时传递值的方式感兴趣?

---

我使用 ref 的幼稚解决方案：

let foo ls =
    let avg = ref 0
    let rec foo' xs sumAcc lenAcc  =
        match xs with
        | x'::xs'   ->
            let s = foo' xs' (x' + sumAcc) (1 + lenAcc)
            if x' < !avg then s else s + 1
        | []        ->
            avg := (sumAcc / lenAcc) //? how to change THIS to functional code ?
            0
    foo' ls 0 0

---

---

编辑(3):

我对性能感兴趣...... 在列表[1..11000]上，

`(my solution with REF) 5501: elapsed <00.0108708>`  
`(nlucaroni)            5501: elapsed <00.0041484>`  
`(kvb)                  5501: elapsed <00.0029200>`  <-- continuation is fastest
`(two pass solution)    5501: elapsed <00.0038364>`  

自1.和3.解决方案是非尾递归的，

---

// simple two-pass solution
let foo2pass (xs : System.Numerics.BigInteger list) =
    let len = System.Numerics.BigInteger.Parse(xs.Length.ToString())
    let avg = List.sum xs / len
    (List.filter (fun x -> x >= avg) xs).Length

---

两个pass 和 kvb 的版本适用于大列表，即：list [1I .. 10 000 000I]：

(two-pass solution)   5000001: elapsed <00:00:12.3200438>     <-- 12 first time
(two-pass solution)   5000001: elapsed <00:00:06.7956307>     <-- 6
(two-pass solution)   5000001: elapsed <00:00:09.1390587>     <-- 9? WHY IS THAT
(two-pass solution)   5000001: elapsed <00:00:06.8345791>     <-- 6
(two-pass solution)   5000001: elapsed <00:00:09.1071856>     <-- 9? WHY IS THAT

每个解 5 次

(kvb tail-recursive) 5000001I: elapsed <00:00:21.1825866>   <-- 21 first time
(kvb tail-recursive) 5000001I: elapsed <00:00:14.8113939>   <-- stable
(kvb tail-recursive) 5000001I: elapsed <00:00:14.8335997>
(kvb tail-recursive) 5000001I: elapsed <00:00:14.8418234>
(kvb tail-recursive) 5000001I: elapsed <00:00:14.8331327>

，对于 list [1I .. 1 000 000I]，kvb 的解更快

(two-pass solution) 500001I: elapsed <00:00:01.8975782>
(kvb tail-recursive) 500001: elapsed <00:00:00.6004453>

Answer 1

您只需将平均值与返回值一起传递到堆栈即可：

let foo ls =
    let rec foo xs sumAcc lenAcc  = match xs with
        | x::xs -> let avg,s = foo xs (x + sumAcc) (1 + lenAcc) in
                   if x < avg then (avg,s) else (avg,s+1)
        | []    -> (sumAcc / lenAcc),0
    in
    let avg,res = foo ls 0 0 in
    res

Answer 2

这是另一个选项：

let foo =
  let rec helper sum ct getCt = function
  | x::xs -> 
      helper (sum+x) (ct+1) (fun avg -> getCt(avg) + (if avg <= x then 1 else 0)) xs
  | [] -> getCt(sum/ct)
  helper 0 0 (fun avg -> 0)

为了帮助澄清这里发生的情况，我将描述辅助函数的参数：

• sum：到目前为止看到的所有项目的总和
• ct：到目前为止看到的所有项目的计数
• getCt：采用单个值的函数参数，它返回到目前为止看到的项目数量的计数，这些项目至少与该参数一样大
• 模式匹配的最终列表参数
  • 如果为空，则通过总数除以计数来计算所有项目的平均值，然后将其传递给 getCt 函数以确定有多少项目大于它。
  • 否则，递归到列表的尾部，传入更新的总计和计数。新的 getCt 函数应调用之前的 getCt 函数来查看此之前有多少项大于平均值，然后如果该项也大于平均值，则增加该总数.

还可以创建仅使用尾部调用的修改版本，因此即使在任意大小的列表上也不会导致堆栈溢出。为此，我们的 getCt 函数现在需要一个表示到目前为止计数的累加器参数：

let foo =
  let rec helper sum ct getCt = function
  | x::xs -> 
      helper (sum+x) (ct+1) (fun avg n -> getCt avg (if avg <= x then n+1 else n)) xs
  | [] -> getCt (sum/ct) 0
  helper 0 0 (fun avg n -> n)

Answer 3

Haskell 的懒惰评价确实在“喜结连理”中大放异彩：

avgList t = let (final, sum, count) = go t 0 0 0
                avg = sum `div` count
                go [] finalA sumA countA = (finalA, sumA, countA)
                go (x:xs) finalA sumA countA = go xs (x' + finalA) (sumA + x) (countA + 1)
                    where x' = if x >= avg then 1 else 0
            in final