4.3 BinaryHash(二分探索を利用した連想配列)
はじめに
たぶん、この記事は間違った感じのことを書いてると思います。
というわけで、参考にしないでください。
4.2 Rubyでマルチプロセス
コンちゃんの改良にあたってマルチプロセスないしマルチスレッドの機構が必要になったのでメモ。
Ruby(テスト環境ではRuby1.9.3)でマルチプロセスをしたい時は、以下のように書く。
Process.fork do # ここに処理を書く end
Process.forkで囲んだところに、子プロセスの処理を書く。
以下、テストコードとその結果。
Process.fork do 10.times do puts "Chinchin!!!" sleep 1 end end 5.times do puts "Hello!!!!" sleep 1 end
Hello!!!! Chinchin!!! Hello!!!! Chinchin!!! Hello!!!! Chinchin!!! Hello!!!! Chinchin!!! Hello!!!! Chinchin!!! Chinchin!!! okabi@ibako:~/$ Chinchin!!! Chinchin!!! Chinchin!!! Chinchin!!!
親プロセスが死ぬと端末的にはプロセス全体が終了としたと見なすらしい。
テスト環境はvbox上のUbuntu12.04だが、低スペにしたからか日本語入力処理が遅すぎて困る。デスクトップ買うか組むかしてLinux専用機作りたいでござる。
5.7 CROSSO的採点機
CROSSO風な採点機が完成した。
音程
瞬間瞬間で、歌唱した数値音階と、その時出すべき数値音階を渡して評価する。
ぴったりじゃなくても部分点が入るようにしている。
タイミング
1つのノートが終わるごとに評価する。
4分音符以下の長さの音程バーのどこかで、正しい音程を発していればOK。
音程バーにはそれぞれタグが付いており、タグの数値はx分音符を意味する。たとえば、四分音符なら4、全音符なら1、タイで2小節にまたがる全音符・全音符なら0.5。
なめらかさ
2つのノートが終わるごとに評価する（事実的に1つのノートが終わるごとに評価する）。
2つのノートの間で何らかの音を発していればOK。階段上に音が続く部分では特に大きく評価する。
ビブラート
1つのノートが終わるごとに評価する。
そのノート中に波が2つ以上連続して存在すればOK。
sin的な波と-sin的な波の2つを想定する。評価ポイントは、sin(x)でいうとx=0,PI/2,PI,3PI/2,2PI。横幅および縦幅に制限を設け、それを満たしていればOKとする。
しゃくり
1つのノートが終わるごとに評価する。
ノート中に、「本来の音程より低い音程をm秒連続で発し、その後正しい音程をn秒保った」場合OK。
コード
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace CROSSO { class Evaluator { private int all_time; // 歌唱しなければならない全時間（10ms） private int time; // 歌唱時間（10ms） class Interval { private int interval_score; // 音程点。満点なら1回の評価につき5点入る private int interval_num; // 評価した音程の数 // 初期化処理 public Interval() { interval_score = 0; interval_num = 0; } // 音程を1回評価する // scale: 出した数値音階、best_scale: 出すべき数値音階 public void Evaluate(float scale, float best_scale) { float dif = Math.Abs(scale - best_scale); interval_num += 1; if (scale == 0.0f) { interval_score += 2; } else if (dif < 0.7f) { interval_score += 5; } else if (dif < 1.0f) { interval_score += 4; } else if (dif < 1.5f) { interval_score += 3; } else if (dif < 2.0f) { interval_score += 2; } else { interval_score += 1; } } // 音程の評価値を返す public float GetScore() { if (interval_num == 0) { return 0.0f; } else { return 100.0f * (interval_score / 5.0f / interval_num); } } } class Timing { private int timing_score; // 評価点。0か1か private int timing_num; // 評価したタイミングの数 // 初期化処理 public Timing() { timing_score = 0; timing_num = 0; } // タイミングを1回評価する // scale: 出した数値音階、best_scale: 出すべき数値音階、start_index: 始まりのインデックス番号、index_size: その音符のインデックス長さ public void Evaluate(float[] scale, float best_scale, int start_index, int index_size) { timing_num += 1; for (int i = 0; i < index_size; i++) { float dif = Math.Abs(scale[(start_index + i) % scale.Length] - best_scale); if (scale[i] != 0.0f) { if (dif < 0.5f) { timing_score += 1; break; } } } } // タイミングの評価値を返す public float GetScore() { if (timing_num == 0) { return 0.0f; } else { return 100.0f * (timing_score / 1.0f / timing_num); } } } class Smoothness { private int smoothness_score; // 評価点。0～5 private int smoothness_num; // 評価したなめらかさの数 // 初期化処理 public Smoothness() { smoothness_score = 0; smoothness_num = 0; } // なめらかさを1回評価する(合わせて全音符以下の長さの、2つ分のノートを評価する) // scale: 出した数値音階、best_scale: 出すべき数値音階(2つ)、start_index: 始まりのインデックス番号、index_size: インデックス長さ、border_index: 境界のインデックス public void Evaluate(float[] scale, float[] best_scale, int start_index, int index_size, int border_index) { smoothness_num += 1; for (int i = 0; i < index_size; i++) { int index = (start_index + i) % scale.Length; if (index == border_index % scale.Length) { if (scale[index] != 0.0f) { float dif = Math.Abs(best_scale[0] - best_scale[1]); if (dif == 0.0f) smoothness_score += 1; if (dif <= 2.0f) smoothness_score += 5; else if (dif <= 5.0f) smoothness_score += 3; else smoothness_score += 1; } else { smoothness_score += 0; } break; } } } // なめらかさの評価値を返す public float GetScore() { if (smoothness_num == 0) { return 0.0f; } else { return 100.0f * (smoothness_score / 3.0f / smoothness_num); } } } class Vibrato { private int vibrato_score; // 評価点。感知できたノート数 private int vibrato_num; // 評価したノートの数 private int time; // 歌唱時間 // 初期化処理 public Vibrato() { vibrato_score = 0; vibrato_num = 0; time = 0; } // ビブラートを1回評価する // scale: 出した数値音階、start_index: 始まりのインデックス番号、index_size: その音符のインデックス長さ、time: 歌唱時間 // 戻り値: 0-> 感知されなかった、1-> 感知された public int Evaluate(float[] scale, int start_index, int index_size, int time) { this.time = time; const int necessary_wave_num = 2; // 感知に必要な波の数 const int limit_time = 50; // ビブラート感知の限界時間（*10ms） const float limit_height_min = 0.5f; // ビブラート感知可能な限界最低縦幅（数値音階） vibrato_num += 1; int break_flag = 0; for (int i = 0; i < index_size; i++) { int base_index = (start_index + i) % scale.Length; // ビブラートの起点とするインデックス float base_scale = scale[base_index]; // 起点の数値音階 // 発音されてない場合は無効 if (scale[base_index] == 0.0f) continue; // 感知の段階。n:now, b:base_scale, h:limit_height_min // mod 4 について。必要感知波数を変えられるように。 // 0-> n >= b、 1-> n >= b+h、 2-> n <= b、 3-> n <= b-h // 0-> n <= b、-1-> n <= b-h、-2-> n >= b、-3-> n <= b-h int process = 0; for (int j = 1; j < limit_time && i + j < index_size; j++) { int index = (base_index + j) % scale.Length; float dif = scale[index] - base_scale; // 起点の数値音階との差 int process_mod = Math.Abs(process) % 4; // 発音されてない場合は無効 if (scale[index] == 0.0f) break; // sin的な波 if (process >= 0) { if (process_mod == 0) { if (dif >= limit_height_min) process++; } else if (process_mod == 1) { if (dif <= 0) process++; } else if (process_mod == 2) { if (dif <= -limit_height_min) process++; } else { if (dif >= 0) process++; } } // -sin的な波 else { if (process_mod == 0) { if (dif <= -limit_height_min) process--; } else if (process_mod == 1) { if (dif >= 0) process--; } else if (process_mod == 2) { if (dif >= limit_height_min) process--; } else { if (dif <= 0) process--; } } // 波を2つ感知できていたらOK！ if (Math.Abs(process) == 4 * necessary_wave_num) { vibrato_score++; break_flag = 1; break; } } if (break_flag == 1) break; } if (break_flag == 0) return 0; else return 1; } // ビブラートの評価値を返す public float GetScore() { if (time == 0) { return 0.0f; } else { return 100.0f * (3.0f * (float)vibrato_score / ((float)time / 100.0f)); } } } class Singup { private int singup_score; // 評価点。感知できたノート数 private int singup_num; // 評価したノートの数 private int time; // 歌唱時間 // 初期化処理 public Singup() { singup_score = 0; singup_num = 0; time = 0; } // しゃくりを1回評価する // scale: 出した数値音階、best_scale: 出すべき数値音階、start_index: 始まりのインデックス番号、index_size: その音符のインデックス長さ、time: 歌唱時間 // 戻り値: 0-> 感知されなかった、1-> 感知された public int Evaluate(float[] scale, float best_scale, int start_index, int index_size, int time) { this.time = time; const int necessary_time = 5; // しゃくり感知のために必要な時間(*10ms) const int limit_time = 30; // しゃくり感知の限界時間（*10ms） const int necessary_stable_time = 5; // しゃくり感知のために必要な、正しい音程での安定時間(*10ms) singup_num += 1; int ok = 0; // しゃくり感知したら1 int process = -1; // -1:音程が下になるまで待つ、0:音程のずり上がり中、それ以外:正しい音程での安定中（数値は正しい音程に達した時間） int start_time = 0; // 低音を出し始めた時間 for (int i = 0; i < index_size && i < limit_time; i++) { int index = (start_index + i) % scale.Length; // チェックするインデックス if (process == -1 && scale[index] == 0.0f) break; // 発音していない部分があれば終了 else if (best_scale - 0.5f <= scale[index] && scale[index] <= best_scale + 0.5f) // 正しい音程 { if (process == 0) { if (i - start_time >= necessary_time - 1) { process = i; } else if (i - start_time >= limit_time) { break; } } else if (process > 0) { if (i - process >= necessary_stable_time) { singup_score++; ok = 1; break; } } } else if (process > 0) break; // 一旦正しい音程に達したのに、安定して正しい音程が出せなかった else if (scale[index] < best_scale - 0.5f) // 正しい音程より低い音を出している { process = 0; start_time = i; } else break; } return ok; } // しゃくりの評価値を返す public float GetScore() { if (time == 0) { return 0.0f; } else { return 100.0f * (3.0f * (float)singup_score / ((float)time / 100.0f)); } } } private Interval interval; private Timing timing; private Smoothness smoothness; private Vibrato vibrato; private Singup singup; // 最初に実行する public Evaluator(int all_time) { this.all_time = all_time; time = 0; interval = new Interval(); timing = new Timing(); smoothness = new Smoothness(); vibrato = new Vibrato(); singup = new Singup(); } // 音程評価のために実行する。瞬間瞬間で回す // 歌唱時間の計算も行う // scale: 出した数値音階、best_scale: 出すべき数値音階 public void EvaluateInterval(float scale, float best_scale) { interval.Evaluate(scale, best_scale); time += 1; } // タイミング評価のために実行する。1つのノートが終わったら実行する // scale: 出した数値音階の配列、best_scale: 出すべき数値音階、start_index: 出した数値音階の配列のスタートインデックス、index_size: 評価すべきインデックス数 public void EvaluateTiming(float[] scale, float best_scale, int start_index, int index_size) { timing.Evaluate(scale, best_scale, start_index, index_size); } // なめらかさ評価のために実行する。2つのノートが終わったら実行する // scale: 出した数値音階の配列、best_scale: 出すべき数値音階(2つ)、start_index: 出した数値音階の配列のスタートインデックス、index_size: 評価すべきインデックス数、border_index: 境界インデックス public void EvaluateSmoothness(float[] scale, float[] best_scale, int start_index, int index_size, int border_index) { smoothness.Evaluate(scale, best_scale, start_index, index_size, border_index); } // ビブラート評価のために実行する。1つのノートが終わったら実行する // scale: 出した数値音階の配列、start_index: 出した数値音階の配列のスタートインデックス、index_size: 評価すべきインデックス数 // 戻り値: 0-> 感知されなかった、1-> 感知された public int EvaluateVibrato(float[] scale, int start_index, int index_size) { return vibrato.Evaluate(scale, start_index, index_size, time); } // しゃくり評価のために実行する。1つのノートが終わったら実行する // scale: 出した数値音階の配列、best_scale: 出すべき数値音階、start_index: 出した数値音階の配列のスタートインデックス、index_size: 評価すべきインデックス数 // 戻り値: 0-> 感知されなかった、1-> 感知された public int EvaluateSingup(float[] scale, float best_scale, int start_index, int index_size) { return singup.Evaluate(scale, best_scale, start_index, index_size, time); } // 評価値を得る // id -> 0: 総合, 1: 音程, 2: タイミング, 3: なめらかさ, 4: ビブラート, 5: しゃくり public float GetScore(int id) { if (id == 0) { float interval_score = interval.GetScore(); float timing_score = 2.0f * timing.GetScore() / 100.0f; float smoothness_score = smoothness.GetScore(); float vibrato_score = vibrato.GetScore(); float singup_score = singup.GetScore(); if (interval_score >= 95.0f) interval_score = 88.0f + 2.0f * (interval_score - 95.0f) / 5.0f; else if (interval_score >= 90.0f) interval_score = 87.0f + 1.0f * (interval_score - 90.0f) / 5.0f; else if (interval_score >= 85.0f) interval_score = 85.0f + 2.0f * (interval_score - 85.0f) / 5.0f; else if (interval_score >= 80.0f) interval_score = 83.0f + 2.0f * (interval_score - 80.0f) / 5.0f; else interval_score = 0.0f + 83.0f * (interval_score - 0.0f) / 80.0f; if (smoothness_score > 100.0f) smoothness_score = 1.0f; else smoothness_score = 1.0f * smoothness_score / 100.0f; if (vibrato_score > 100.0f) vibrato_score = 7.0f; else vibrato_score = 7.0f * vibrato_score / 100.0f; if (singup_score > 100.0f) singup_score = 3.0f; else singup_score = 3.0f * singup_score / 100.0f; return (interval_score + timing_score + smoothness_score + vibrato_score + singup_score); } else if (id == 1) return interval.GetScore(); else if (id == 2) return timing.GetScore(); else if (id == 3) return smoothness.GetScore(); else if (id == 4) return vibrato.GetScore(); else return singup.GetScore(); } // デバッグ用 public void Debug() { UnityEngine.Debug.Log("all_time->" + all_time + ", time->" + time); } } }
感想
本来の黒よりテクニック評価が厳しいので、なかなかつらい採点になっている。
GUI.DrawTextureで反応テクニックを表示させるのが一番苦労した。
もちろん、こんな採点機はゴミも同然なので、今からオリジナルの採点機を作る。間に合うのかな
6.4 すごいHaskellたのしく学ぼう！ 第4章
再帰について。
再帰
再帰（関数）とは、関数内で自身を参照する関数である。
たとえば、フィボナッチ数列は再帰関数の代表例である。フィボナッチ数列は以下のように定義されている。
2行目の式で、自己参照を行なっているのが分かるだろう？
再帰の利点
再帰で問題を考えることで、部分的に考えたものを全体の答えとすることが出来る。つまり、「どうやって(How)」解くか、ではなく、「どういう(What)」モノか、ということを考えることで、解を得ることが出来る。そもそもHaskellはそういう風に設計された言語なので、再帰と非常に相性が良い。
たとえば、フィボナッチ数列ではF(0) = 0、F(1) = 1と定義されている。これはどうしようもない。このように、最低限与えなければならない情報を基底と呼ぶ。基底さえ考えれば、あとはその関数が「どういうものか？」ということを考えれば良い。
再帰でいろいろ定義する
GHCiでデフォルトで使える関数を自分で定義する。
定義から自分で考えたものがほとんどなので、すごいH本に載っている内容とは異なる場合がある。まぁ、ほとんどの関数は全く同じ実装になっている。
maximum
引数
1つのリスト（ただし、要素は順序付けが可能）。
戻り値
引数リスト内の最大要素。
定義
maximum' :: (Ord a) => [a] -> a maximum' [] = error "This list is empty." maximum' [x] = x maximum' (x:xs) = max x (maximum' xs) {- *Main> maximum' [8,2,6,3,1,8,3,9,1] 9 *Main> maximum' [5] 5 *Main> maximum' [] *** Exception: This list is empty. -}
replicate
引数
整数、要素。
戻り値
要素を整数回繰り返したリスト。
定義
replicate' :: Int -> a -> [a] replicate' n x | n <= 0 = [] | otherwise = x : replicate' (n-1) x {- *Main> replicate' 5 7 [7,7,7,7,7] *Main> replicate' 0 7 [] *Main> replicate' (-100) 7 [] -}
take
引数
整数、リスト。
戻り値
リストから先頭整数個を取り出したリスト。
定義
take' :: Int -> [a] -> [a] take' n _ | n <= 0 = [] take' _ [] = [] take' n (x:xs) = x : take' (n-1) xs {- *Main> take' 5 "Hello, World!" "Hello" *Main> take' (-8) "Hello, World!" "" *Main> take' 100000 "Hello, World!" "Hello, World!" -}
reverse
引数
リスト。
戻り値
ひっくり返したリスト。
定義
reverse' :: [a] -> [a] reverse' [] = [] reverse' (x:xs) = reverse' xs ++ [x] {- *Main> reverse' "Hello, World!" "!dlroW ,olleH" *Main> reverse' [] [] -}
repeat
引数
要素。
戻り値
要素の無限リスト。
定義
無限リストなので基底がない。
repeat' :: a -> [a] repeat' x = x : repeat' x {- *Main> take' 10 (repeat' 'H') "HHHHHHHHHH" -}
zip
引数
リスト、リスト。
戻り値
同じインデックスの要素をペアとしたリスト。
定義
zip' :: [a] -> [b] -> [(a,b)] zip' _ [] = [] zip' [] _ = [] zip' (x:xs) (y:ys) = (x, y) : zip' xs ys {- *Main> zip' [1,2,3,4,5] ['a','b','c'] [(1,'a'),(2,'b'),(3,'c')] *Main> zip' [1,2,3,4,5] ['a','b','c','d','e'] [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')] *Main> zip' [1,2,3,4,5] ['a','b','c','d','e','f'] [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')] *Main> zip' [1,2,3,4,5] [] [] -}
elem
引数
要素、リスト。
戻り値
要素がリスト内にあるならTrue、ないならFalse。
定義
elem' :: (Eq a) => a -> [a] -> Bool elem' _ [] = False elem' n (x:xs) | n == x = True | otherwise = elem' n xs {- *Main> elem' 'h' "Hello, World!" False *Main> elem' 'r' "Hello, World!" True *Main> elem' 'r' "" False -}
クイックソート
めっちゃ速いソート。ソートっていうのは、リストを与えられてリスト内のデータを昇順（あるいは降順）に並べ治すこと。Haskellの場合は破壊的代入ができないので、ソートしたリストを返すだけである。
ちなみに、私の頼りない記憶によると、たしか最悪計算量がO(n^2)でバブルソートと等しいが、平均計算量がO(nlogn)でめっちゃ速い、だったと思う。
アルゴリズム
昇順ソートの場合。
- 軸とする数字をリスト内から1つ選ぶ（ピボットと呼ぶ）。
- ピボット以下のものをピボットの左に、ピボットより大きいものを右にリスト化して置く。これをsmallerOrEqualとlargerと名付ける。
- smallerOrEqualとlargerに対して、1から同じ操作を行う。
定義
quicksort :: (Ord a) => [a] -> [a] quicksort [] = [] quicksort (x:xs) = let smallerOrEqual = [a | a <- xs, a <= x] larger = [a | a <- xs, a > x] in quicksort smallerOrEqual ++ [x] ++ quicksort larger {- *Main> quicksort [5,7,2,8,1,6,2,9,4,2,1,0,2,1,7] [0,1,1,1,2,2,2,2,4,5,6,7,7,8,9] *Main> quicksort "Hello, World!" " !,HWdellloor" *Main> quicksort [] [] *Main> quicksort [4] [4] -}
めっちゃ簡単に実装できた！前期実験でCでクイックソート（動的配列で）実装したけど、割と苦労した覚えがある。
感想
箸休め的な第4章。特に難しい内容はない。
次からは本格的に関数型言語に斬り込んでいく感じ。
6.3 すごいHaskellたのしく学ぼう！ 第3章
Haskellの関数構文について。
パターンマッチ
lucky :: Int -> String lucky 7 = "You are lucky!" lucky x = "Ku-z." {- *Main> lucky 5 "Ku-z." *Main> lucky 7 "You are lucky!" -}
関数定義の上から順にパターンマッチが行われ、マッチした場合それが実行される。
パターンに具体的値でなく、小文字から始まる名前を書くと、任意の値に合致するようになる。引数はその名前に束縛される。
もちろん、if/then/elseを使ってもluckyは定義することができるが、見やすさの問題でこちらの方が優れた定義方法と言える。
階乗を計算するfactorialを、再帰とパターンマッチを使って定義する。
factorial :: Integer -> Integer factorial 0 = 1 factorial n = n * factorial(n-1) {- *Main> factorial 5 120 -}
0の階乗は1と定義する。まず、引数が0であるかチェックする。0ならば1を返す。それ以外の整数ならば、n*factorial(n-1)を返す。再帰について詳しくは第4章でやるので、この辺で置いておく。
パターンマッチは、任意の値を取る場合を考えないとエラーでプログラムがクラッシュする場合があるので、最後に任意値についてのパターンマッチを入れておく方が良い設計である。
タプル
addVectors :: (Double, Double) -> (Double, Double) -> (Double, Double) addVectors (x1, y1) (x2, y2) = (x1 + x2, y1 + y2) {- *Main> addVectors (3,4) (5,6) (8.0,10.0) -}
リスト
*Main> let xs = [(1,1), (2,3), (3,1), (4,3), (5,1), (6,3)] *Main> [x | (x,1) <- xs] [1,3,5]
head関数を定義する
head' :: [a] -> a head' [] = error "list is empty." head' (x:_) = x {- *Main> head' [1,2,3,4,5,6,7] 1 *Main> head' [] *** Exception: list is empty. -}
asパターン
値をパターンに分解しつつ、パターンマッチ対象となった値自体を参照したい時に使用する。
headAndString :: String -> String headAndString [] = error "list is empty." headAndString xs@(x:_) = "head -> " ++ [x] ++ ", string -> " ++ xs {- *Main> headAndString "oh,chin chin" "head -> o, string -> oh,chin chin" -}
ガード
パターンマッチは具体的な値でしかマッチングが出来なかったが、ガードでは範囲をしていすることでパターンマッチ（みたいなもの）が可能。
BMI指数を入力すると文字列による評価を返すbmiTellを定義する。
bmiTell :: Double -> String bmiTell bmi | bmi <= 18.5 = "You are too thin!" | bmi <= 25.0 = "You look good!" | bmi <= 30.0 = "You are fat!" | otherwise = "You are a whale!" {- *Main> bmiTell 21.0 "You look good!" *Main> bmiTell 32.6 "You are a whale!" -}
パイプ文字（|）から続く部分がガードと呼ばれる。パイプ文字以降に条件式を書き、Trueならイコール（=）以降の内容が返される。どのガードも通り抜けた場合、otherwiseで受け止められる。
where
ガードを利用して、体重・身長を入力して計算したBMI指数から、文字列による評価を返すbmiTellを(再)定義する。
なお、BMI指数は体重(kg)を身長(m)の2乗で割った値である。
bmiTell :: Double -> Double -> String bmiTell weight height | weight / height ^ 2 <= 18.5 = "You are too thin!" | weight / height ^ 2 <= 25.0 = "You look good!" | weight / height ^ 2 <= 30.0 = "You are fat!" | otherwise = "You are a whale!" {- *Main> bmiTell 52.0 1.698 "You are too thin!" -}
ガリガリやな、って言われた;-)
しかし、この書き方はイマイチであるのは見れば分かると思う。同じ計算を3回繰り返している。
そこで、whereを使うとすっきりと書ける。
bmiTell :: Double -> Double -> String bmiTell weight height | bmi <= 18.5 = "You are too thin!" | bmi <= 25.0 = "You look good!" | bmi <= 30.0 = "You are fat!" | otherwise = "You are a whale!" where bmi = weight / height ^ 2 {- *Main> bmiTell 52.0 1.698 "You are too thin!" -}
whereのスコープ
whereのスコープは、属するパターンマッチのみである。ガードは1つのパターンマッチの連続と見なされる。
たとえば、以下の関数を考える。
greet :: String -> String greet "okabi" = nicegreeting ++ ", okabi!" greet "gojira" = badgreeting ++ ", gojira!" greet name = normalgreeting ++ "," ++ name ++ "!" where nicegreeting = "Hello" badgreeting = "Chinko" normalgreeting = "Hi"
この関数は正しく動作しない（というかコンパイルエラーになる）。
whereのスコープは1つのパターンマッチのみなので、この関数ではnicegreeting・badgreeting・normalgreetingはgreet nameから始まるパターンでしか認識できないためである。
whereを使って、もう少しスマートにbmiTellを定義する。
bmiTell :: Double -> Double -> String bmiTell weight height | bmi <= thin = "You are too thin!" | bmi <= good = "You look good!" | bmi <= fat = "You are fat!" | otherwise = "You are a whale!" where bmi = weight / height ^ 2 (thin, good, fat) = (18.5, 25.0, 30.0)
where内の関数
where内では関数も定義できる。体重と身長のリストからBMI指数のリストを返すbmiListを定義する。
bmiList :: [(Double, Double)] -> [Double] bmiList xs = [bmi w h | (w, h) <- xs] where bmi weight height = weight / height ^ 2 {- *Main> bmiList [(52.0, 1.698), (85.0, 1.752), (32.0, 1.519)] [18.03549107173825,27.69177039678072,13.868657743630061] -}
let式
whereが後から変数や関数を定義していたのに対し、前から定義するlet式がある。
「式」と名のつく通り、let自体が値を返すという点でwhereと明確に異なる。「式」だから、whereのようにガードをまたぐことはできない。
円柱の表面積を高さと半径から求めるcylinderを定義する。
cylinder :: Double -> Double -> Double cylinder h r = let sideArea = 2 * pi * r * h topArea = pi * r ^ 2 in sideArea + 2 * topArea {- *Main> cylinder 3 4 175.92918860102841 -}
let式は、let A in Bという形を取る。ここで定義した値はlet式全体でのみ参照できる。
GHCiにおいてinを省略した場合は、全体から参照可能になる。GHCiでlet式を定義した時に、定義した値が返るのは、let式が「式」だからである。
また、let式は「式」なので、リスト内包表記で利用することもできる。
体重と身長のペアのリストから肥満な人のBMIだけをリスト化するbmiList'を定義する。
bmiList' :: [(Double, Double)] -> [Double] bmiList' xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi > 25.0] {- *Main> bmiList' [(52.0, 1.7), (55.0, 1.7), (60.0, 1.7), (70.0, 1.7), (80.0, 1.7), (90.0, 1.7), (100.0, 1.7)] [27.68166089965398,31.14186851211073,34.602076124567475] -}
case式
Cとかのswitchでお馴染みのcase。Haskellではコイツも「式」なので、いろいろな使い方ができる。
リストの先頭要素を返すheadを、case式を使って定義する。
myHead :: [a] -> a myHead xs = case xs of [] -> error "list is empty." (x:_) -> x {- *Main> myHead "Chinko" 'C' -}
case Expression of Pattern1 -> Result1...という書き方になる。of以降のパターンはインデントを揃えないとエラーが起きたので注意。
case式全体が値を返すのでこのような書き方もできる。
describeList :: [a] -> String describeList xs = "This list is " ++ case xs of [] -> "empty." [x] -> "a singleton list." ls -> "a longer list." {- *Main> describeList "" "This list is empty." *Main> describeList "c" "This list is a singleton list." *Main> describeList "chinchin" "This list is a longer list." -}
感想
- whereは後から定義を補完するもの。
- let A in B は全体が1つの式となり、その中で利用可能なモノをA内で定義、Bがlet式全体の値となる。GHCiにおいてinを省略した場合は、A自体がlet式全体の値となり、スコープが全体になる。
- case A of B -> C は全体が1つの式となり、以前定義されているAがBのパターンにマッチする場合Cをcase式全体の値として返す。
式とそうでないものの違いをハッキリ認識することが大切であるようだ。式は必ず値を返す。
だから、ifもif「式」って呼んでたんですね。
パターンマッチの強みは、大きく捉えているもの（たとえばタプルとかリストとか）から部分を取り出して、そこを評価できること。これが出来るのはwhereおよびlet式。caseでは部分評価はできない。
あまり深く考えると頭がおかしくなりそうだから、適当に組んでいくうちにもっと理解が深まるだろう…。というわけで次に進もう。
6.2 すごいHaskellたのしく学ぼう！ 第2章
第2章はHaskellの型システムについて。
明示的な型宣言
GHCiでは、:tを使うことで型を調べることができる。
Prelude> :t 'a'
'a' :: Char
Prelude> :t True
True :: Bool
Prelude> :t "Hello"
"Hello" :: [Char]
Prelude> :t 4 == 5
4 == 5 :: Bool
Prelude> :t ('a', True)
('a', True) :: (Char, Bool)Haskellにおける"::"は、「の型を持つ」と読むことができる。
この中で注目すべきは、文字列とタプル。"Hello"はCharのリストとして表現されている。('a', True)は(Char, Bool)という型である。タプルは、要素の数と要素の型の組み合わせで1つの新しい型となる。
Haskellでは、型名はすべて大文字から始まる。
関数に明示的な型を与える
removeNonUppercase :: [Char] -> [Char] removeNonUppercase st = [c | c <- st, c `elem` ['A'..'Z']]
1行目の表現で、「removeNonUppercaseはCharのリストからCharのリストへの写像である」と読むことができる。
なお、removeNonUppercaseは与えられた文字列から大文字以外を除去した文字列を返す関数である。
引数が2つ以上ある場合は以下のように書けば良い。addThreeは、与えられた3整数をすべて足しあわせて返す関数。
addThree :: Int -> Int -> Int -> Int addThree x y z = x + y + z
一般的なHaskellの型
Integer
有界でない整数型。正確にはメモリ上の限界点まで、だろうけど。
引数の階乗を返すfactorialを定義してみる*1。
factorial :: Integer -> Integer factorial n = product [1..n] -- *Main> factorial 50 -- 30414093201713378043612608166064768844377641568960512000000000000
Bool
真理値型。TrueかFalseしか取れない。
Char
Unicode文字型。文字をシングルクォートで囲む。Charのリストは文字列型。
タプル
タプルの1つ1つが型。一度に最大62個までしか定義できないらしいが、そんなに必要になることはまずないとのこと。空タプルを1つのタプルだとしても合計63個だが、あと1つはなんだろう。
型変数
リストの先頭要素を取り出すheadの型を見てみる。
*Main> :t head head :: [a] -> a
ここで使われている「a」は小文字から始まっているので型ではない。これは型変数と呼ばれる。C++でいうテンプレートみたいなもの。
型変数名は小文字から始まっていれば何でもいいが、1文字のみで表すことが多い。また、1つの型宣言中に同じ文字が使われている場合、それらの型は同じであることを意味する。
型クラス
…だけど、型変数では少し厄介なことが起こる。
たとえば、第1章でsucc（引数の次の要素を返す）という関数が出てきたが、これに(3,2)というタプルを与えるとどうなるだろうか。「次の要素」が定義されていないので、どうしようもない。
そこで、型変数に制約を与えたい。具体的には、「順番」が存在している型（つまり可算集合）のみを取れるようにしたい。
succの型を見てみよう*4。
succ :: Enum a => a -> a
ここで、"::"以降の記述は「aはEnumクラスのインスタンスであり、aからaへの写像である」と読める。Enumクラスは性質として順番が定義できる。
型を統合させるものが型クラスである。すなわち、以下のような構造をしている。
Haskellの型クラス
Eq
等値性を持つクラス。==および/=による比較が可能。
Ord
大小比較ができるクラス。>および<による比較が可能。なお、その性質上Eqクラスに部分集合として含まれる*5。
Show
文字列に変換可能なクラス。たとえば、
*Main> show 1234 "1234"
Read
文字列から変換可能なクラス。たとえば、
*Main> read "True" || False True
Enum
順番があるクラス。
Bounded
有界なクラス。
Num
数を表すクラス。加減乗除が定義可能。
Floating
浮動小数点数を表すクラス。
Integral
整数を表すクラス。
型推論
ここで、fromIntegralという関数の型を調べる。
*Main> :t fromIntegral fromIntegral :: (Integral a, Num b) => a -> b
すなわち、与えた整数を何らかの数型に変換する関数である。
たとえば、以下のような状況で使用する。
*Main> length [1,2,3,4] + 1.0 # Error。length :: [a] -> Int なので、IntとFloatの足し算になるため。 *Main> fromIntegral( length [1,2,3,4] ) + 1.0 5.0 # FloatはNumのインスタンスなのでOK。
…と、このようにfromIntegralが返す型は明示的に宣言されていないが、Haskellは状況に応じて必要な型を推論し、与えられたクラスから適当なインスタンスを決定する。これを型推論という。
Haskellは非常に強い静的型付けを持ちつつ、強力な型推論も備えている。
型が一意に定まらない場合、Haskellはエラーを返す。たとえば、以下のような例を考えると良い。
*Main> read "5" - 2 3 # 2がIntなので、read "5" はIntとして一意に定まる。 *Main> read "5" # エラー。Numのインスタンスが一意に定められない。
感想
型・型クラス辺りは文章で読んでもピンと来ないので、集合論的に考えるとスッキリする。
6.1 すごいHaskellたのしく学ぼう！ 第1章
カラオケ採点機制作の息抜きとして、「すごいH本」ことすごいHaskellたのしく学ぼう！を読み始めた。
- 作者: Miran Lipovača,田中英行,村主崇行
- 出版社/メーカー: オーム社
- 発売日: 2012/05/23
- メディア: 単行本（ソフトカバー）
- 購入: 25人 クリック: 580回
- この商品を含むブログ (51件) を見る
Haskellとは
Haskellとは、純粋関数型言語である。CとかJavaとか普段我々がよく使う言語は手続き型言語と呼ばれる。
関数型言語では、「ある関数は必ず決まったある値を返す」ことを原則とする。そもそも、数学における関数の定義は「ある引数を与えるとある決まった値を返す」である。そのため、において「yはxに関する関数」であるが、「xはyに関する関数」ではない*1。グラフを考えればわかるが、あるy(>0)を与えてもxの値は一意に定まらないのである。「ある引数を与えると必ず決まったある値を返す」関数のことを副作用のない関数と呼ぶ。Haskellは副作用のない関数しか扱えない。
手続き型言語では、関数は必ずしも値を返すわけではない（Cとか考えてもらうとわかる）。関数内にはそのメソッドが実行する手続きが書かれているのである。
ちなみに、Cだと簡単に副作用のある関数を書くことができる。たとえば、以下のような関数である。
int a; int func(int x){ return x + a; // funcの値はグローバル変数aに依存する。すなわち、xに対して一意でない }
また、Haskellでは遅延評価を基本とする。
遅延評価とは、「その値が必要となるまで計算しない」というものである*2。これによって、無限長のリストを扱うこともできる。なぜなら、本当に必要となるまでそのリストは評価されないからだ。
というわけで、Haskellは手続き型言語とはまた異なった趣向の言語である。これがどういう世界で有効なのかというと、まぁ、今の私では数学への応用くらいしか思いつかない。要するに暇つぶしで読み始めた。
環境構築
Ubuntu12.04にて。
sudo apt-get install haskell-platform
これでHaskellのコンパイラ・インタプリタ・基本ライブラリがインストールされる。
対話環境を起動するには、端末でghciと打つ。
okabi@pc:~/haskell$ ghci GHCi, version 7.4.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude>
試しに。
Prelude> 2 * 4 8
基本演算
Prelude> 1 + 2 * 3 7 Prelude> (1 + 2) * 3 9 Prelude> 5 / 2 2.5 Prelude> True && False False Prelude> True || False True Prelude> not False True Prelude> not (True && False) True Prelude> 5 == 5 True Prelude> 5 /= 0 True Prelude> "hello" == "hello" True
Haskellは型が厳密なので、同じ型同士でないと比較はできない。
基本関数
関数succは与えた引数の次に位置する値を返す。
Prelude> succ 8 9 Prelude> succ 'a' 'b'
関数名を引数の前に置く関数を前置関数と呼ぶ。演算子'+'や'-'も、その前後にある数を引数とする関数と捉えることができる。このように引数の間に関数名を置く関数を中置関数と呼ぶ。
Prelude> min 7 9 7 Prelude> max 7 9 9 Prelude> div 5 2 2 Prelude> 5 `div` 2 2
2引数関数は中置関数っぽくすることも可能。その場合、関数名をバッククォート（Ctrl+@）で囲む必要がある。
関数定義
baby.hsというファイルを作って、以下のように書く。
doubleMe x = x + x
これは、引数1つ（x）を取り、x+xの値を返すdoubleMeという関数である。なお、関数名の最初の文字は小文字である必要がある。何かしら理由があるらしいがまだ知らない。
実際にghci上で使用するには、コードを保存した上でロードする。
Prelude> :l baby.hs [1 of 1] Compiling Main ( baby.hs, interpreted ) Ok, modules loaded: Main. *Main> doubleMe 7 14
次に、「xとyを与えて2x+2yを返す」関数doubleUsを定義する。
doubleUs x y = doubleMe x + doubleMe y
評価の優先順位は演算子より関数のほうが高い。
次に、「xが100より大きい時はxを、それ以外の場合は2xを返す」関数doubleSmallNumberを定義する。
doubleSmallNumber x = if x > 100 then x else 2*x
Haskellでは、if文に必ずelseが必要である。なぜなら、未定義領域が出来るのでif文が「関数」とならないためである。
リスト
*Main> let lostNumbers = [4,8,15,16,23,42] *Main> lostNumbers [4,8,15,16,23,42]
こんな感じで、'['と']'で囲むとリストになる。リストの要素はすべて同じ型でなければならない。つまり、
[1,'a'] # できない
みたいなことはできない。なお、GHCiでletを使うのは、定数宣言みたいなものだと思えば良い。
文字列は文字のリストである。
*Main> let string = ['c','a','t'] *Main> string "cat"
リストの結合には'++'を使う。
*Main> let st1 = "a " *Main> let st2 = "cat" *Main> st1 ++ st2 "a cat"
リストの先頭に要素を追加するには':'を使う。
*Main> let st = " cat" *Main> 'a' : st "a cat"
以下のような書き方はできない。
*Main> 'a' ++ " cat" # できない。++はリストとリストをつなぐため。 *Main> "a " : "cat" # できない。:は第1引数を要素で取らねばならないため。
リストのリストとかも書ける。
*Main> let a = [[1,2,3], [4,5,6], [7,8,9]] *Main> a [[1,2,3],[4,5,6],[7,8,9]] *Main> a ++ [[10,11,12]] [[1,2,3],[4,5,6],[7,8,9],[10,11,12]] *Main> [-2,-1,0] : a [[-2,-1,0],[1,2,3],[4,5,6],[7,8,9]]
リストの操作
*Main> let a = [9,8,7,6,5,4,3,2,1] *Main> let b = [1,8,3,6,5,4,7,2,9] *Main> a !! 2 # !! n はインデックスナンバーnの要素を取り出す。 7 *Main> a > b # リストは先頭要素から順に比較ができる。 True *Main> [9,8,7] < [9,9,1] # 先頭要素が同じ場合、再帰的に次の要素の大小を見る。 True *Main> [9,8,7] > [9,8,6,9] # サイズが違っていても良い。あぶれた分は無視される（空リストとの比較という見方も可能）。 True *Main> [1,2,3] > [] # 空リストは必ず最小。 True *Main> head a # aの先頭要素を返す。 9 *Main> tail a # aの第2要素以降のリストを返す。 [8,7,6,5,4,3,2,1] *Main> last a # aの最終要素を返す。 1 *Main> init a # aの最終要素を除いたリストを返す。 [9,8,7,6,5,4,3,2] *Main> length a # aのサイズを返す。 9 *Main> null a # aが空リストならTrueを返す。 False *Main> null [] True *Main> reverse a # aを反転させたリストを返す。 [1,2,3,4,5,6,7,8,9] *Main> take 3 a # aの第n要素までをリストにして返す。 [9,8,7] *Main> take 1 a [9] *Main> take 0 a [] *Main> drop 3 a # aの第n要素までを落としたリストを返す。 [6,5,4,3,2,1] *Main> drop 0 a [9,8,7,6,5,4,3,2,1] *Main> drop 100 a [] *Main> maximum a # aの最大要素を返す。 9 *Main> minimum a # aの最小要素を返す。 1 *Main> sum a # aの総和を返す。 45 *Main> product a # aの積を返す。 362880 *Main> 6 `elem` a # aに要素が存在する場合はTrueを返す。 True *Main> 0 `elem` a False
レンジ
範囲を指定して、それをすべて要素とするリストを作ることができる。これをレンジと呼ぶ。
また、最初の要素を指定することで等差数列のリストを作ることもできる。これをステップと呼ぶ。
*Main> [1..9] [1,2,3,4,5,6,7,8,9] *Main> [1,3..9] [1,3,5,7,9] *Main> [1,4..20] [1,4,7,10,13,16,19]
レンジを利用して無限リストを作ることもできる。たとえば、3から始まる3の倍数のうち24番目までのリストを得るには、以下のようにすれば良い。
*Main> take 24 [3,6..] [3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,51,54,57,60,63,66,69,72]
これは、Haskellが遅延評価だからこそできる芸当である。つまり、無限リスト生成時には実際にはリスト内容が計算されていないのである。take 24を適用させることで、初めて無限リスト（の一部）が評価される。
その他、特筆すべきリスト利用について。
*Main> take 10 (cycle [1,2,3]) # cycleは与えたリストを繰り返す無限リストを生成する。どこかで切らないと無限ループするので注意。 [1,2,3,1,2,3,1,2,3,1] *Main> take 12 (cycle "LOL ") "LOL LOL LOL " *Main> take 10 (repeat 5) # repeatは与えた要素を繰り返す無限リストを生成する。 [5,5,5,5,5,5,5,5,5,5] *Main> replicate 10 5 # replicateはx回yを繰り返すリストを生成する。 [5,5,5,5,5,5,5,5,5,5] *Main> [0.1,0.3..1] # 実数は浮動小数点数なので、期待した値とは異なるものが得られる場合があるので注意 [0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]
リストの内包表記
Haskellの大きな特徴の一つだと思う。
Haskellでは、リストを数学の集合表記と似たような表記法で記述可能である。
たとえば、のような集合表記があったとする（10未満の自然数xについて2xを要素とする集合）。これは、Haskellでは以下のように表記する。
*Main> [2*x | x <- [1..9]] [2,4,6,8,10,12,14,16,18]
50から100のうち、7で割ったあまりが3であるすべての数を含むリストは以下のように定義する。
*Main> [x | x <- [50..100], x `mod` 7 == 3] [52,59,66,73,80,87,94]
また、要素表記に複数のリストを使った場合は、すべての組み合わせが要素となる。
*Main> [x+y | x <- [1,2,3], y <- [10,100,1000]] [11,101,1001,12,102,1002,13,103,1003]
ここで、リストの長さを返すlength'を自分で定義してみよう*3。
length' xs = sum [1 | _ <- xs]
ちょっと分かりにくいので説明。
引数として与えたリストxsから、順番にアンダーバーに要素を取っていく（事実的に要素を1つずつ捨てている）。取るたびに、1を要素としてリストに追加する。つまり、xsのサイズの、1のみを要素としたリストができる。その総和を取ることで、xsの長さを得る。
タプル
タプルとは、リストのようなものである。リストとの違いは以下の通り。
- 異なる型を1つのタプルに纏められる
- タプル比較の際、長さが等しくすべてのインデックスの型が等しい必要がある
長さ2のタプルはペア、長さ3のタプルはトリプルと呼ばれる。
以下、タプルを扱う基本関数と共に使用例。
*Main> (1,'a') < (1,'b') True *Main> fst (1, 2) # fstはペアの最初の要素を返す。 1 *Main> snd (1, 2) # sndはペアの最後の要素を返す。 2 *Main> zip [1, 2, 3, 4, 5] "abcde" # zipは2つのリストからペアのリストを作る。 [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')] *Main> zip [1..5] "abc" # リストの長さが異なる場合、短い方に合わせられる。 [(1,'a'),(2,'b'),(3,'c')] *Main> zip [1..] ['a'..'f'] # よって、無限リストにも対応可能。 [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e'),(6,'f')]
