2026-08-29
Companion.hs
companion :: [Integer] -> [[Integer]]
数列 a が、係数 c1, …, ck を使って an = c1an−1 + c2an−2 + … + ckan−k で決まるとします。係数のリスト [c1, …, ck] から、直前の k 項を上から新しい順に並べた縦ベクトル (an−1, …, an−k) に掛けると (an, …, an−k+1) になる k 行 k 列の行列を、行のリストとして返す companion を書いてください。行列に縦ベクトルを掛けた結果の i 段目は、行列の i 行目と縦ベクトルの対応する要素を掛けて足した値です。係数のリストは空でないものとします。
入力例 1
companion [1, 1]
出力例 1
[[1,1],[1,0]]
入力例 2
companion [2, 0, 5]
出力例 2
[[2,0,5],[1,0,0],[0,1,0]]
入力例 3
companion [3]
出力例 3
[[3]]
Reference
companion :: [Integer] -> [[Integer]]
companion cs = cs : [[if j == i then 1 else 0 | j <- [1 .. k]] | i <- [1 .. k - 1]]
where
k = length cs
結果の1段目は an で、漸化式そのものなので、行列の1行目は係数のリスト cs をそのまま使います。2段目から下は、縦ベクトルの段を1つずつ下へずらすだけです。i + 1 段目に来るのは an−i で、これは元の縦ベクトルの i 段目なので、i + 1 行目は i 列目だけが1で残りが0の行になります。
内包表記の i は1から k − 1 まで回り、2行目から k 行目を作ります。入力例 2 では [1,0,0] と [0,1,0] が cs の下に並びます。k が1なら [1 .. 0] は空なので、入力例 3 のように1行目だけの行列になります。この行列を n 回掛ければ、縦ベクトルは n 項先へ進みます。
掲載したのは参考実装で、唯一の正解ではありません。cs : map (take k) (take (k - 1) (iterate (0 :) (1 : replicate (k - 1) 0))) のように、1の位置を右へずらした行を iterate で作り、それぞれ長さ k に切りそろえて並べる書き方もあります。