Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

はじめに

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"の文字を逆に(末尾から先頭に向かって)並べた文字列を得よ.

oneZero : String
oneZero =
    String.reverse "stressed"

説明不要

01

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

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を使い、

[(0, 'パ'), (1, 'タ'), (2, 'ト')] -- 以後続く

のようなリストを生成し、List.filterでTuple.firstが偶数のものだけを取り出しています。
(問題文中では奇数となっていますが、indexedMapは0ベースのため一つずれて偶数)
あとは文字列に戻すだけですね。

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

02

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

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で

["パタ", "トク"] -- 以後続く

というリストを作ってString.concatで文字列のリストをくっつけてるだけですね

03

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

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を使います。

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を使って、

[(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
です。 なんとなく分かるのではないかと思います。

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)の3つ作成する
([ ["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は

        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としています)

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

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

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

簡単ですね

08

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

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

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

            else
                c
    in
    String.map convert

最後から2番目の問題ですが、あっさり終わってしまいました

09

いよいよ第1章ラストです

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

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

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

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.constantRandom.mapの解説は正直ここで行うのは難しいので別記事でやります。(いつか書きます・・・)
ちなみにshuffleという関数はelm-community/random-extraで定義されている、リストをいい感じにシャッフルしてくれる関数です。型はList a -> Generator (List a)です。

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

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

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

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

正直Random.Generator周りが全く説明できていないので後でなんとかします。
→ 解説記事を書きました!

感想

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away