Namaran

Code daily. Without assist.

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 に切りそろえて並べる書き方もあります。