隣接n項間漸化式 - dachs

昨日，zipWithAnyなんてものを考えたのは，Perlでも考えた隣接n項間漸化式をHaskellでも考えようとしたためです．

例えば，隣接4項間で考えてみます．

        | a0 a1 a2 a3 a4 a5 a6 a7  a8  a9
     a0 | a1 a2 a3 a4 a5 a6 a7 a8  a9  a10
(a0) a1 | a2 a3 a4 a5 a6 a7 a8 a9 a10

          a3 a4 a5 a6 a7 a8 a9

とずらすことで，隣接n項間漸化式は計算できることになります．例えば，a3を計算するにはその上のa0，a1，a2を知ればよいことになります．

a0，a1，a2, ....ですが，a0，a1，a2は初期条件として与えられます．この列を「左に一つ」ずらして，最初の一個（a0）をとって（つまりtail），さらに一つずらして，最初の一個（a1）をとります．
こうすると，1列目を計算して，a3を求め，すると次に，2列目が計算できて・・・と，順番に計算していけます．

求めたい列をreclistとすると，二行目は tail reclist，三行目はtail $ tail reclistです．これらに対して，zipWithAny を適用すれば，reclistが作られます．段階をおって，tailを適用するのにはtailsを使いました．ただし，これを無限リストに使うと，四行，五行と余計な行まででてｊくるので必要な分だけとるためにtakeを用います．上の図中の上から三行を作るには，

(take 3 . tails) reclist

となります．これにzipWithAnyを適用させます．例えば $a_{n}=a_{n-1}+a_{n-2}+a_{n-3}$ （ただし，初期値は $a_0=0$ ， $a_1=1$ ， $a_2=1$ ）を計算させるには，

reclist :: [Integer]
reclist = 0:1:1:zipWithAny sum ((take 3 . tails) reclist)

とすればよいことになります．例えば

initial :: [Integer]
initial = [0,1,1] -- 適当に決める

receq :: [Integer] -> Integer
receq a  = a!!0 + a!!1 + a!!2 -- 適当に決める．a!!2 が一番大きい項数の項

reclist :: [Integer]
reclist = initial++zipWithAny reqeq ((take (length initial). tails) reclist)

とすれば，汎用的になるでしょう．