Elm(とHaskell)でシーザー暗号
Tags: haskell, elm
Published: 2020-03-26 00:12:34

## なぜシーザー暗号

[プログラミングHaskell 第2版](https://www.lambdanote.com/collections/haskell)を読んでたらシーザー暗号が出てきて、
昔々某社の中途採用試験のオンラインテストで全然できなかったのが思い出されたのでそのリベンジです。

## シーザー暗号とは

[Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%BC%E3%82%B6%E3%83%BC%E6%9A%97%E5%8F%B7)読んでください。

> シーザー暗号は単一換字式暗号の一種で、平文の各文字を、辞書順に3文字分シフトして暗号文を作る暗号である[4]。古代ローマの軍事的指導者ガイウス・ユリウス・カエサル(英語読みでシーザー)が使用したことから、この名称がついた[3]。文字のシフト数は固定であるが、3に限る必要はない。例えば左に3文字分シフトさせる場合、「D」は「A」に置き換わり、同様に「E」は「B」に置換される。

## Haskellで書いてみる

Haskellの実装は [プログラミングHaskell 第2版](https://www.lambdanote.com/collections/haskell) を引用させていただきました。 :bow:

### 暗号化と復号

小文字を 0 から 25 の整数に変換する関数 let2int と、その逆関数 int2let を定義します。

```haskell
let2int :: Char -> Int
let2int c = ord c - ord 'a'
int2let :: Int -> Char
int2let n = chr (ord 'a' + n)
```

この二つの関数を使うと、小文字をシフト数だけずらす関数 shift が定義できます。

```haskell
shift :: Int -> Char -> Char
shift n c | isLower c = int2let ((let2int c + n) `mod` 26)
          | otherwise = c
```

関数 shift を使えば、与えられたシフト数で文字列を暗号化する関数が定義できます。

```haskell
encode :: Int -> String -> String
encode n xs = [shift n x | x <- xs]
```

> encode 3 "haskell is fun"
"kdvnhoo lv ixq"
> encode (-3) "kdvnhoo lv ixq"
"haskell is fun"

### 文字の出現頻度表

26 文字の出現頻度表を定義します。

```haskell
table :: [Float]
table = [8.1, 1.5, 2.8, 4.2, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.0, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1]
```

百分率を計算して浮動小数点数として返す関数を定義します。

```haskell
percent :: Int -> Int -> Float
percent n m = (fromIntegral n / fromIntegral m) * 100
```

lowers および関数 count は、それぞれ小文字あるいは指定した文字の個数を数える関数です。

```haskell
lowers :: String -> Int
lowers xs = length [x | x <- xs, x >= 'a' && x <= 'z']

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']
```

任意の文字列に対して文字の出現頻度表を返す関数が定義できます。

```haskell
freqs :: String -> [Float]
freqs xs = [percent (count x xs) n | x <- ['a'..'z']]
  where n = lowers xs
```

> freqs "abbcccddddeeeee"
[6.666667, 13.333334, 20.0, 26.666668, ..., 0.0]

### 暗号解読

カイ二乗検定を使う。「計算された値が小さければ小さいほど二つのリストはよく似ている」ということらしい。

```haskell
chisqr :: [Float] -> [Float] -> Float
chisqr os es = sum [((o-e)^2)/e | (o,e) <- zip os es]
```

リストの要素を n だけ左に回転させる関数を定義します。

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

目的とする値がリストのどの位置にあるかを調べて、その位置すべてをリストとして返す関数を定義します。

```haskell
positions :: Eq a => a -> [a] -> [Int]
positions x xs = [i | (x',i) <- zip xs [0..], x == x']
```

暗号文に対する文字の出現頻度表を作り、その表を左に回転させながら、期待される文字の出現頻度表に対するカイ二乗検定の値を計算します。そして、算出されたカイ二乗検定の値のリストの中で最小の値の位置をシフト数とします。

```haskell
crack :: String -> String
crack xs = encode (-factor) xs
  where
    factor = head (positions (minimum chitab) chitab)
    chitab = [chisqr (rotate n table') table | n <- [0..25]]
    table' = freqs xs
```

> crack "kdvnhoo lv ixq"
"haskell is fun"
> crack "vscd mywzboroxcsyxc kbo ecopev"
"list comprehensions are useful""

## Elmで書いてみる

```elm
let2int : Char -> Int
let2int c =
    Char.toCode c - Char.toCode 'a'
```

- ほぼHaskellですね。

```elm
int2let : Int -> Char
int2let n =
    Char.fromCode <| Char.toCode 'a' + n
```

- Elmにはパイプライン演算子 ( `<|` ) があります。`()` のネストが深くならないので便利ですね。

```elm
shift : Int -> Char -> Char
shift n c =
    if Char.isLower c then
        int2let <| modBy 26 <| let2int c + n

    else
        c
```

- Haskellは``` `` ```で関数を中置演算子にできるので便利ですね。Elmは愚直に書きましょう。これがElmの良さ。
- これを書いてるときに気づいたんですが、パイプって難しいですね。右にも左にも流せるので、どういう時にどっち向きに書くのかルールを決めておかないと大変なことになりそうです。  
（このパイプの向き問題だけで、もうひとつアドベントカレンダーが書けそうな気がするので気力があれば...）
- modByの引数を勘違いしてハマりました。`n % 2` は `modBy 2 n` です、感覚的には`modBy n 2`なのに何でだよ！とSlackに書いたら、カリー化できるからと教えてもらいました。膝を打ちすぎて膝が壊れるかと思いました。
- Haskellのガード式は雰囲気的にパターンマッチかなと思いパターンマッチで書いたら、同僚にBooleanを返すんだからifで書けと言われました。  
（`if(true == true) true` みたいで面白かったのに...）

```elm
encode : Int -> String -> String
encode n xs =
    String.fromList <| List.map (shift n) <| String.toList xs
```

- ElmのStringはCharの配列ではないので変換しましょう。
- Haskellは`[]`でmapが書けるので便利ですね。Elmは愚直に書きましょう。これがElmの良さ。

```elm
table : List Float
table =
    [ 8.1, 1.5, 2.8, 4.2, 12.7, 2.2, 2.0, 6.1, 7.0, 0.2, 0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0, 6.3, 9.0, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1 ]
```

- ほぼHaskell(ry

```elm
percent : Int -> Int -> Float
percent n m =
    toFloat n / toFloat m * 100
```

- ほぼ(ry

```elm
lowers : String -> Int
lowers xs =
    List.length <| List.filter (\n -> n >= 'a' && n <= 'z') <| String.toList xs
```

- Haskellは`[]`でfilterMapと同じことができるので便利ですね。Elmは愚直に書きましょう。これがElmの良さ。  
（Haskellのほうが書いてて気持ちよかったのは内緒）

```elm
count : Char -> String -> Int
count c xs =
    String.length <| String.filter ((==) c) xs
```

- ElmはStringにfilterがあって便利ですね。


```elm
lowerAlphabets : List Char
lowerAlphabets =
    List.map (\n -> Char.fromCode n) <| List.range (Char.toCode 'a') (Char.toCode 'z')


freqs : String -> List Float
freqs xs =
    let
        n =
            lowers xs
    in
    List.map (\x -> percent (count x xs) n) lowerAlphabets
```

- `List.range` は、Intしか取らないので `Char.toCode` するか、 "abcdefghijklmnopqrstuvwxyz" を定義しましょう。

```elm
chisqr : List Float -> List Float -> Float
chisqr os es =
    List.sum <| List.map2 (\o e -> ((o - e) ^ 2) / e) os es
```

- Elmにはzipが無いので、２つの配列をタプルにしたければ `List.map2 Tuple.pair os es` とします。ただし、今回の場合はタプルを作る必要はありません。

```elm
rotate : Int -> List a -> List a
rotate n xs =
    List.drop n xs ++ List.take n xs
```

- (ry

```elm
positions : a -> List a -> List Int
positions y xs =
    List.filterMap
        (\( i, x ) ->
            if y == x then
                Just i

            else
                Nothing
        )
    <|
        List.indexedMap Tuple.pair xs
```

- Elmは全ての型が比較可能なので、 `Eq` は不要です。
- Elmの `indexedMap` 便利ですね。
- Elmに無限配列はないらしい。
- `filterMap` は、Maybeを受け取りNothingを除外します。

```elm
crack : String -> String
crack xs =
    let
        factor =
            List.head <| positions (Maybe.withDefault 0.0 <| List.minimum chitab) chitab

        chitab =
            List.map (\n -> chisqr (rotate n table2) table) <| List.range 0 25

        table2 =
            freqs xs
    in
    encode -(Maybe.withDefault 0 factor) xs
```

- `List.minimum` と `List.head` はListが空だった場合、Nothingを返すため戻り値の型はMaybeです。  
Haskellは例外が起きます。Elmのこういうところとても良いですね。

## 感想

- 新しい言語を学ぶというのはいいですね。
- Elmは言語仕様がシンプルなので、公式ドキュメントを読めばなんとなくどうやれば実現できるのかわかるのが非常に良いですね。
- 普段はScalaを書いてるので、HaskellとElmは難しいなと思いました。  
関数を書く時って、関数の名前と、引数と戻り値の型を決めてから実装を書き始めると思うんですが（私はそう）、
そうすると、ちょっと難しいことをやろうとするとコンパイルが通らない時間が長くてちょっと疲れちゃいます。  
Scalaなら`???`でいいし、何なら手続きしまくって取り敢えず動かすができちゃうので楽（？逃げ？）ができて好きです。
  - 同僚に `Debug.todo` があると教えてくれた。Elmがまた好きになりました。

## おまけ

せっかくElmで書いたので、[HTML](https://dyoshimitsu.github.io/elm-caesar-cipher/)にしました。