シーザー暗号を作ってみた

古代ローマのシーザーが使っていた暗号を「シーザー暗号」という。どんなものかというと、アルファベットを後ろに三つ巡回置換した文字で文章を書くのだ。詳しい説明はWikipediaの「シーザー暗号」にある。

まず、アルファベットを巡回置換するので、文字列 xs の文字を n 文字だけ後ろへずらす巡回置換をする関数 rotate を作る。

rotate n xs = drop n xs ++ take n xs

実行してみると次のようになる。

Main> rotate 3 ['a'..'z']
"defghijklmnopqrstuvwxyzabc"

つぎにこの置換した文字列と元の文字列を対応させた暗号テーブルを作る。

encode_tbl = zip ['a'..'z'] (rotate 3 ['a'..'z'])

encode_tbl の中身は次のようになる。

Main> encode_tbl
[('a','d'),('b','e'),('c','f'),('d','g'),('e','h'),('f','i'),('g','j'),('h','k'),('i','l'),('j','m'),('k','n'),('l','o'),('m','p'),('n','q'),('o','r'),('p','s'),('q','t'),('r','u'),('s','v'),('t','w'),('u','x'),('v','y'),('w','z'),('x','a'),('y','b'),('z','c')]

デコード用のテーブルは、タプルの第1項と第2項を入れ替えて作る。

decode_tbl = [(y, x)| (x, y) <- encode_tbl]

これも見てみよう。

Main> decode_tbl
[('d','a'),('e','b'),('f','c'),('g','d'),('h','e'),('i','f'),('j','g'),('k','h'),('l','i'),('m','j'),('n','k'),('o','l'),('p','m'),('q','n'),('r','o'),('s','p'),('t','q'),('u','r'),('v','s'),('w','t'),('x','u'),('y','v'),('z','w'),('a','x'),('b','y'),('c','z')]

暗号テーブルを利用して1文字を暗号化する関数 coder をつくる。暗号テーブルのようなタプルの配列の検索は lookup 関数で行える。lookup 関数の戻値は Maype モナドで、対応する値が見つかったときは、Just a を返し、見つからなかったときは Nothing を返す。したがって検索した値 a を取り出すためには、Just x として、パターンから取り出さなければならない。

言葉で説明すると面倒になるから、coder を作って使ってみるとその意味が分かる。Maybe 型を使うときのお決まりの方法だ。

corder xs c = let Just d = lookup c xs
          in d

早速使ってみよう、

Main> coder [('a','d'), ('b', 'e'), ('c', 'f')] 'a'
'd'

あとは、この coder と暗号テーブルを使って文字列を map すれば暗号が出来上がる、暗号テーブルに encode_tbl を使うと文字列が暗号化され、decode_tbl を使うと暗号が復号化される。暗号化する関数 encode と、復号化する関数 decode の定義は次のようになる。

encode xs = map (corder encode_tbl) xs

decode xs = map (corder decode_tbl) xs

関数の型宣言まで含めた完全なプログラムは次のようになる。

rotate :: Int -> [a] -> [a]
rotate n xs = drop n xs ++ take n xs

encode_tbl :: [(Char, Char)]
encode_tbl = zip ['a'..'z'] (rotate 3 ['a'..'z'])

decode_tbl :: [(Char, Char)]
decode_tbl = [(y, x)| (x, y) <- encode_tbl]

coder :: [(Char, Char)] -> Char -> Char
coder xs c = let Just d = lookup c xs
          in d

encode :: [Char] -> [Char]
encode xs = map (coder encode_tbl) xs

decode :: [Char] -> [Char]
decode xs = map (coder decode_tbl) xs

これをファイルに作成して Hugs のコマンドラインから実行したのが次の例だ。

Main> encode "hello"
"khoor"
Main> decode "khoor"
"hello"

関数型のプログラミングのいいところは、個々の関数をテストしながらインタラクティブにプログラムを作成していけることだ。部分プログラム -> テスト -> 部分プログラムのデバッグ のサイクルは負担にならない。慣れてくると関数でプログラミングするのが楽しくなってくる。
[PR]
by tnomura9 | 2011-06-08 18:11 | Haskell | Comments(0)
<< ピンクレディー ピタゴラス数の作り方 >>