アルファベットの繰り上がり

haskell

(http://d.hatena.ne.jp/ha-tan/20070715/1184447837 経由)
書いてみた。「どう書くorg(http://ja.doukaku.org/)」も気になっていたのでついでに初投稿。

お題はこれ

Excelの桁表示は 1桁目はA、2桁目はB、以下C、D、 E…とすすみ、Zの次はAA AB AC…と続きます。AZの次はBAです。

この表記法で1から100までを表示してください。出力結果は下記のサンプルの「...」の部分に適切な文字列を埋めたものになります。

A, B, C, ... CU, CV

http://ja.doukaku.org/21/

ソース

module Main(main) where
import List(intersperse)
alpha_index = base ++ [ e ++ s |e<-alpha_index,s <- base]
    where base = [[c]|c<-['A'..'Z']]
main = (putStrLn . concat . intersperse ", ") (take 100 alpha_index)

出力

$ ./main.exe
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, AA
, AB, AC, AD, AE, AF, AG, AH, AI, AJ, AK, AL, AM, AN, AO, AP, AQ, AR, AS, AT, AU
, AV, AW, AX, AY, AZ, BA, BB, BC, BD, BE, BF, BG, BH, BI, BJ, BK, BL, BM, BN, BO
, BP, BQ, BR, BS, BT, BU, BV, BW, BX, BY, BZ, CA, CB, CC, CD, CE, CF, CG, CH, CI
, CJ, CK, CL, CM, CN, CO, CP, CQ, CR, CS, CT, CU, CV

3桁以上もいけるように作ったつもり。alpha_indexの繰り上がり部分を抜きだすとこう。

*Main> take 20 $ drop (26 +  26 * 26 - 10) alpha_index
["ZQ","ZR","ZS","ZT","ZU","ZV","ZW","ZX","ZY","ZZ","AAA","AAB","AAC","AAD","AAE","AAF","AAG","AAH","AAI","AAJ"]

コンマを挟む処理はList.intersperseとconcatを使うのがすっきりすると思います。

ついでにStateモナド版 (もなもなもなど番外編)

(runStateとevalStateを思いっきり勘違いしていたので書き直しました)

最近、ようやくStateモナドの使い方がわかってきたので、Stateモナドでも書いてみた。

module Main(main) where
import List(intersperse)
import Control.Monad.State

alpha_index2 = (evalState (sequence (repeat next_state)) "")

next_state :: State String String
next_state = modify next_str >> get

next_str :: String -> String    
next_str "" = "A"
next_str str = case (last str) of
                 'Z' -> next_str heads ++ ['A']
                 c -> heads ++ [succ c]
    where heads = take (length str - 1) str

main = (putStrLn . concat . intersperse ", ") (take 100 alpha_index2)

全体的には、1ステップずつの文字列の変換を定義して、それをStateモナドにして、繋いで、evalStateで1ステップごとの出力のリストを取得しておわり。
1ステップずつの文字列の変換はnext_str。例えば、next_str "A"は"B"になるし、next_str "ZZ"は"AAA"になる。整合性とるために""の次を"A"にしてある。
文字列を状態と見て、next_strをStateモナドで簡単にラップしたのがnext_state。ちなみにmodifyとgetがState関係*1の関数で、modifyは渡した関数で状態を更新し、getは状態を取得する。ここでは状態を更新してから、そのまま出力している。
状態遷移の1ステップであるnext_stateを無限回繰り返してつないでいるのが(sequence (repeat next_state))。こうやって繋ぐと、繋いたStateモナドの状態遷移を連続で行い、各ステップの出力のリストを出力とするStateモナドが得られる。
evalStateをStateモナドにかますと、出力が返ってくる。さっきも書いたようにこのStateモナドの出力は各ステップの出力のリストになっているので、それがそのまま求めるものになる。ちなみに、evalStateじゃなくてexecStateを使うと状態が返ってくるし、runStateを使うと(出力,最終状態)というタプルが返ってくる。状態も取得したい時はこっち使うんだろな。



Stateモナドはものすごく強力で使いこなす価値は十分にあるので、使ってない方はちょっといじってみることをお勧めします。各要素さえちゃんと定義できていれば、それをどう組みあわせてもちゃんと動いてくれるのは素晴しく気持ちがいい。モナドの気持ちよさ、ってこういうことなのかな。

*1:正確にはMonadState