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を全てかけた値が導出されます。

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