foldrでナップザックDP

# ナップザック問題とは

難しい問題だが動的計画法を使うことで効率的に解けることで有名で、DPの紹介などでは定番の問題。

こちらの記事から、問題と漸化式を引用します。
[典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～](https://qiita.com/drken/items/a5e6fe22863b7992efdb)

> **$n$ 個の品物があり、$i$ 番目の品物のそれぞれ重さと価値が $\rm{weight}[i], \rm{value}[i]$ となっている ($i = 0, 1, ..., n-1$)。
これらの品物から重さの総和が $W$ を超えないように選んだときの、価値の総和の最大値を求めよ。**

DPは、ある見方ではDAG上の最短距離/最長距離/パス数の数え上げであり、ある見方では漸化式の計算だ。以下の漸化式を計算すると、$n$個の品物$W$の重さの場合のナップザック問題を解くことができる。

> **＜DP漸化式＞**
>
```math
\rm{dp}[i+1][w] = \left\{
\begin{array}{ll}
\max (\rm{dp}[i][w-\rm{weight}[i]] + \rm{value}[i], \rm{dp}[i][w]) & (w \ge \rm{weight}[i]) \\
\rm{dp}[i][w] & (w < \rm{weight}[i])
\end{array}
\right.
```
>
> **<DP初期条件＞**
$$\rm{dp}[0][w] = 0　(w = 0, 1, \dots, W)$$

漸化式を見ると、DPテーブルの$dp[i+1]$を求めるのにその直前の$dp[i]$しか使っていない。このような畳み込み処理は、[`foldr`](https://hackage.haskell.org/package/base-4.12.0.0/docs/Prelude.html#v:foldr)を使うことで簡単に実装することができる。

# foldr

`foldr`は以下のような関数だ。`f :: a -> b -> b`を実装すると、それを使って畳み込んでくれる。

```Haskell
foldr :: (a -> b -> b) -> b -> [a] -> b
```

# foldrでナップザックDP

まず`foldr`の型変数`a`, `b`が何になるかを考える。

ナップザック問題は重さと価値のリストが入力として渡されるので、型変数`a`は`(Int, Int)`になるだろう。
また、DPテーブルの`dp[i]`は「`i`番目までの品物の中から、重さがそれぞれインデックス`w`を超えないように選んだときの、価値の総和の最大値のリスト」だ。すなわち、型変数`b`は「価値の総和の最大値のリスト」ということで、`[Int]`になるだろう。

これを当てはめて特殊化した`foldr`の型は下の通りだ。

```Haskell
foldr :: ((Int, Int) -> [Int] -> [Int]) -- 畳み込み関数
      -> [Int]                          -- 初期値
      -> [(Int, Int)]                   -- 入力(W, V)
      -> [Int]
```

これで、作る畳み込み関数の型が`knapsack :: (Int, Int) -> [Int] -> [Int]`になることを確認できた。
この`knapsack`は、`weight[i]`, `value[i]`, `dp[i]`を受け取って、`dp[i+1]`を返す関数だ。

つまり、漸化式がそのまま畳み込み関数になる。

>```math
\rm{dp}[i+1][w] = \left\{
\begin{array}{ll}
\max (\rm{dp}[i][w-\rm{weight}[i]] + \rm{value}[i], \rm{dp}[i][w]) & (w \ge \rm{weight}[i]) \\
\rm{dp}[i][w] & (w < \rm{weight}[i])
\end{array}
\right.
```

実装に落とし込んでみると、読みやすくてなかなか良い。

```Haskell
knapsack :: (Int, Int) -> [Int] -> [Int]
knapsack (wi, vi) dp = do
    w' <- [0 .. length dp - 1]
    return $ if
        | w' >= wi  -> max ((dp !! (w' - wi)) + vi) (dp !! w')
        | otherwise -> dp !! w'
```

## 例題を解く
問題も同記事から引用する。何度も引用しているが、この記事はDPの入門に最適なので、DPについて不安がある人はこちらを読むと良い。
[典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～](https://qiita.com/drken/items/a5e6fe22863b7992efdb)

>**【数値例】**
**1)** 
**　$n = 6$**
**　$(\rm{weight},\rm{value}) = {(2,3), (1,2), (3,6), (2,1), (1,3), (5,85)}$**
**　$W = 9$**
**　答え: 94 ((3,6), (1,3), (5,85) を選んだときが最大です)**

これを解いてみよう。

```Haskell
>>> let w = 9
>>>     weights = [2,1,3,2,1,5]
>>>     values =  [3,2,6,1,3,85]
>>> foldr knapsack (replicate (w + 1) 0) (zip weights values)
[0,3,5,6,9,85,88,90,91,94]
```

`replicate (w + 1) 0`はDPテーブルの最初の行であり、`dp[0]`の値だ。重さ`0`から重さ`9`までを全て`0`で埋めたリストを初期値としている。返ってきたのはDPテーブルの最後の行であり、`dp[n]`の値だ。インデックス$W$には`94`が入っており、きちんと答えを出せていることを確認できた。

# より複雑なDPに対応するには

ナップザック問題では、`dp[i+1]`を求めるのに`dp[i]`が分かっていればよかった。しかし、もっと過去の添字が必要だったり、DPテーブル全体が必要な場合はどうすれば良いのだろう。
残念ながらそれは`foldr`では対応できない。しかし、`foldr`の一般化であるCatamorphism（参考: [おじいさん、今日のご飯はCatamorphismですよ](https://qiita.com/rinse_/items/878a962f92e675f21695)）を過去の結果全てを畳み込み関数に渡すよう拡張したものがHistomorphismという名前で知られており、これを使えばDPテーブル全体を使って計算をすることができる。

Histomorphismについての解説もそのうち作る予定だが、ここで簡単に`foldr`のHistomorphism版を紹介しよう。

Histomorphismでは、リストの代わりにリストに付加情報を持たせられるようにしたデータ構造を使う。余談だが、このデータ構造はリストのように`Monad`のインスタンスにはならない。その代わり、`Comonad`のインスタンスになる。

```Haskell
data List' a b = Nil' b | Cons' b a (List' a b)
    deriving (Functor)

instance Comonad (ListA' a) where
    extract (Nil' b)      = b
    extract (Cons' b _ _) = b
    extend f l@(Nil' _)       = Nil'' $ f l
    extend f l@(Cons' _ x xs) = Cons' (f l) x $ extend f xs

histfoldr :: (b -> List' b a -> a) -> a -> [b] -> a
histfoldr f = histo . Nil'
    where
    histo hist []     = extract hist
    histo hist (x:xs) = histo (Cons' (f x hist) x hist) xs
```

`foldr`とは違い、`histfoldr`では畳み込み関数が今までの計算のメモを受け取ることが分かる。これならDPテーブルのどの情報でも使うことができる。

# まとめ
`foldr`を使ってナップザックDPを実装した。
また、`histfoldr`を使ってより一般的な畳み込み処理を行う方法を考えた。