Namaran

Code daily. Without assist.

2026-08-29

Recurrence.hs

import Data.List (transpose)

mul :: [[Integer]] -> [[Integer]] -> [[Integer]]
mul a b = [[sum (zipWith (*) row col) | col <- transpose b] | row <- a]

main :: IO ()
main = print (iterate (mul [[1, 2], [1, 0]]) [[1], [0]] !! 3)

これは何を出力するでしょうか?

Answer

[[5],[3]] です。

mul a b の内包表記は、外側で a の行 row を、内側で transpose b の要素 col を回します。transpose は行と列を入れ替えるので、col は b の列です。行と列の対応する要素を掛けて足した値が、結果の行列の「row 番目の行、col 番目の列」に並び、これは行列の積そのものです。

[[1], [0]] は1列の縦ベクトルで、transpose すると列が1つだけの [[1, 0]] になります。[[1, 2], [1, 0]] を掛けると、1行目は 1*1 + 2*0、2行目は 1*1 + 0*0 で、[[1], [1]] が得られます。

iterate f x は [x, f x, f (f x), …] と並ぶリストで、!! 3 は f を3回使った値です。縦ベクトルは [[1], [0]] から [[1], [1]]、[[3], [1]]、[[5], [3]] と変わります。1回掛けるごとに、新しい上の段は前の上の段と下の段の2倍の和になり、新しい下の段には前の上の段が下ります。下の段を順に読むと 0, 1, 1, 3 で、この掛け算は「前の項に、その前の項の2倍を足す」数列を1項ずつ先へ進めています。