リストを利用したメモ化の一般化

リストを利用したメモ化の一般化
==========================

正しく対応づけられた括弧
---------------------

正しく対応づけられた括弧の並びが何通りあるかを考える。

### 漸化式

#### 括弧が0組から3組のとき

括弧が0組のときは1通りだ。括弧が1組のときは()だけなので1通りとなる。
2組のときは()()と(())の2通りだ。
3組の括弧の正しい並びは5通りある。
()()(), ()(()), (())(), (()()), ((()))

#### 括弧が4組のとき

4組の括弧の正しい並びは何通りあるだろうか。
まず3組の括弧の正しい並びの先頭に()をつけることで5通りの
組み合わせができる。

()()()(), ()()(()), ()(())(), ()(()()), ()((()))

次に2組の括弧の正しい並びの先頭に(())をつけることで2通りの
組み合わせができる。

(())()(), (())(())

上記の2つは先頭の(...)のなかにそれぞれ0組の括弧があるもの、
1組の括弧があるものと考えることができる。
よって次に考えるのは先頭の(...)のなかに2組の括弧があるものと
先頭の(...)のなかに3組の括弧があるものだ。

先頭の括弧のなかに2組の括弧があるものは
先頭は(()())と((()))の2通りとなりそれに続くものは
1組の括弧であり()の1通りだ。

(()())(), ((()))()

先頭の括弧のなかに3組の括弧があるものは
先頭が(...)の...の部分が3組の括弧のすべての組み合わせとなる。
続く括弧はない。

(()()()), (()((())), ((())()), ((()())), (((())))

の5通りとなる。
よって5 + 2 + 2 + 5 = 14通りとなる。これらは

1. 0組の括弧を含む先頭の括弧に3組の括弧が続いたもの(5通り)
2. 1組の括弧を含む先頭の括弧に2組の括弧が続いたもの(2通り)
3. 2組の括弧を含む先頭の括弧に1組の括弧が続いたもの(2通り)
4. 3組の括弧を含む先頭の括弧に0組の括弧が続いたもの(5通り)

となっている。

#### 括弧が5組のとき

同様に考えると括弧が5組のときには

1. 0組の括弧を含む先頭の括弧に4組の括弧が続いたもの
2. 1組の括弧を含む先頭の括弧に3組の括弧が続いたもの
3. 2組の括弧を含む先頭の括弧に2組の括弧が続いたもの
4. 3組の括弧を含む先頭の括弧に1組の括弧が続いたもの
5. 4組の括弧を含む先頭の括弧に0組の括弧が続いたもの

となる。ここでn組の括弧の配置の数をPnとすると、

    P5 = P0 * P4 + P1 * P3 + P2 * P2 + P3 * P1 + P4 * P0

となり、P5 = 1 * 14 + 1 * 5 + 2 * 2 + 5 * 1 + 14 * 1で42となる。

#### 括弧がn組のとき

一般化すると

    Pn = P0 * P(n-1) + P1 * P(n-2) + P2 * P(n-3) + ... + P(n-1) * P0

となる。

### 単純な実装

n組の括弧でm通りの配置があるとしてnからmを求める関数を書く。
比較的小さいnに対してmは非常に大きくなる。
nの型をIntとしmの型をIntegerとした。

```hs:parens.hs
parens :: Int -> Integer
parens 0 = 1
parens n = sum [ parens h * parens t | h <- [0 .. n - 1], let t = n - h - 1 ]
```

となる。

    % ghci parens.hs
    *Main> parens 3
    5
    *Main> parens 4
    14
    *Main> parens 5
    42
    *Main> parens 10
    16796
    *Main> parens 15
    9694845

n = 15くらいでかなり時間がかかるようになる。

### メモ化

上記のような単純な定義ではparens 10を求めるのにparens 9からparens 0を求め、
parens 9を求めるのにはparens 8からparens 0を求め、
parens 8を求めるのにはparens 7からparens 0を求め、
...
のように非常に冗長な計算を行っている。
よってparens nを求めるのにn-1以下をメモ化することで高速化できる。
リストを使ってメモ化してみよう。

```hs:parensMemo.hs
parens :: Int -> Integer
parens 0 = 1
parens n = sum
        [ parensL !! h * parensL !! t | h <- [0 .. n - 1], let t = n - h - 1 ]

parensL :: [Integer]
parensL = map parens [0 ..]
```

試してみよう。

    % ghci parensMemo.hs
    *Main> parensL !! 3
    5
    *Main> parensL !! 5
    42
    *Main> parensL !! 15
    9694845
    *Main> parensL !! 100
    896519947090131496687170070074100632420837521538745909320

n = 100でもすぐに答えが出る。

「メモ化」の抽象化
----------------

漸化式であれば何であれ同じようなメモ化が可能だ。
「メモ化」そのものを抽象化した関数を書いてみよう。

```hs:memoization.hs
memoization :: ([a] -> Int -> a) -> [a]
memoization f = xs
        where xs = map (f xs) [0 ..]
```

この関数は引数に関数をとりリストを返す。
引数となる関数は
「もし求める数列のリストがあったならそこからn番目を求める関数」
である。

括弧の並べかたの例で試してみよう。

```hs:memoization.hs
parens :: [Integer] -> Int -> Integer
parens _ 0 = 1
parens l n = sum [ l !! h * l !! t | h <- [0 .. n - 1], let t = n - h - 1 ]

parensL :: [Integer]
parensL = memoization parens
```

同じようにフィボナッチ数列でも試してみる。

```hs:memoization.hs
fib :: [Integer] -> Int -> Integer
fib _ 0 = 0
fib _ 1 = 1
fib l n = l !! (n - 1) + l !! (n - 2)

fibs :: [Integer]
fibs = memoization fib
```

まとめ
-----

漸化式をそのままコードにすると冗長な計算が行われてしまうことがある。
リストを使ってメモ化することができるが、「メモ化」そのものを関数として抽象化してみた。