Haskellでリストを使って、コンビネーション（C）の計算プログラムを作って遊ぶ

HaskellでコンビネーションCの計算プログラムを作って遊びました。

リストを多用しています。
他にも方法はあるかもしれませんが、リストを使ってみたかっただけです。

combi.hs

c (m,n) = let denom = if m <= 0 || n <= 0 || m < n then [1,1]       --(1)
                      else case m of
                             1 -> [1,1]             --(2)
                             2 -> [2,1]             --(3)
                             x | n == 1 -> [x,1]    --(4)
                               | n == 2 -> [x,x-1]  --(5)
                               | otherwise -> [x,x-1..x-n+1]     --(6)
              nume = if n <= 0 || m < n then [1,1]      --(7)
                     else case n of
                             1 -> [1,1]             --(8)
                             2 -> [2,1]             --(9)
                             x -> [n,n-1..1]        --(10)

          in
              (foldl (*) (head denom) (tail denom)) / (foldl (*) (head nume) (tail nume))     --(11)

main::IO()
main = do
    let conbi = [(10,9),(9,9),(8,3),(7,-2),(1,3)]
    print (map c conbi)

実行結果は

[10.0, 1.0, 56.0, 1.0, 1.0]

となります。（リストの区切りが見にくかったので、スペースを入れました。）

解説

上記のプログラムは、c (m,n)関数とmain関数で構成されています。

関数cの引数は、(m,n)という、2つの値からなるタプルです。
mCnを表しています。
main関数内のconbiは、計算したいコンビネーションをタプルで表したリストになります。
そのリストの各要素を引数にして関数cを呼び出しています。（map関数は、第１引数の関数に、第２引数のリストの各要素を適用して、その結果のリストを返します。）

関数cの内部ではどのような処理をしているでしょうか？

先ずは、denomの定義から。

combi.hs

             let denom = if m <= 0 || n <= 0 || m < n then [1,1]       --(1)
                      else case m of
                             1 -> [1,1]             --(2)
                             2 -> [2,1]             --(3)
                             x | n == 1 -> [x,1]    --(4)
                               | n == 2 -> [x,x-1]  --(5)
                               | otherwise -> [x,x-1..x-n+1]     --(6)

denomは、『分母』のスペルの前半分くらい。
（１）では、mやnが負だった場合や、mのほうが小さい場合、そのようなコンビネーションは計算不可のため、とりあえず、リスト[1,1]を返します。
case-of文は、条件によって処理を分けたい場合に使います。
上記のプログラムでは、mの値によって処理を分けています。
（２）で、mが1の場合、リスト[1,1]を返します（要素が１つのリストになると都合が悪いため要素２つのリストを返します（理由は後で説明））。
（３）では、2の時に[2,1]を返します。
（４）以降では、それ以外の値の場合どうするかを記述しています。
それ以外の値の場合を、さらに細かく条件分けしています。
（４）では、nが1の場合、（５）では、nが2の場合です。
（６）は、それ以外の場合です。
コンビネーションの計算するときの分母は、
m×(m-1)×(m-2)×...×(m-n+1)です。
（２）～（６）まで、分母でかける値の一覧をリストにしています。

combi.hs

              nume = if n <= 0 || m < n then [1,1]      --(7)
                     else case n of
                             1 -> [1,1]             --(8)
                             2 -> [2,1]             --(9)
                             x -> [n,n-1..1]        --(10)

次にnumeの定義です。分子です。
（７）は、nが負だった場合や、mのほうが小さい場合、リスト[1,1]を返しています。
（８）（９）（１０）は分母の時と同じです。
コンビネーションの計算するときの分子は
n×(n-1)×(n-2)×...×1です。

最後に関数cの戻り値を決定する部分です。

combi.hs

          in
              (foldl (*) (head denom) (tail denom)) / (foldl (*) (head nume) (tail nume))     --(11)

foldl関数は、第２引数を初期値として、第３引数のリストの各要素を順次、第１引数の関数に適用します。
headは、リストの先頭の要素を取り出します。
tailはhead以降の要素をリストで返します。
例えば、分母リストdenomが[10,9,8,7,6,5]の場合
head denomは、10になります。
tail denomは、[9,8,7,6,5]になります。
つまり、(foldl (*) (head denom) (tail denom))は、
10を初期値として、まずは9を(*)に適用するので、10×9
そして次は、その結果と、リストの次の要素をかけます、90×8
それを繰り返します。
よって、10,9,8,7,6,5を全てかけた値が導出されます。

分子を表す部分も同様に考えることができます。