Haskell / トップダウン or ボトムアップ

関数プログラミングの本がでるようです。とりあえずAmazonで予約注文しています。

関数プログラミング実践入門という本を書きました - ぼくのぬまち 出張版

日本語のHaskell本（Haskellを題材にした関数プログラミングを含め）が徐々に増えてきて、にわかHaskellerにとっても大変嬉しいですね。

本題

著者のブログに、RLE（Run Length Encoding）を題材に、トップダウンで書いていく道のりが丁寧に記述された記事があったので、トップダウンの実装について思ったことを書きます。

こちらの記事です。RELの内容もこちらを御覧ください。

孤独のHaskell - ぼくのぬまち 出張版

やっぱりトップダウンですよね

僕も、なるべくHaskellでは「抽象的に、トップダウンに」書いていこうと気をつけています。 試しにRLEを書いてみたところ、似たような道のりをたどって、こんな感じになりました。

rle :: String -> String
rle = concatMap encode . group where
  encode cs = head cs : show (length cs)

でもボトムアップになっちゃうこともあるよね

RLD関数

RLEはトップダウンで書けました。では、その逆の操作は？

つまり、RLEされた「A2B2C3」といった文字列から、「AABBCCC」という元の文字列に復号する関数です。 Run Length Decoding、RLDと名づけます。

トップダウンのアプローチ

これをトップダウンで書いてみます。

「A2B2C3」といった文字列は、「文字、連続回数、文字、連続回数、文字、連続回数..」といった構造になっています。これを、一連の文字列になおすわけですね。

中間構造としては「（文字、連続回数）, （文字、連続回数）, （文字、連続回数）..」がよいでしょうか。 RLD関数の基本構造は、「文字列」→「（文字、連続回数）のリスト」→「文字列」となります。

コードで示します。

rld :: String -> String
rld = fromIntermediate . toIntermediate where
  fromIntermediate :: [(Char, Int)] -> String
  fromIntermediate = undefined
  toIntermediate :: String -> [(Char, Int)]
  toIntermediate = undefined

さて、fromIntermediateの実装は自明のためよいとして、toIntermediateはどう実装すればよいでしょうか。

1. Parsecを使う
2. 正規表現を使う
3. 地道に実装（文字列の頭から「文字、連続回数」の組を取り出して、残りを再帰で同様に処理する）

選択肢はこのあたりかと思います。この程度の単純なパースであれば、（LLなら迷わず正規表現ですが）3.の地道な実装で十分事足ります。

ここで、とても嫌な予感がします。

ともあれ、実装してみます。

rld :: String -> String
rld = fromIntermediate . toIntermediate where
  fromIntermediate :: [(Char, Int)] -> String
  fromIntermediate = concatMap (\(c,n) -> replicate n c)
  toIntermediate :: String -> [(Char, Int)]
  toIntermediate [] = []
  toIntermediate (c:cs) = let n = takeWhile isNumber cs
                              rest = dropWhile isNumber cs
                          in  (c, read n) : toIntermediate rest

RLDが出来上がりました。やったー！

簡単には簡単にならない

さてと、ひと通り出来上がったところで、このRLD実装を簡単にしてみようと思います。

fromIntermediateにいなくなってもらうのは、非常に簡単です。置換するだけなので。

rld :: String -> String
rld = concatMap (\(c,n) -> replicate n c) . toIntermediate where
  toIntermediate :: String -> [(Char, Int)]
  toIntermediate [] = []
  toIntermediate (c:cs) = let n = takeWhile isNumber cs
                              rest = dropWhile isNumber cs
                          in  (c, read n) : toIntermediate rest

次に、toIntermediateにもいなくなってもらいたいですね。 でも..どうやって？

toIntermediateは再帰関数です。この関数には、toIntermediateという名前が付いているため、関数内で再帰呼び出しができます。 toIntermediateをRLDに組み込んでしまうと、関数に名前が付かないのでtoIntermediateの実装を呼び出すことができません。

toIntermediateを消すの簡単には行かず、RLD自体を再帰呼び出し関数に作り替えてやる必要があります。 でも、それって「（文字、連続回数）, （文字、連続回数）, （文字、連続回数）..」という中間構造を作るという方針から外れるということです。

嫌な予感がした時点でボトムアップに

嫌な予感がした時点でボトムアップに方針転換すると問題は非常に簡単に解けます。

1. 文字列を受け取ったら、最初の「文字、連続回数」のペアとその後に分ける
2. 「文字、連続回数」のペアを、文字列に直す
3. 残りの文字列も同様に処理する

こういう処理の流れで書く、ボトムアップな方針です。

コードで示します。

rld :: String -> String
rld [] = []
rld (c:cs) = let n = read $ takeWhile isNumber cs
                 rest = dropWhile isNumber cs
             in  replicate n c ++ rld rest

あるいは、spanを使って

rld :: String -> String
rld [] = []
rld (c:cs) = let (n,rest) = span isNumber cs
             in  replicate (read n) c ++ rld rest

トップダウンで回り道をするよりも、早く短くシンプルに書けてしまいました。アイヤー。

最終的なコード

参考までにテストコードも含めて置いておきます。

gist1ef0c725af9cf8fcad8a

トップダウン or ボトムアップ

「基本的にトップダウンで、あとはまあ臨機応変に」っていうありきたりな結論が導かれそうなのですが、その臨機応変が難しいですわホンマ。