Elmで言語処理100本ノックをやる！

# はじめに
Advent Calendar初挑戦です、頑張ります。

Elmって本当にいい言語、フレームワークですよね。 書いていて楽しいし、The Elm Architectureは堅牢でシンプルだし、データがイミュータブルだったり、副作用が強制的に分離させられるのでトラブルが起きづらい、それで学習コストは比較的低い(と言われています。 )・・・

Elmは基本的にWebフロントエンドに特化した言語で、それゆえ多くの記事は「Elmを使っていかにしてWebアプリケーションを作成するか」に主眼が置かれています。 しかしここではあえて、ElmをWebから切り離し、そのプログラミング言語としての側面にスポットを当ててみようと思います。 すでに色々な言語で挑戦されている「言語処理100本ノック」をElmで実装してみたいとおもいます。

それらしい大義名分を掲げてみましたが、単にネタが思いつかなかっただけです。

ソースは以下に置いています。

https://github.com/IamKeck/lang_processing_knock_elm

# 本記事について
上記の通り、言語処理100本ノックをElmで実装します。 
基本的には各問題の答えとなる文字列や関数を記事に示して、簡単に解説します。
Elm未経験者にとってはElmの雰囲気がなんとなくわかるのではないでしょうか。
Elm経験者にとっては・・・この記事から学ぶことは特にないと思うので、ツッコミなどしていただければ幸いです。
やってから気づきましたが一つの記事にするとやたら長くなってしまうので、ひとまず第1章だけやります。
第3章までは(Portなしに)Elmでもできるはずですが、第2章以降はまあ余力があればやります・・・

# 第1章
## 00
> 文字列"stressed"の文字を逆に（末尾から先頭に向かって）並べた文字列を得よ．


```elm
oneZero : String
oneZero =
    String.reverse "stressed"
```

説明不要

## 01
> 「パタトクカシーー」という文字列の1,3,5,7文字目を取り出して連結した文字列を得よ

```elm
oneOne : String
oneOne =
    let
        base =
            "パタトクカシーー"

        toIndexedList =
            String.toList >> List.indexedMap Tuple.pair

        firstIsEven =
            Tuple.first >> modBy 2 >> (\n -> n == 0)

        toNormalString =
            List.map Tuple.second >> String.fromList
    in
    base |> toIndexedList |> List.filter firstIsEven |> toNormalString
```

ちょっと長くなってしまいました。
一旦Charのリストにして、List.indexedMapを使い、

```elm
[(0, 'パ'), (1, 'タ'), (2, 'ト')] --　以後続く
```
のようなリストを生成し、List.filterでTuple.firstが偶数のものだけを取り出しています。
(問題文中では奇数となっていますが、indexedMapは0ベースのため一つずれて偶数)
あとは文字列に戻すだけですね。

ところで、このような計算をワンライナーで書くと可読性が落ちてしまうので、
let式を使って中間値(?)を定義しながら書いていくのが一般的だと思います。
この中間値、値そのものではなくてこのように小さな関数を定義していったほうがわかりやすいことも多いと思っています。 
少なくともこの記事ではこのスタイルでやろうかなと思っています。



## 02
>「パトカー」＋「タクシー」の文字を先頭から交互に連結して文字列「パタトクカシーー」を得よ

```elm
oneTwo : String
oneTwo =
    let
        base1 =
            "パトカー"

        base2 =
            "タクシー"

        base1List =
            String.toList base1

        base2List =
            String.toList base2

        joinChars a b =
            String.cons a <| String.fromChar b
    in
    List.map2 joinChars base1List base2List |> String.concat
```
それぞれList Charに変換、List.map2で

```elm
["パタ", "トク"] --　以後続く
```
というリストを作ってString.concatで文字列のリストをくっつけてるだけですね

## 03
> "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."という文を単語に分解し，各単語の（アルファベットの）文字数を先頭から出現順に並べたリストを作成せよ．

```elm
oneThree : String
oneThree =
    let
        base =
            "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."

        removeNotLatinChars : List Char -> List Char
        removeNotLatinChars =
            List.filter Char.isAlpha

        countLatinChars =
            String.toList >> removeNotLatinChars >> List.length
    in
    base
        |> String.words
        |> List.map countLatinChars
        |> Debug.toString

```
String.wordsで文を単語のリストに分解し、文字数を数える関数をリストの各要素に適用します。 リストの文字列化は面倒なのでDebug.toStringを使いました。(別に文字列化しなくてもいいんですが)
wordsという命名はHaskellでもおなじみですね

文字数を数える関数は、文字列を文字(Char)のリストに変換。アルファベット以外の文字を排除してからリストの長さを数えることにしました。


## 04
>"Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."という文を単語に分解し，1, 5, 6, 7, 8, 9, 15, 16, 19番目の単語は先頭の1文字，それ以外の単語は先頭に2文字を取り出し，取り出した文字列から単語の位置（先頭から何番目の単語か）への連想配列（辞書型もしくはマップ型）を作成せよ．

連想配列を作成するのでDictを使います。

```elm
oneFour : Dict.Dict String Int
oneFour =
    let
        base =
            "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."

        takeFirstSet =
            Set.fromList [ 1, 5, 6, 7, 8, 9, 15, 16, 19 ] |> Set.map (\n -> n - 1)

        toIndexedWords =
            String.words >> List.indexedMap Tuple.pair

        extractString i word =
            if Set.member i takeFirstSet then
                String.left 1 word

            else
                String.left 2 word

        insertDict ( i, word ) dict =
            Dict.insert (extractString i word) (i + 1) dict
    in
    base |> toIndexedWords |> List.foldl insertDict Dict.empty

```
1, 5, 6 ,7・・・番目の単語は先頭一文字を取り出し・・・という条件の判定にいちいちif式やcase式を使っていては面倒なので、先頭一文字を取り出す単語の序数のSet(集合)を作ります。
ある要素がそのSetに含まれるかどうかはSet.memberで簡単にチェックすることができます。
問題文中は1ベースですが、プログラム中では0ベースで取り扱いたいので、Setのすべての要素から-1しています。


次に単語に序数の情報を持たせたいので、先ほどのString.wordsとList.indexedMapを使って、

```elm
[(0, "Hi"), (1, "He"), (2, "Lied")] --　以下続く
```

というリストを作成します。

序数と単語から、問題文に沿った文字列を取り出すextractStringを定義します。

最後に、単語と序数のリストから辞書を作ります。 リストから何か1つのものを作るので、畳み込み(foldl)を使います。
リストから一つの辞書に畳み込む感じで、辞書をアキュムレーターとします。

## 05
> 与えられたシーケンス（文字列やリストなど）からn-gramを作る関数を作成せよ．この関数を用い，"I am an NLPer"という文から単語bi-gram，文字bi-gramを得よ．

n-gramとは何かっていう話ですが、例えば"I am an NLPer"という文の単語bi-gram(2-gram)は
`I am, am an, an NLPer`
tri-gram(3-gram)は
`I am an, am an NLPer`
です。 なんとなく分かるのではないかと思います。

```elm
oneFive : Int -> List a -> List (List a)
oneFive n list =
    let
        canMake =
            List.length list - n + 1

        createGram index elem =
            List.drop index elem |> List.take n
    in
    List.repeat canMake list |> List.indexedMap createGram
```

このn-gramは、`要素数 - n + 1`だけ作成することができます。(後ろから数えてみれば、なぜそうなるかはすぐわかります。) そこで、今回は、例えば単語bi-gramの場合、
1. `["I", "am", "an", "NLPer"]`というリストを(4 - 2 + 1)の３つ作成する
(`[ ["I", "am", "an", "NLPer"], ["I", "am", "an", "NLPer"], ["I", "am", "an", "NLPer"]]`となる)
2. リストの各`["I", "am", "an", "NLPer"]`について、序数分だけ先頭要素を削除、そこからnだけ要素をtakeする
(0から数えて1番目のリストなら、"I"を削除してから要素を2つtakeする)(`createGram`関数)
というアプローチでやりました。

このcreateGramは

```elm

        createGram =
            List.drop >> (<<) (List.take n)
```

ポイントフリースタイルでこう書くこともできますが、まあわかりにくいかなと思います。

## 06
> "paraparaparadise"と"paragraph"に含まれる文字bi-gramの集合を，それぞれ, XとYとして求め，XとYの和集合，積集合，差集合を求めよ．さらに，'se'というbi-gramがXおよびYに含まれるかどうかを調べよ．

またbi-gramです。 これを求める関数は前項のoneFiveをそのまま使うことにします。 
また、今回は複数種類の結果を求められるので、戻り値をHtmlにしてみました。(`import Html as H`としています)

```elm
oneSix : Html msg
oneSix =
    let
        xBase =
            "paraparaparadise"

        yBase =
            "paragraph"

        stringToBigramSet =
            String.toList >> oneFive 2 >> Set.fromList

        x =
            stringToBigramSet xBase

        y =
            stringToBigramSet yBase

        applyAndToString f =
            f x y |> Debug.toString

        hasSe =
            Set.member [ 's', 'e' ]
    in
    H.div []
        [ H.p []
            [ H.text <|
                "和集合は"
                    ++ applyAndToString Set.union
                    ++ "です"
            ]
        , H.p []
            [ H.text <|
                "積集合は"
                    ++ applyAndToString Set.intersect
                    ++ "です"
            ]
        , H.p []
            [ H.text <|
                "差集合は"
                    ++ applyAndToString Set.diff
                    ++ "です"
            ]
        , H.p []
            [ H.text <|
                "[se]はXに"
                    ++ (if hasSe x then
                            "含まれます"

                        else
                            "含まれません"
                       )
            ]
        , H.p []
            [ H.text <|
                "[se]はYに"
                    ++ (if hasSe y then
                            "含まれます"

                        else
                            "含まれません"
                       )
            ]
        ]

```

今回は集合の話なので、先ほど登場したSetを使います。 Set.union, Set.intersect, Set,diffを使うと和集合、積集合、差集合を簡単に求めることができます。  Set.memberを使うと、ある要素がある集合に属しているかを調べることができます。
簡単ですね。

## 07
>引数x, y, zを受け取り「x時のyはz」という文字列を返す関数を実装せよ．さらに，x=12, y="気温", z=22.4として，実行結果を確認せよ．

なんか一気にやたら簡単になった気が・・・
関数は`String -> String -> String -> String`ですね
あと２つ目では、引数にIntやString,Floatをバラバラに渡していますが、Elmでは(型クラスを持たないので)実装不可能ではないでしょうか。 もちろん最初の関数を`Int -> String -> Float -> String`と実装すれば可能ですが・・・
あとDebug.toStringを使っても実装できそうできそうですが、なんか違う気がします。
今回は全部Stringとして渡すことにします

```elm
oneSeven : String -> String -> String -> String
oneSeven x y z =
    x ++ "時の" ++ y ++ "は" ++ z

--　後半部分
 H.p [] [ H.text <| oneSeven "12" "気温" "22.4" ]

```
簡単ですね

## 08
> 与えられた文字列の各文字を，以下の仕様で変換する関数cipherを実装せよ．
    英小文字ならば(219 - 文字コード)の文字に置換
    その他の文字はそのまま出力
この関数を用い，英語のメッセージを暗号化・復号化せよ．

どうみても文字の置換関数でmapするやつですね

```elm
oneEight : String -> String
oneEight =
    let
        convert c =
            if Char.isLower c then
                Char.toCode c |> (-) 219 |> Char.fromCode

            else
                c
    in
    String.map convert
```
最後から２番目の問題ですが、あっさり終わってしまいました


## 09
いよいよ第1章ラストです
> スペースで区切られた単語列に対して，各単語の先頭と末尾の文字は残し，それ以外の文字の順序をランダムに並び替えるプログラムを作成せよ．ただし，長さが４以下の単語は並び替えないこととする．適当な英語の文（例えば”I couldn′t believe that I could actually understand what I was reading : the phenomenal power of the human mind .”）を与え，その実行結果を確認せよ． 

出ましたランダム。 これまでは参照透過な関数ばかり書いてきましたが、乱数(=副作用)が絡む以上、少々ややこしくなります。


そして、今回の問題を解くコードは以下の通りです。

```elm
oneNine : String -> Random.Generator String
oneNine =
    let
        extractLettersToShuffle : String -> String
        extractLettersToShuffle =
            String.dropLeft 1 >> String.dropRight 1

        concatShuffled : String -> List Char -> String
        concatShuffled word shuffled =
            String.left 1 word ++ String.fromList shuffled ++ String.right 1 word

        shuffleWord : String -> Random.Generator String
        shuffleWord word =
            if String.length word < 5 then
                Random.constant word

            else
                extractLettersToShuffle word
                    |> String.toList
                    |> shuffle
                    |> Random.map (concatShuffled word)

        foldGenerator : List (Random.Generator String) -> Random.Generator (List String)
        foldGenerator =
            List.foldr (Random.map2 (::)) (Random.constant [])

        concatWords : Random.Generator (List String) -> Random.Generator String
        concatWords =
            Random.map <| String.join " "
    in
    String.words
        >> List.map shuffleWord
        >> foldGenerator
        >> concatWords


```

一つ一つ説明していきます。

まずこの関数、`oneNine`は、シャッフル対象の文字列を引数にとり、`Random.Generator String`を返すものとします。
この`Random.Generator`はシャッフル済みの文字列を表すこととします。

まず単語文字列からシャッフル対象の単語(先頭と末尾以外の文字列)を切り出す関数`extractLettersToShuffle`と、
元の単語文字列(の先頭と末尾の文字)とシャッフル済みの文字列をくっつける`concatShuffled`を定義します。

ここからが本番なのですが、単語文字列を受け取って、それを並べ替えるGeneratorを返す関数`shuffleWord`を定義します。
`Random.constant`や`Random.map`の解説は正直ここで行うのは難しいので別記事でやります。(いつか書きます・・・)
ちなみにshuffleという関数は[elm-community/random-extra](https://package.elm-lang.org/packages/elm-community/random-extra/latest/Random-List)で定義されている、リストをいい感じにシャッフルしてくれる関数です。型は`List a -> Generator (List a)`です。

この関数`shuffleWord`を各単語に`List.map`で適用すると`List (Random.Generator String)`ができます。
これを順々に実行し、シャッフル済みの単語それぞれを受け取ってから、あとでくっつけてもいいのですが、
ここでは一気に各単語をくっつけた後の文字列を得られるようにしたいと思います。

最初に`List (Random.Generator String)`を`Random.Generator (List String)`に畳み込みます。
次に、`Random.Generator`の中に入ってしまった`List String`を`String.join " "`でくっつければ良さそうです。

まずは畳み込みです。畳み込みなので`List.foldr`を使います。 アキュムレーターとリストの各要素が`Random.Generator`の中に入ってしまっていますが、`Random.map2`を使えばそれぞれについて`Random.Generator`から中身の値を取り出して関数を適用し、またその値を`Random.Generator`の中に格納することができます。

あとは`Random.map`と`String.join " "`を使って単語のリストを文に戻す`concatWords`を定義すればおしまいです。 最後に各関数を並べるだけです

正直Random.Generator周りが全く説明できていないので後でなんとかします。
→　[解説記事を書きました！](https://qiita.com/Keck/items/106c3d14e2b078acdc59)

# 感想
純粋なコード量では一部の手続き言語より長くなってしまったものもありますが、全体的にスッキリかけたのではないかと思います。 あとやっぱり書いてて楽しいです。