学んだこと ハッシュの仕組み
答えはここにありました。
Wikipediaの画像を転載すると、
まずキーに何かを指定して、それにハッシュ関数を通す。そうすると数字の羅列（Hash値）が生まれるので、それをメモリの番地（INDEX)としてキーとValueを格納する。 メモリの番地を決めるために、最初にある程度メモリを確保しておく必要がある。（ハッシュテーブルのサイズ）
逆に求めるときは、キーをハッシュ関数に入れると即座にポインタ的に場所が求まるので定数時間O(1）で即座にアクセスできて最高だ！
みたいな感じだと理解しました。 ポインタ的な感じで、Keyが決まるとハッシュ関数に通すだけでメモリの番地が一意に定まり一発（くらい）で数字を引き出せるということでした。
なぜ「ぐらい」なのかというと、Hash値は絶対衝突しない（同じにならない）とは言い切れず、同じになった場合は記事にある通り配列の配列にしたりして突っ込んだりするため、非常に低確率ながら1回では求まらないことがあるようです。
なるほどなあ、上の記事さんに感謝です。
実行時間については
こちらが参考になるかと。 実行時間に関しても自分用にあとでまとめたいですね。
Haskellで「ユークリッドの互除法」
GCD（最大公約数）の求め方
greatestCommonDivisor x y
|x `mod` y == 0 = y
|otherwise = greatestCommonDivisor y (x `mod` y)
where、let-in、case
where
testFunc :: Int -> Int
testFunc x = f x
where f x = x^2
whereで引数xを取る関数fにx2を束縛しています
実行結果
>testFunc 4 16
whereにはスコープがあり、パターンマッチを次のようにした場合最後の本体のみから参照されるため意図したとおりに動きません
testFunc' :: Int -> Int
testFunc' 2 = f 2
testFunc' x = f x
where f x = x^2
ロード時エラー
error: Variable not in scope: f :: Integer -> Int
追記：whereの中でもパターンマッチが使えます！
let-in
構文
let 式 in 処理
例
doublePlusTriple :: Int -> Int -> Int
doublePlusTriple x y =
let double = x^2
triple = y^3
in double + triple
結果
> doublePlusTriple 3 4 73
letのスコープは定義したあと全てです。
whereとletの違い
whereは束縛、letはそれ自体が値を持つ「式」
case
case 引数 of パターン(パターンマッチ可) -> 処理
case構文は通常のパターンマッチの糖衣構文です。 違いはどこでも使えるというところ。
パターンマッチ、ガードの話
パターンマッチとは
tellMeNumber :: Int -> String tellMeNumber 1 = "ONE" tellMeNumber 2 = "TWO" tellMeNumber 3 = "THREE" tellMeNumber x = show x ++" is bigger than 3"
実行結果
>tellMeNumber 2 TWO >tellMeNumber 4 "4 is bigger than 3"
解説
1行目、Int型で受け取ってString型で返しますという宣言。
2行目から4行目、パターンにあったらそれを実行します
最後、パターン以外の引数をxに格納し、showで文字列に変換し（++の右辺も左辺もShow型クラスのインスタンスであるため可能)、++で 文字列（文字のリスト）を結合して表示しています。
ガードとは
if文と似ていますが、かなり文体がスマートになります。
tellMeNumber' :: Int -> String
tellMeNumber' x
|x < 3 = "lower than 3"
|x == 3 = "THREE"
|otherwise = show x ++" is bigger than 3"
実行結果
>tellMeNumber' 1 "lower than 3" >tellMeNumber' 3 "THREE" >tellMeNumber' (-321) "lower than 3" >tellMeNumber' 5000 "5000 is bigger than 3"
解説
if-elseを書くのはなんか嫌だ、そんなあなたにお勧めの書き方です。
恐らく上のものをIFで書こうとするとちょっと面倒くさいです。
しかも、もっともっと条件分岐をさせたいときはどうなるでしょう？
考えるのも見るのも嫌です！そんな時はこのガードです。
|の前のインデントは4つ、|の後で引数を評価して場合分けをしていきます。
最後にotherwise（elseみたいなもの）を書くと終わりです。
なんだかSwitch文に似ています
型クラスの説明
型クラスとはつまり関数の集まり（＝＝や/=)を定めていて、その関数で扱う何かのふるまい(型)を定義するものです。
何か(1でも3でも何でも)を使うときに実装されて、というより実装されることで使えるようになって（インスタンス”実体”）、その実装されたときにEq型クラスやらOrd型クラス、Show型クラスとして認識されています。 例えば何らかの関数を自分で作る場合に「第一引数はEq型クラスを実装していればなんでもいい」みたいな定義がかけて、そこに何が入ってくるかは厳密にはわからないけど、少なくとも「==」はつかえる！みたいなことは分かって、安全です。
注釈 IntとIntegerの違い IntegerはIntのラッパーで、IntegerはJavaでは便利なメソッドなど持っている Javaでは型変換が自動で行われるのであまり気にしないが、Intはプリミティブ型でIntegerはオブジェクト型。 Javaでは。
Haskellでは、IntegerはIntと違い上限がない（Bounded型クラスを持たない）。
リスト内包表記で失敗した話
ステップのサイズは1つしか定義できない >[3,9,27..50] error
前回の記事のこれに関して、50以下の3nを羅列したい場合はどうすべきか？
>[3^x|x<- [1..],3^x<=50] [3,9,27
Haskell の気持ち
31 = 3 50以下だ！出力！
32 = 9 50以下だ！出力！
33 = 27 50以下だ！出力！
34 = 81 50より上だ！出力しない！
35 = 247 50より上だ！出力しない！
以下ずっと続く
takeWhileを使うと良いそうなのだがまだ習っていないので次回に持ち越し
range(レンジ)の使い方
リストを一気に生成する >[1..30] [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30] ステップ（法則性のあるリスト）を生成する >[1,3..30] [1,3,5,7,9,11,13,15,17,19,21,23,25,27,29] ステップのサイズは1つしか定義できない >[3,9,27..50] error 降順のリストを作るのにもつかう >[30,29..1] [30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1] レンジは文字列にも利用できる >['A'..'Z'] "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
無限リストを生成する
>[1..] 実行すると大変なことになるので注意 >[1,3..] 同じく大変なことになるので注意 正しい使い方 >take 20 [1..] [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
無限リストの様々な例
受け取ったリストの要素を永遠に繰り返す >cycle[1,2,3,4,5] [1,2,3,4,5,12,3,4,5,1,2,3,4,5,1,2,3,4,5以下無限 ひとつの要素を永遠に繰り返す >repeat 1 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,以下無限
便利なリスト生成
引数2で受け取った要素を引数1の回数繰り返す >replicate 10 5 [5,5,5,5,5,5,5,5,5,5]
