「Haskell」で「Look and Say 数列」を生成してみた

「Haskell」について

どうも。ゾディアックです。

私はしがない大学生でございます。

今回は関数型言語で有名な「Haskell」で「Look and Say 数列」を生成してみました。

Haskellって何って言われたら、まあ、語らなくちゃいけなくなるのでアレなんですが、

まぁ、軽く言うと「純粋関数型言語」であるという説明でいいでしょう。

みなさんがよくご存知の、「C言語」は、俗に「手続き型言語」と言われております。

関数を書くときにごちゃごちゃしちゃいます。

直感的に書けません。数式で書けません。関数を引数にとれません。

そもそも関数っていうのはですね、数学の分野です。

関数の定義に倣って欲しいし、一つの引数を受け取って一つの返り値を返して欲しいですよね。

Haskellの関数は基本的に引数を一つしか取れません。

ですが、カリー化という手法で、「add x y = x + y」みたいな多価関数が実現出来ます。

こんな感じの言語を「関数型言語」って言うんじゃないの？って思ってます。

そして「純粋」っていうのが「副作用」が無いって意味なんですが話すと長くなり、面倒なのでやめておきます。

「Haskell」の説明はこの程度にしときます(汗)

本題に入りましょう。

本題

「Look and Say 数列」とは

まず、「Look and Say 数列」っていうのは、

「1,11,21,1211,111221,312211,132221,...」って数列なんです。

法則性が見えますか...?

私は説明されるまでわかりませんでした(汗)答えを聞いてナルホドって感じでした。

答えを言うとですね、まず「見る」。

「1」です。そして「言う」。

"1"コの"1"です。

次の項は「11」になります(笑)。

「11」です。"2"コの"1"です。よって次の項は「21」になります。

わかります。「しね」って感じですよね(笑)。

この要領で生成していくんですね。

今回はこの数列を「Haskell」で生成してみようと言う話です。

「Haskell」で書いてみる

まず実際のコードを

import Data.List

reverseRle :: [Char] -> [Char] 
reverseRle = concatMap (\s -> show (length s) ++ [head s]) . group

las :: [[Char]]
las = ["1"] ++ (map reverseRle las)

これだけです！Haskellはやっぱすげぇ！

そして、「group」関数を使いたいので、「Data.List」をインポートします。

「group」関数っていうのは、文字列が与えられた時に、
同じ要素が続いた箇所をグループにします。

「"AAABBBBBCC"」であったら「["AAA","BBBBB","CC"]」と返します。

そして、「reverseRle」は引数取ってねぇじゃんって思うかも知れませんが、違います。

引数は取ります。合成関数の「.」が効いてます。

「reverseRle a」としたら「a」が引数なんですが、

まずは「group」関数を適用して、次に「.」以前を適用します。

そしてその結果をラングレス圧縮します。そして「reverse」します。

ラングレス圧縮っていうのが、以下のコードで書けます。

import Data.List

rle :: [Char] -> [Char] 
rle = concatMap (\s -> head s : show (length s)) . group

入力は文字列、つまり[Char]じゃないとダメです。返り値も[Char]を返します。

例えば「rle "AAABBBBBCC"」とやったら、「"A3B5C2"」って返ってきます。

これが、「"3A5B2C"」になって欲しいので、「reverseRle」が必要なんですね。

そもそも何でラングレス圧縮するのかということですが、

課題の数列が、前の項の、同じ要素が続いた箇所をグループにし、その文字の連続回数とその文字をくっつけた数字(型的には[Char])を次の項とするような数列だからです。

「show」は「Int -> [Char]」です。「111」を「"111"」にして返します。

「length」は「"111"」であったら「長さ」を返すのでこの場合は「3」を返します。

「length」は「[Char] -> Int」なので、いじりやすくするために、文字列にしたいので、「show」で文字列に調整します。

「head s」で「s :: [Char]」なんですが、返り値が「Char」になってしまうので困ります。

"[ ]"でくくって[Char]にします。

先ほどの「reverseRle」ですが、無名関数(「\」のラムダ式)で、「s」として引数をとってますが、

「s」はgroupされた["1","11","21",...]とあったら、このなかの各要素に、

headとlengthしてshowした値をくっつけた値を返しています。

これは「map」関数で、各要素に対して、第一引数の関数を適用していきます。

「concatMap」関数ですが、これは第一引数で「map」して、結果を「concat」するものです。

例えば、「concatMap ("1"++) ["1","2"]」ってやりますと、

「"11"と"12"」が生成されて、最終的にこれらをくっつけるので、「"1112"」が返ってきます。

この関数だと、例えば、「s」が「"21"」だったら、「"1211"」を返します。

「"2" ++ "1"」でくっつけているんですね。「++」は文字列同士の結合です。

「:」はリストの先頭にくっつけます。

例えば、「"11" : ["21"]」でしたら、「["11","21"]」となります。

これで、reverseRle関数については分かって頂けると思います。

次行きます。「las」関数です。これは「"l"ook "a"nd "s"ay 数列」なので「las」です(わかりづらい)。

las関数は再帰的に定義されています。

las関数の中でlas関数が使われてますから「再帰的」ということです。

まずは、初項は「"1"」ですね。

そして、「map」関数で「reverseRle」関数をそれぞれの要素に適用してやります。

Haskellは「遅延評価」が採用されていますから、lasの値が決定されてねぇじゃんってならないんです。

初項は「"1"」ですから、先ほどの「reverseRle」関数をこれに適用させます。

すると返り値は「"11"」です。

今の段階でlasは["1","11"]です。

次に適用するのは、「"11"」です。返り値は「"21"」です。

今の段階でlasは["1","11"."21"]です。

この要領で次々に無限に生成できます。

定義的には無限リストです。

は？やばくね？って普通の人は思うかも知れませんが、さっきも言ったように、Haskellは遅延評価を採用していますから、大丈夫なんです。必要なときに評価するのです。

上の関数を、Haskellの式を対話的に評価したりプログラムを解釈実行したりできる、GHCiというGHCの対話環境を使って、loadして使うといいですね。

「ghci」でGHCiは起動できます。

そして「:l 「haskellファイル」」

でloadしてやります。

lasは無限リストなので、「take」とか「!!」を使ってやって処理しましょう。

「take 10 lst」ってやると、lstを10項分返してくれます。

「lst!!10」ってやると10項目じゃなくて11項目が返ってきます。Haskellのリストは0からですから。

まぁこんな感じです。ありがとうございました。