6

平均以上のリスト内の要素の数をカウントする関数を記述します (簡単にするために整数除算を使用します)。リスト構造の
を使用するだけです!single traversal

私はすでにこれに対する解決策を持っていますが、それは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）：

パフォーマンスに興味があった...list [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

2つのパスと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>
4

3 に答える 3

9

戻り値を使用して平均値をスタックに渡すだけです。

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
于 2009-11-23T18:23:44.387 に答える
7

別のオプションは次のとおりです。

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)
于 2009-11-23T18:32:25.197 に答える
0

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
于 2009-12-31T20:46:28.730 に答える