孤独のHaskellこんな記事が目にとまり、例題("AABBCCC"を"A2B2C3"にする関数を書こう)がおもしろそうだったので、自分なりに実装を考えてみた。
元記事では、トップダウンアプローチを採っているが、僕はそもそも解法を考えてから、実装する方法を採ってみた。
戦略を練る
ルールがよく分からないので、例題の一文を見て、連続する文字(A-Zの範囲と勝手に限定)を数字に置き換えれば良いとする。その時に、直感的に以下のことを考えた。
- 連続するので、きっと(A,A)(A,B)と隣り合う二つの文字が大事だろう
- AAA->A3なので畳み込みである。この問題は何としてもfoldで解く(?)
すると、こんな図が頭に浮かぶ
(A,A) (A,B) (B,B) (B,C) (C,C) (C,C)
隣り合う数字をfoldで畳めば答えが出そうだ。
(A,A) -> 2A (A,B) -> B2A (B,B) -> 2B2A (B,C) -> C2B2A (C,C) -> 2C2B2A (C,C) -> 3C2B2A
こんな感じに畳み込まれるのが理想。
ここで問題は、
- 最初の処理で、ABが来たときどうするの?
- いいけど、文字列が逆!
先の問題は、A,"AABBCCC"と、文字列の最初の文字を初期値にしてしまえば解決しそう。後の問題は、reverseで解決(ながーい文字列の事は考えない!)。
実装
戦略が練れたので、実装しよう。
まず、(A,A),(A,B)だが、最初String ->[(a,a)]な関数を考えたが、30分ほど考えているうちに、tailsで良いことに気づく。tailsは教本によくでてくるあれだ。
元の記事で、hoogleの使い方がやさしく説明してあって、hoogleってすごい!と思ったが、残念ながら、ネット環境が無かったので自前で実装する(ぉ。
tails :: String -> [String] tails [] = [] tails (x:[]) = [[x]] tails (x:xs) = (x:xs) : tails xs
こんな感じ?
次に、真ん中飛ばして一番上を書く。reverseとtails、foldを予定どおりに組み合わせる。
rle :: String -> String rle (x:xs) = reverse $ foldl f [x] $ tails (x:xs)
fはfでいいのか?いいのだ!
fを実装する。戦略を練っている段階では、細かいことは考えていなかったので、実装しながら細部を考えた(ぉぃ
f :: String -> String -> String f (xs) (y:[]) = xs f (x:xs) (y1:y2:ys) = if y1 == y2 then if isDigit x then (show (1 + (read (x:""))::Int)) ++ xs else '2' : x : xs else y2 : x : xs
showとreadが組み合わさってるところがみっともないが、何とか組めた。(`・ω・´)
isDigitも絶対既にあると思うけど、自分で実装。
isDigit :: Char -> Bool isDigit x = '0' < x && x < '9'
ということで、実装は30分程度。東神奈川から大井町ぐらいの間に完成。
考えてる時間の方が長くて、朝元記事読んでから、戦略を練り終わるまで、7時間ぐらい。仕事しながら考えて、会議中に実装草案を起こす(ぉ
全体は何となくGistに。
衝撃の結末
実は、これ致命的なバグがあります。
*Main> rle "ABBBBBBBBBBBBBBBBBBBBBBB" "AB997"
_, ,_
(;゜д゜)
なんと、数字が2桁以上になると動きません。
戦略を変更することなく、このバグに対処するためにはデータ型を定義する必要がありそうです。
data Node = A Char | N Int deriving Show
こんな感じでしょうか。
このデータ型を剥いたり被せたりすれば、うまく行きそうですが、それはまた別のお話し・・・(ぉ