巨人の肩の上に登る

先人の積み重ねた発見に基づいて、なにかを発見しようとすることを指す。

Haskell

挿入ソート

単純なソートアルゴリズム. 計算量は O(n2). 空リストは整列されているものとする 整列しているリストに対して,1つの要素を正しい場所に挿入する insert :: Ord a => a -> [a] -> [a] insert x [ ] = [x] insert x (y:ys) | x <= y = x : y : ys | other…

マージソート

ボトムアップの分割統治法を用いたソートアルゴリズム. データを分割する 各々をソートする マージする 以下 haskell の実装(安定ソートではない) merge :: Ord a => [a] -> [a] -> [a] merge [ ] [ ] = [ ] merge xs [ ] = xs merge [ ] ys = ys merge (…

ユークリッドの互除法

ユークリッドの互除法は,2つの自然数または整数の最大公約数(Greatest Common Divisor)を求めるアルゴリズムです. 入力を m, n (m ≧ n) とする。 n = 0 なら、 m を出力してアルゴリズムを終了する。 m を n で割った余りを新たに n とし、更に 元のnを…

CoffeeScript のカリー化

個人的に CoffeeScript が再燃してる今日このごろ. CoffeeScript の関数定義はこんな感じ # CoffeeScript add = (a, b) -> a + b // JavaScript var add; add = function(a, b) { return a + b; }; 続いてカリー化してみる add = (a) -> (b) -> a + b add(2…

Haskell の複数の引数を渡す関数の型

複数の引数を渡す関数には、例えば和を求める関数があげられる. add x y = x + y これの型を調べると以下のようになる. > :t add add :: Int -> Int -> Int Int と Int を引数にとって, Int を返す関数なのだが、 いまいち複数の引数を取っている感が無い…

プログラミング言語 Haskell 借りてきた

Haskell は,Web上のチュートリアルと連載と,WEB+DB の Dan さんの記事くらいしかやってなかったけど,体系的に学びたくなったから,図書室で「プログラミング言語 Haskell」を借りてきた. 大学にはこの本と,O'Reilly のカブトムシ本?ヘラクレス本?しか…