はじめに
Advent Calendar初挑戦です、頑張ります。
Elmって本当にいい言語、フレームワークですよね。 書いていて楽しいし、The Elm Architectureは堅牢でシンプルだし、データがイミュータブルだったり、副作用が強制的に分離させられるのでトラブルが起きづらい、それで学習コストは比較的低い(と言われています。 )・・・
Elmは基本的にWebフロントエンドに特化した言語で、それゆえ多くの記事は「Elmを使っていかにしてWebアプリケーションを作成するか」に主眼が置かれています。 しかしここではあえて、ElmをWebから切り離し、そのプログラミング言語としての側面にスポットを当ててみようと思います。 すでに色々な言語で挑戦されている「言語処理100本ノック」を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の場合、
-
["I", "am", "an", "NLPer"]というリストを(4 - 2 + 1)の３つ作成する
([ ["I", "am", "an", "NLPer"], ["I", "am", "an", "NLPer"], ["I", "am", "an", "NLPer"]]となる) - リストの各
["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ですね
あと２つ目では、引数に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
最後から２番目の問題ですが、あっさり終わってしまいました
09
いよいよ第1章ラストです
スペースで区切られた単語列に対して，各単語の先頭と末尾の文字は残し，それ以外の文字の順序をランダムに並び替えるプログラムを作成せよ．ただし，長さが４以下の単語は並び替えないこととする．適当な英語の文（例えば”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.constantやRandom.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 StringをString.join " "でくっつければ良さそうです。
まずは畳み込みです。畳み込みなのでList.foldrを使います。 アキュムレーターとリストの各要素がRandom.Generatorの中に入ってしまっていますが、Random.map2を使えばそれぞれについてRandom.Generatorから中身の値を取り出して関数を適用し、またその値をRandom.Generatorの中に格納することができます。
あとはRandom.mapとString.join " "を使って単語のリストを文に戻すconcatWordsを定義すればおしまいです。 最後に各関数を並べるだけです
正直Random.Generator周りが全く説明できていないので後でなんとかします。
→ 解説記事を書きました！
感想
純粋なコード量では一部の手続き言語より長くなってしまったものもありますが、全体的にスッキリかけたのではないかと思います。 あとやっぱり書いてて楽しいです。