Σ(総和)とかΠ(総積)をHaskellで定義する

id:Nabetaniさんが、日記に結城浩さんのサイトからのリンクがあって嬉しいと書かれているのを見つけた。
私の書いたものにまでリンクしていただいていた。(Nabetaniさん、結城さん、ありがとうございます。)

ところで、数学に、総和記号Σというのがある。
高校で習うと思うのだが、たとえば1から100までのすべての自然数の和(合計)を次のように書くものだ。

要するに、のように書くのはめんどうくさいから、のように略して書くことにしようというものだ。

和

と書くのと変わらない略記法だが、「和」ではなく「Σ」と書く慣わしになっているというわけだ。

数学では、この記号は、けっこうよく出てくる。

一般的に拡張して、たとえば、整数 i についての関数 f(i) の整数 m から n までの和ならこう書ける。

ただし、整数の総和なら、f(i)は単にiそのものだ。
（それでも、このように、f(i)=iとなるような関数は話を展開する上で意義がある。そこで、このような関数にはきちんと名前を付けて、id関数と呼ぶ。Haskellにはid関数が標準で定義されている。）

整数の総和(整数の区間はmからn)を Haskell で素朴に書くとこうなるかもしれない。

-- [Haskell]
sumOfIndex m n = sigma m n 0
  where sigma m n sum | m == n    = (sum+m)
        sigma m n sum | otherwise = sigma (m+1) n (sum+m)

でも、こう書くほうが簡潔だ。

-- [Haskell]
sumOfIndex m n = sigma [m..n]
  where sigma [] = 0
        sigma (n:ns) = n + sigma ns

さらに、id関数をつかって少しだけ一般化すると

-- [Haskell]
sumOfIndex m n = sigma [m..n] id
  where sigma [] f = 0
        sigma (n:ns) f = (f n) + sigma ns f

関数 sigma が区間[m,n]での整数の総和を定義している。
こうすると、関数 sigma の定義は、数学でのΣの定義を忠実に写していると言えるのではないだろうか。

Σは総和記号であり、は関数列 f(i) の総和を意味する。

これと似た記号に、Πというのがある。
総積記号とでもいうもので、関数列 f(i) を次々にすべて掛け合わせた答え(積)を表す。
Σほど頻繁には出てこないが、有名な記号だ。
たとえば、再帰関数の例としてよく使われる階乗。
たとえば10の階乗は、以下のように書ける。

これをHaskellで書こう。
さきほどのΣの場合と非常によく似た形で書ける。

-- [Haskell]
factorial n = product [1..n] id
  where product [] f = 1
        product (n:ns) f = (f n) * product ns f

これだけ似ていると、共通の関数として抽出できる。

-- [Haskell]
sumOfIndex m n = sigma [m..n] id
  where sigma   ns f = recursive (+) 0 ns f
factorial n = product [1..n] id
  where product ns f = recursive (*) 1 ns f

recursive :: (Int -> Int -> Int) -> Int -> [Int] -> (Int -> Int) -> Int
recursive op initial [] f = initial
recursive op initial (n:ns) f = (f n) `op` recursive op initial ns f

sigmaは数学記号Σ、productは数学記号Πをなぞっている。
これらがHaskellで定義したΣとΠ(のそれぞれ一例)だ。

実行例はこうなる。

[Hugs(Haskellインタプリタ)での実行例]
Main> sumOfIndex 1 10
55
Main> factorial 10
3628800
Main>

ほんとうは、Πに対応する関数名としては、productではなく、piを使いたかった。
だが、Haskellでは、 pi という名前は円周率πを表す定数として定義されている。
また、Haskellでは大文字で始まる名前は型に使い、値(関数も値)には使えないことになっている。
そのため、総積記号Πに対して同じ名前 pi を使うことができない。
それで、苦し紛れにproductとしたのだ。

[参考]
Cで書くとたぶんこんなふうになる。
やはり長い・・・。

/* [C] */
typedef int (*op_t)(int,int);
typedef int (*f_t)(int);

int recursive(op_t op, int initial, int m, int n, f_t f) {
  int result;
  int i;

  result = initial;
  for (i = m; i < n+1; i++) {
    result = op(result, f(i));
  }
  return result;
}
int id(int index) {
  return index;
}
int plus(int lhs, int rhs) {
  return lhs + rhs;
}
int times(int lhs, int rhs) {
  return lhs * rhs;
}
int sigma(int m, int n, f_t f) {
  return recursive(plus, 0, m, n, f);
}
int product(int m, int n, f_t f) {
  return recursive(times, 1, m, n, f);
}
int sumOfIndex(int m, int n) {
  return sigma(m, n, id);
}
int factorial(int n) {
  return product(1, n, id);
}

難しい内容ではないかもしれないが、Haskell版が6行で終わることからすると、かなり読むのも書くのもめんどうな定義ではあると言えるだろう。

Cでこれらの関数を1から100までの総和と10の階乗を求めるのに使うと、以下のようになる。

#include <stdio.h>
#include <stdlib.h>

/* ここに上記の関数定義を記述する。 */

int main(int argc, char * argv[]) {
  int m = strtol(argv[1], NULL, 10);
  int n = strtol(argv[2], NULL, 10);
  printf("sumOfIndex(%d,%d)=%d\n", m, n, sumOfIndex(m, n));
  printf("factorial(%d)=%d\n", n, factorial(n));
  return 0;
}

[C版の実行例]
$ gcc --ansi -Wall -o sum sum.c

$ ./sum 1 10
sumOfIndex(1,10)=55
factorial(10)=3628800

$