概要
腕試しにHaskellでROT13を実装してみた。
(GoとRustは以前に書いたものでこの記事としてはおまけです)
次の点を意識しています。
- 論理的に理解しやすいことが優先で、処理をまとめすぎない
- 数学的な思考を優先する (
$を使って写像の合成を意識するぐらいですが)
指針
大まかに次の指針がある。
- ローテーションの境界で場合分けする
a-m, n-z, A-M, N-Z で場合分けする(modは使わない) - mod を使う
a-z, A-Z で場合分けし、ローテーションはmodを使って計算する - ROT13 の変換テーブルを用意する
今回は、1つ目のが多分一番理解しやすく、2つ目が自然な定式化で簡潔、3つ目がHaskell心をくすぐる書き方ができる…といった感じです。
解1: ローテーションの境界で場合分けする
a-m/n-z と A-M/N-Z で符号が変わるという知識をもとに実装する。
a-m, A-M の場合は 13 後ろにずらす。n-z, N-Z は前にずらす。
import Data.Char (chr, ord)
decodeRot13 :: String -> String
decodeRot13 s = map rot13Char s
where
rot13Char c | 'a' <= c && c <= 'm' = chr $ (+ 13 ) $ ord c
rot13Char c | 'n' <= c && c <= 'z' = chr $ (+ (-13)) $ ord c
rot13Char c | 'A' <= c && c <= 'M' = chr $ (+ 13 ) $ ord c
rot13Char c | 'N' <= c && c <= 'Z' = chr $ (+ (-13)) $ ord c
rot13Char c = c
main :: IO ()
main = do
putStrLn $ show ((decodeRot13 "") == "")
putStrLn $ show ((decodeRot13 "Lbh penpxrq gur pbqr!") == "You cracked the code!")
Rosetta Code を見るに、「+」と「-」は条件で呼び分けられるようですね。
bool 関数を使って、第三引数が True/False によって (ord x) (+) 13 や (ord x) (-) 13 のようにできるみたいです。
Rozetta Codeのコードはこれで場合分けをなくしていますが、理解しやすいかは人によるでしょう。
> import Data.Char (ord)
> import Data.Bool (bool)
> bool (-) (+) ('c' <= 'm') (ord 'c') 13
112
> bool (-) (+) ('p' <= 'm') (ord 'p') 13
99
解2: mod を使う
次の計算をしている。
- a..z または A..Z を 0..26 に対応付ける
例: 'a'→ 0, 'b'→ 1, ..., 'z'→ 25 または 'A'→ 0, 'B'→ 1, ..., 'Z'→ 25 - 13を足す (0..25 を 13..38 に対応付ける)
例: 0→13, 1 → 14, ..., 25 → 38 -
mod26 を適用する
例: 13 → 13,...,26 → 0, ..., 38 → 12 - 0～25 の数値を a..z または A..Z に戻す
分かりにくいですけど Char → Int → Char が f-1 • gh • f みたいな形をしていますよね。
import Data.Char (chr, isLower, isUpper, ord)
decodeRot13 :: String -> String
decodeRot13 s = map rot13Char s
where
rot13Char c | isLower c = chr . (+ (ord 'a')) $ (`mod` 26) $ (+ 13) $ (+ (- ord 'a')) . ord $ c
rot13Char c | isUpper c = chr . (+ (ord 'A')) $ (`mod` 26) $ (+ 13) $ (+ (- ord 'A')) . ord $ c
-- ^^^^^^^^(4)^^^^^^^^ ^^^^(3)^^^ ^^(2)^^ ^^^^^^^^^(1)^^^^^^^^^
rot13Char c = c
main :: IO ()
main = do
putStrLn $ show ((decodeRot13 "") == "")
putStrLn $ show ((decodeRot13 "Lbh penpxrq gur pbqr!") == "You cracked the code!")
ちなみに素朴に数値計算を $ を使わずに書くとこうなる。カッコが多くて分かりにくい。
Haskell 以外の言語だと大抵はこれと似通った書き方になるので、こっちの方が分かりやすい人もいると思う。
decodeRot13 :: String -> String
decodeRot13 s = map rot13Char s
where
rot13Char c | isLower c = chr $ (ord 'a') + (((ord c) - (ord 'a') + 13) `mod` 26)
rot13Char c | isUpper c = chr $ (ord 'A') + (((ord c) - (ord 'A') + 13) `mod` 26)
rot13Char c = c
解3: ROT13 の変換テーブルを用意する
実装のポイントは次の通り。
- ローテーションを行う
- drop/take でローテーションした配列を生成できる
- テーブルを作る
- zip で ['a'..'z'] と ['n'..'z''a'...'m'] のペアを作る
- テーブルを検索する
- 0..25 でインデックスで辞書引きできるので
!!を使っている(O(1)のオーダー)
- 0..25 でインデックスで辞書引きできるので
import Data.Char (isLower, isUpper)
decodeRot13 :: String -> String
decodeRot13 s = map rot13Char s
where
makePairsRot13 cl = zip cl ((drop 13 cl) ++ (take 13 cl))
lowerPairs = makePairsRot13 ['a'..'z'] -- [('a','n'),('b','o'), ...,('z','m')]
upperPairs = makePairsRot13 ['A'..'Z'] -- [('A','N'),('B','O'), ...,('Z','M')]
rot13Char c = case c of
ch | isLower ch -> snd $ lowerPairs !! (fromEnum ch - fromEnum 'a')
ch | isUpper ch -> snd $ upperPairs !! (fromEnum ch - fromEnum 'A')
ch -> ch
main :: IO ()
main = do
putStrLn $ show ((decodeRot13 "") == "")
putStrLn $ show ((decodeRot13 "Lbh penpxrq gur pbqr!") == "You cracked the code!")
おまけ: 他の言語の実装例
例1: Go
Goのチュートリアルそのままです。
GoのチュートリアルのROT13の練習問題はRead の使い方を理解することが主な目的であったのです。
Haskell と大きな違いはやはり、固定長バッファを確保しているところでしょう。
ハードウェア的にはページサイズに収まる範囲での読み込みは一般的には効率的に行えるので、性能面でも予測可能な動きをしてくれると思います。
package main
import (
"io"
"os"
"strings"
)
type rot13Reader struct {
r io.Reader
}
func (rot13 *rot13Reader) Read(b []byte) (n int, err error) {
c := make([]byte, 32)
n, err = rot13.r.Read(c)
for i:=0; i<n; i++ {
if 'a' <= c[i] && c[i] <= 'z' {
b[i] = 'a' + (c[i] - 'a' + 13) % 26
} else if 'A' <= c[i] && c[i] <= 'Z' {
b[i] = 'A' + (c[i] - 'A' + 13) % 26
} else {
b[i] = c[i]
}
}
return
}
func main() {
s := strings.NewReader("Lbh penpxrq gur pbqr!")
r := rot13Reader{s}
io.Copy(os.Stdout, &r)
}
例2: Rust
Go言語のコードを作った後にRustに移植したものです。
Haskell と比較して簡潔であり、可読性はなかなかかな…と思います。ポイントは次の点です。
- 結局、Goの実装であった固定長バッファを使うのをやめた
- 本質的でない処理が湧いてくる (配列の初期化、固定長データ中の有効データ長の管理など)
- 最終的にイテレータの map で変換を施して collect() で文字列に戻した
- ロジック的には map を使っており、Goのコード寄りはHaskell のコードの構造に近いですね
- 今回は入力がASCIIコードのみなので as_bytes() を使用。Unicodeも入力にまざるなら chars() のほうがいいはず
Haskell だと ord 'a' となっていることろが、Rustだと b'a' のように短くかけるとか、ほか範囲指定が簡潔にかけるのはいいですね。
fn rot13_decoder(s: &str) -> String {
s.as_bytes().iter().map(
|&c| match c {
b'a' ..= b'z' => b'a' + (c - b'a' + 13) % 26,
b'A' ..= b'Z' => b'A' + (c - b'A' + 13) % 26,
_ => c
} as char
).collect::<String>()
}
fn main() {
println!("{}", rot13_decoder("Lbh penpxrq gur pbqr!"));
assert_eq!(rot13_decoder("Lbh penpxrq gur pbqr!"), "You cracked the code!");
}