文字列置換

最新のghcには文字列置換の関数(subRegex)があるのだけれど、オイラのghc6.2.2には入ってないっていうんで、まぁ仕方なしとばかりに置換関数を自作。

import Text.Regex

replaceStr mtcStr newStr srcStr =
    case matchRegexAll mtcStr srcStr of
    Just (bfrStr, _, aftStr, _) -> (bfrStr
                                    ++ newStr
                                    ++ replaceStr mtcStr newStr aftStr)
    _ -> srcStr

説明)
mtcStrに置換対象文字列、
newStrに置換するときにおく文字列、
srcStrに置換を行う文字列。


使用例)
srcStr = "AAA###BBB###DDD@@@FFF#43###@4stp####@@@@#fa09ujf"

main = do
  putStrLn srcStr
  putStrLn replaced1
  putStrLn replaced2
  where
    replaced1 = replaceStr (mkRegex "###") "?" srcStr
    replaced2 = replaceStr (mkRegex "@@@") "!" replaced1

初めてのHaskell ～はつける

初めてとはいっても，一ヶ月くらい前からチョコチョコやってるんだけどね．
ようやく，つかんできた気がするし，ブログも書いてないからちょっとネタにしてみた．
（最近アニメばっかで，学生してないように思われるのは心外だしね;-) )

まずはかの有名なコードを書こう．（コンパイラはghc windowsだったらmsiでインストーラつきだし，debianとかならaptでとってこれる．間違ってもソースとってきてコンパイルしてインストールをやろうなんて考えない方が吉．)

main = putStrLn "Hello HaskellWorld!"

まぁ，「ghc -o hello hello.hs」とかしてhelloを実行すれば，かの有名なフレーズが出てくるわけさね．


さて，これはコンパイラチェックのためのコードに過ぎなくて，
今日はこの間やったICPCのプロコン国内予選の問題Bを解いてみよう．（ある講義の課題で先生自作の関数型言語のインタープリタで解くのがでているいて，まぁ言語仕様がかなり似ているし，まずはhaskellでやってみよ，というのが本音）

さて，問題を要約すると，
もともとの列車がtrain．
分かれ道で，t1, t2に分かれる．
t1，t2は反転するかもしれない．
t1とt2が再び連結して出て行く．このときt1とt2の順が入れ替わることも．

例) train = abcd
t1 = なし ，t2 = abcd  -> abcd, dcba
t1 = a, t2 = bcd -> a + bcd,  a+dcb, bcd + a, dcb + a
t1 = ab, t2 = cd -> ab + cd, ab + dc, ba + cd, ba + dc, cd + ab, ...

さて，簡単に考えるならば，
t1' <- reverse t1
t2' <- reverse t2
と考えて，
t1 と t2,  t2 と t1
t1 と t2', t2' と t1
t1' と t2, t2 と t1',
t1' と t2', t2' と t1'
の組み合わせが出来る，となる．
なんか，これじゃああんまりな気がするけれど，関数型の頭が不出来なもんで，仕方ない．
で，ペア（2つ組）のリストを作るmakeTupples関数を用意．
makeTupples :: ([Char], [Char]) -> ([Char], [Char]) -> [([Char], [Char])]
makeTupples (a1,a2) (b1,b2) =
  (a1, b1) : (a1, b2) : (a2, b1) : (a2, b2) : []

これで，あとはfstとsndを入れ替えたものも作ればいいから，
各２つ組を引数で渡して，そのまま連結したもの，入れ替えて連結したものも含むリストを返すshuffle1を用意．
shuffle1 :: ([Char], [Char]) -> [[Char]]
shuffle1 (l1, l2) = (l1 ++ l2) : (l2 ++ l1) : []

これを先ほどのmakeTupplesで作ったリストの各要素に関数適用してやればいいから，
map shuffle  (makeTupples  (t1, reverse t1) (t2, reverse t2))
これで，t1とt2に分割されたときの列車の組み合わせのリストができる．

あとは全ての分割パターンに対して↑を再帰的にやる関数を作る．

shuffleTrain :: [Char] -> [Char] -> [[Char]] -> [[Char]]

shuffleTrain _ [] trainPatterns = trainPatterns

shuffleTrain train1 train2 trainPatterns =
  shuffleTrain (head train2 : train1) (tail train2)
    (trainPatterns ++
     (concat $ map shuffle1 $ makeTupples (train1, reverse train1) (train2, reverse train2))
    )

2番目のやつは2つ目のリストが空リストだったらという再帰呼び出しの最後のために用意．
trainPatternは累積変数で，できあがっていったパターンのリストを再帰呼び出し先へ次々持っていくためのもの．

で，あとは呼び出しのところだが，
shuffleTrain "" "abcd" []
と関数適用すれば全パターンのリストができる．
この"abcd"がシャッフルしたいリスト．（文字列はCharのリストとして実装されているので，""や"abcd"は[Char]型となっている．）
だが，重複があるので，nub関数を使って重複を排除．
さらに，リストの長さが欲しいので，
length (nub (shuffleTrain "" "abcd" []))

カッコが多くてウザい．
特にケツにコッカがたまってるのは邪魔臭くなるので，後ろにコッカがきている時には，対応するカッコを$に置き換えて，後ろのコッカをなくすことができる．

length $ nub $ shuffleTrain "" "abcd" []

テストするために，
main = do
 print $ length $ nub $ shuffleTrain "" "abcd" []

さぁ，実行すると，，あぁ出来たっぽい．
あとは，入力処理のあたりをやればプロコンの問題を解くプログラムになる．
それは面倒だから，また今度にしよう．