セカイノカタチ

世界のカタチを探求するブログ。関数型言語に興味があり、HaskellやScalaを勉強中。最近はカメラの話題も多め

マーブルワーズ

孤独のHaskellを読んで

孤独の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

こんな感じでしょうか。
このデータ型を剥いたり被せたりすれば、うまく行きそうですが、それはまた別のお話し・・・(ぉ