線香を焚きながら

いろいろなことを知りたい

CSVのパーサを書いた

せっかくHaskell使っているのに、パーサライブラリをまともに使ったこと無いな、ってことで書いてみた。 ライブラリは無難に attoparsec を使う。パースした結果、CSVがリストになる。

github.com

CSVの規則は、RFC4180(の日本語訳)を参考に。

CSVファイルの一般的書式 (RFC4180 日本語訳) - アルプス登山の玄関口・笠井家

もともとCSVを平坦なJSONに変換しようとしていたので、パッケージ名が csv2json となっている。 書いてみた感想としては、パーサライブラリに慣れていないことを除けば、大凡平易に書けるなと感じた。

遅延データ構造におけるメモ化再帰を理解する

Introduction

Haskellにおけるメモ化がどんな風に動いているか、ようやくわかってきたのでメモ。

競技プログラミングでよく使用されるアルゴリズムに「動的計画法(DP)」と呼ばれるものがある。 その中では、メモ化(一度計算した値を保存しておいて再び同じ計算をする代わりに保存した値を返すこと)というテクニックが使用されている。

Haskellでも、もちろんメモ化を実装することができる。メモ化について以下のような実装があるようだ。

  1. メモ用のデータ構造として遅延しない(しなくても大丈夫な)データ構造を使用するパターン(今回はMap)。 値を辞書(もしくはテーブル)として保持し、新しいデータだった場合は辞書に追加する(値を追加した新しい辞書を返す)。 github.com

  2. メモ用のデータ構造として遅延するデータ構造を使用するパターン(今回は遅延リスト)。 値を遅延リストの要素として保持し、新しいデータだった場合に初めてリストの要素を計算する。 計算(評価)されたら、今後は評価済の値が使用される。 再帰的な計算を実行する場合は、こちらの方が都合が良さそうである。 qiita.com こちらはメモ化に対応した不動点演算子を使用するバージョン(データ構造は無限の2分木)。 tanakh.hatenablog.com

比較的どのようなことをしているのかがわかりやすいのは1である。 一方、2は少しわかりづらい。 これは、遅延評価によってどのタイミングでデータが更新されるかが不明瞭だからだと思われる。

そこで、遅延評価に基づいた簡約計算を実行してみて、実際にどのように値の更新が行われるのか確認する (実際に計算できるものでも、理屈がわからないと安心して使えないので)。

簡約計算

ここでは、2で出てきた定義をそのまま使用する。

fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n = fibList !! (n - 2) + fibList !! (n - 1)

fibList :: [Integer]
fibList = map fib [0..]

fib 5が、どのように簡約されるのか見よう。 簡単のため、単純な和はすぐに評価されるものとして書く (今回はデータ構造の遅延に着目しているので、これでも問題ない、と思う)。 実際に計算されている様子は、GHCiデバッガを使用して確認することもできる。

fib 5
= fibList !! 3 + fibList !! 4
= fibList !! 3 + (map fib [0..]) !! 4
= fibList !! 3 + ((fib 0):(fib 1):(fib 2):(fib 3):(fib 4):_) !! 4
= fibList !! 3 + fib 4
= fibList !! 3 + (fibList !! 2 + fibList !! 3)
= fibList !! 3 + (fibList !! 2 + ((fib 0):(fib 1):(fib 2):(fib 3):(fib 4):_) !! 3)
= fibList !! 3 + (fibList !! 2 + fib 3)
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + fibList !! 2))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + ((fib 0):(fib 1):(fib 2):(fib 3):(fib 4):_) !! 2))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + fib 2))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fibList !! 0 + fibList !! 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fibList !! 0 + ((fib 0):(fib 1):(fib 2):(fib 3):(fib 4):_) !! 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fibList !! 0 + fib 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fibList !! 0 + 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (((fib 0):1:(fib 2):(fib 3):(fib 4):_) !! 0 + 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fib 0 + 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (0 + 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + 1))
= fibList !! 3 + (fibList !! 2 + ((0:1:1:(fib 3):(fib 4):_) !! 1 + 1))
= fibList !! 3 + (fibList !! 2 + (1 + 1))
= fibList !! 3 + (fibList !! 2 + 2)
= fibList !! 3 + ((0:1:1:2:(fib 4):_) !! 2 + 3)
= fibList !! 3 + (1 + 2)
= fibList !! 3 + 3
= (0:1:1:2:3:_) !! 3 + 3
= 2 + 3
= 5

再帰的に遅延リストが呼ばれているが、このとき一度計算された要素は全てその結果で置き換えられていることがわかる (例えば15行目以降に出てくるfibListの全てについて、その第1要素はサンクではなく評価済の値 (1) となっている)。 上記の結果は、Haskellの評価戦略が遅延評価である事、およびfibListの実体がただ1つである事に拠る (メモ化せずに計算したときfib 1といった計算が大量に発生するのは、計算毎にfib 1の実体が異なっているからである)。

まとめ

上記のように簡約計算を実行してみることで、メモ化の構造(特に遅延データ構造)がどのようにしてメモ化しているのかが理解できる。 また、実際に使うときにどのように値がストアされていくのかを知っておくと、安心して使えそうである。

なお、競技プログラミングでは、こういうメモ化するためのデータ構造には配列(Array)が有力なようで、そのルックアップの計算量はO(1)である。 他方今回記載したメモ化用のデータ構造はMap/リスト/2分木だが、それぞれルックアップに必要な計算量がO(\log n)/O(n)/O(\log n)であり圧倒的に遅い。 配列を使用することを前提にした制限時間になっている以上、上記で検討したメモ化は採用できない。 また、遅延データ構造では問題にならないが、遅延しないデータ構造を使用する場合、 immutableなデータ構造(例えばIArray)だと新しい辞書を返すたびに辞書の再構築が必要となり、こちらもコストが大きい。 そのため代わりに、他の手続き型言語と同様、mutableな配列(MArray / MVector)を使ってメモ化する必要がある。

参考