行列

L'eclat des jours(2010-05-28)

命令プログラマにとっては行列は2次元配列なので，インデックスを使って要素にアクセスしようとするのは自然です．Haskellのように行列をリストのリストで表現すると，何だかアクセスが面倒な気がするのもうなずけます．(!!)を使えばインデックスによるアクセスと同じように表現できますが，これはコストが高そうです．ランダムアクセスが高価なリストのリストは使いものにならん．

ほんとう？そんなことはないんですよね．

ちょっと考えてみれば，行列の計算の多くはランダムアクセスではなくシーケンシャルアクセスなのでリストで十分なんですよ．件の「最大長方形の面積」はこんな感じです（外部からの入力についてはまた別途）．改良の余地はいろいろありそうだけど，シンプルに考えればよいと思います．件の記事の図3に表現されている行列を構成する(rectsがその関数)というだけのものです．

type Rect  = (Int,Int)
type Rects = [Rect]

maxRectArea :: [[Int]] -> Int
maxRectArea = maximum . map (uncurry (*)) . concatMap concat . rects

rects :: [[Int]] -> [[Rects]]
rects = tail . scanl (zipWith v) (repeat []) . map (scanl1 h)

h :: Int -> Int -> Int
_ `h` 0 = 0
n `h` _ = n+1

v :: Rects -> Int -> Rects
_  `v` 0 = []
[] `v` n = [(n,1)]
ps `v` n = case span ((n <=) . fst) ps of
  ([],_)  -> (n,1) : map yinc ps
  (qs,rs) -> (n,1+snd (last qs)) : map yinc rs

yinc :: (Int,Int) -> (Int,Int)
yinc (x,y) = (x,y+1)