最小自由数とHaskell

「おはよう」

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

最近は禁煙しまして、お酒が好きになりました。

やはり、神は二物を与えないということですね。

全く以て欲張りには生きにくい世界であります。

ああ、そういえば最近ドストエフスキーの「賭博者」を読了致しまして、

人の性質というか、破滅に落ちていく其れに抗えない、何か切ないというか、

ジーザスって感じです。おお！神よ！お赦しください...

はい。今はウィリアム・ギブスンの「ニューロマンサー」を読んでいます。

有名なやつです。いろいろ賞とか取ってる。SFのやつ。

ドストエフスキーを読んでから、まあ、悪い気分というわけではなかったんですが、

暗い気持ちになってしまったので、愉快になりたいなと思ったんで、このチョイスです(?)。

そろそろ本題に入りたいネ。

「お前何した」

ついにとうとうやっと「関数プログラミング珠玉のアルゴリズムデザイン」を読み始めたんです。

この本で出てくる関数型言語はHaskellなんです(なにそれ？って聞くのはナシで)。

一年ほど前なんて、Haskell好き好き言っときながら、全く書けなかったし、

この本も、ページをめくっては「ヤバイ」とか言うだけでした。

そう。俺は成長してるのよ。

で、この本の第一章「最小自由数」に関して書く。

「最小自由数」

最小自由数ってのは、簡単に言うと、与えられた自然数の有限集合に含まれない最小の自然数のことです。

[3,5,2,9]だったら"0"が求めるべき最小自由数です。

この集合の中では"2"が最小の自然数でありますが、

この中に含まれない最小の自然数であるところの、

この場合"0"が最小自由数というわけです。

[2,0,4,3]でしたら最小自由数は"1"です。

これをできるだけ速く求めたいんですね。ここではそういうアルゴリズムと実装を考えるんです。

「方法」

この本で紹介されているのは２つあります。

一つは、「Haskellの配列を用いる方法」です。

もう一方は、「分割統治法を用いる方法」です。

先ずは一つ目から紹介します。

「配列を用いる方法」

もう正直眠いし、めんどくさいんで、本当に軽く説明させて頂きます。

その考えに行き着いた経緯的なのとか省きます。本買って読みましょう。高いけど。

引数はリストですが、リスト受け取ってその長さ分の配列を作ります。

有るor無いをBoolで表します。

配列のFalseで一番小さい数を答え(最小自由数)として出します。

以下がコード。

import Data.Array
import Data.Array.ST

search = length . takeWhile id . elems

checklist xs = runSTArray (do
                {a <- newArray (0,n) False;
                sequence [writeArray a x True | x <- xs, x <= n];
                return a})
                  where n = length xs

minfree = search . checklist

配列作った後に変えるのでStateモナドでモナります。

配列の長さより大きい数は無視します。あったらTrueで書き込み。

saerch関数はTrueの続く要素を取り出していって、最終的にその取り出した個数を返します(これが最小自由数と一致する)。

minfree [〜〜〜]みたいな感じで使います。ghciとか使ってロードして試してみましょう。

「分割統治法を用いる」

分割統治法っていうのは簡単に言うとアレです。

全部やると面倒い問題を分割して小さくして小さい方を解くみたいな感じではないでしょうか。

以下がコード。

import Data.List

minfrom a (n,xs) | n == 0    = a
                 | m == b-a  = minfrom b (n-m,vs)
                 | otherwise = minfrom a (m,us)
                    where (us,vs) = partition (<b) xs
                          b       = a + 1 + n `div` 2
                          m       = length us

minfree xs = minfrom 0 (length xs,xs)

再帰ですね。

ガード記法、惚れ惚れしますね相変わらず。

whereは局所定義っていうんですが、partition (条件) で、

([条件を満たすリスト],[条件を満たさないリスト])で分け、これが(us,vs)に対応して定義されます。

リストを与えられた値よりも小さいものとそうでないものに分割しています。

まぁ、プログラム見ていただければ""削ってる""ってのは分かって頂けると思います。

このプログラムは先程のものより20%速いそうです。本にそう書いてありますし。

なんか適当ですみません。なげやり過ぎますね(時間があったら加筆してもいいなとは思ってる)。

ではありがとうございました。おやすみなさい。

ではでは。

「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からですから。

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

数学の心得(初心者が語る)

お詫び

お詫び

　　　今回は、僕の数学の集大成、なんですが、大したものはお見せできなかったのですが、はてなブログにおける数学の記法にあまり慣れていないため数式で書けませんでした。申し訳ないですね。

ではどんな記事を書くのか？

　　　今回の内容に関しては、数学というテーマで書かせていただきます。よろしくお願いいたします。任意の数学科の皆様は、温かい目でお見守りくださりますようここにお願い申し上げます。

本題

数学の初心者として

　　　数学の初心者としてまず重要なことがあって、それは、記号を覚えることだと思います。僕が今まで数学書を読んできて思うのですが、結構、当たり前のように記号が用いられており、初心者の方は特に、最初は記号の意味がわからなくてよく混乱すると思います。なのでまず、数学書を読む前に、最低限の記号は覚えておいたほうが良いかもしれません。よく使われるものを以下に挙げていきます。

(for all) : "任意の"の意。「for all」のAです。"ターンエー"とも読むらしいです。

ex)
: 全ての に対して である。

(exist) : "ある～"の意。「exist」のEです。"ターンイー"とも読むらしいです。

ex)
: である が存在する。

または : "～が唯一存在する"の意。

ex)
: である が唯一つ存在する。

と :

ex)
, :

は が実数の集合 から実数の集合 への写像であることを意味し、 はその写像が実数 を実数 に写すことを意味する。

: "～となるような…"の意。「such that」の頭文字をとったものです。

ex)
:
となるような実数 が存在する。

とまあこんなところですかね。あと、数学的な言葉回しを挙げていきます。

「高々」:「多くとも」という意味。英語では at most。 高々4個は4以下を意味します。0でもよいのです。

「適当な」: 「適当な に対し、となる」は、うまく を選べば となるということで、でたらめに をとったときには となるかもしれないということです。

「任意の」: これ結構誤解して使っている人多いですね。僕も最初の方は誤解してましたし(笑)。これは「全ての」という言葉で置き換えられるんです。「任意な に対し」というと「 を一つ選んでくるのだが、どの一つをとってきても成り立つ」ということです。

「一意的、ユニーク」: 「唯一つ」とか「一意的である」とか言われる。意味は言わずとも分かりますよね？

「自明」: でました。邪悪な呪文ですよね。これで何度死にたくなったことか...数学に向かう者同士で力量差があったとき「これって自明だよね？(死ね)」「は、ﾊｲｯ!(死んできます！(白目))」ってなりますよね。意味は「証明する必要もなく明らかである」です。まあ当然人によって自明と言える段階が違いますよね。ジョルダンの曲線定理の証明の際にも「自明」うんちゃらでミスっているお方もいたらしいです。

実践

　　　ではこれらのことをふまえて、ちょっとした定義に触れてみましょうか。

関数 が点 において連続である.とは

,
.

ということなのですが、先ほどの知識で読めますか？是非やってみてください。

謝辞

　　　何かとんでもない記事を書いた気がしますので、間違いがあったらご指摘ください。また、参考にした文献は「数学ビギナーズマニュアル」という本で、これは初心者に打って付けの本なので初心者のお方は是非一度お読みください。
http://www.amazon.co.jp/2/dp/4535787557/ref=dp_ob_image_bkwww.amazon.co.jp

ぷよぐやみんぐしたぽよ～☆

序論

　どうも。ぞでぃあっくです☆ハタチ♥大学生していますっ♥趣味は数学とぷよぐやみんぐ！情報科大学生なのですが、最近は数学のお勉強にハマっています！
　でもでも今回は、最近講義で出された課題について書かせて戴きたいと思っておりますぽよ～

本題

　講義で出た課題というのは、「引数をmとnとし、m×n行列の各マスにポイントを割り振る。右と下に各マスを移動できるものとし、通ったマスのポイントを加算していく。左上から右下まで移動したときの最大総ポイントを答えよ。」というものです。「宝集めゲーム」っていうらしい(？)fig.1 課題の例(4×5の場合)

　最初は全く分からなかったが、後々よく寝た(睡眠学習した)ことで、瞬殺できまちた☆思いのほか達成感があったので、これについて記事を書こうと思った次第です。

解答

　では、僕の考えたアルゴリズムを紹介しましょう。
　全探査を全ての経路の総和を算出して、最も大きな値を最大値として返すものとするならば、このアルゴリズムは全探査ではないです。方針としては、「各マスにそのマスにたどり着くまでの総和を割り当てる」という考えで解いていきます。そのような考えを念頭に置くと、まず、1行と1列の各マスの値は進行方向の制限性により一意的です。よって、まず値を入れちゃいましょう。(fig.2)

fig.2 1行と1列の各マスに値を割り振る

　他のマスは、上のようにはいかないですよね。まあでも、「各マスにそのマスにたどり着くまでの総和を割り当てる」という方針に変わりはないです。ここで大事なのは進行のパターンです。2×2の正方行列を考えたときに、右斜め下のマスに進むためには2パターンしかないということです。なので、その2パターンでどちらの方が大きいか比べ(fig.3)、大きい方をマスに割り振れば良いのです。(fig.4)

fig.3 2×2正方行列における進路

fig.4 2×2正方行列における最大地値を取る進路

　まあそこまで難しくないですね？どうですか？あとはこれを念頭に置いて、各マスに確実な値を端から順次に埋めていけばできますね。因みに、このfig.1のような場合は、39が最大値となるはずですがどうでしょうかね。(fig.5)

fig.5 プログラム実行例

　それと僕の書いたコードも載せちゃいます///

/*simauta.c*/
#include <stdio.h>

#define N 100

int main(){
  int i, j;
  int takara[N][N] = {{0}}; //各マスに価値を割り振るために用意
  int ship[N][N] = {{0}}; //ある位置での宝の価値の総和を表すために用意
  int south, east;

  /* 行数の入力 */
  printf("south = ");
  while(scanf("%d", &south)!= 1||south < 1||south > N){
    printf("Wrong number of rows.\n");
    printf("south = ");
    while(getchar() != '\n');
  }

  /* 列数の入力 */
  printf("east = ");
  while(scanf("%d", &east)!= 1||east < 1||east > N){
    printf("Wrong number of rows.\n");
    printf("east = ");
    while(getchar() != '\n');
  }

  /* 要素の入力 */
  for(i = 0;i <= south - 1;i++){
    printf("Please input number at matrix[%d][0~%d]: ", i, east - 1);
    for(j = 0;j <= east - 1;j++){
      while(scanf("%d", &takara[i][j])!=1){
        puts("incorrect input.");
        while(getchar() != '\n');
      }
    }
  }

  /* [0〜east][0]と[0][0〜south]まで進行したときの宝の価値の和 */
  for(i = 0;i <= south - 1;i++){
    if(i == 0) ship[i][0] = takara[0][0];
    else ship[i][0] += takara[i][0] + ship[i - 1][0];
  }
  for(i = 0;i <= east - 1;i++){
    if(i == 0) ship[0][i] = takara[0][0];
    else ship[0][i] += takara[0][i] + ship[0][i - 1];
  }

  /* れっつ航海☆ */
  for(i = 1;i <= south - 1;i++){
    for(j = 1;j <= east - 1;j++){
      ship[i][j] += takara[i][j] + ((ship[i - 1][j] >= ship[i][j - 1]) ? ship[i - 1][j] : ship[i][j - 1]);
      printf("ship[%d][%d] = %d\n", i, j, ship[i][j]);
    }
  }
  
  printf("Max = %d\n", ship[south - 1][east - 1]);
  return 0;
}

　まあ、再帰でも書けると思います。(#それはそう)
　どうも御覧いだだきましてありがとうございます(^^)またこういった記事を書いていきたいと思っておりますのでよろしくです！ではでは～