挿入ソート

単純なソートアルゴリズム．
計算量は O(n²)．

1. 空リストは整列されているものとする
2. 整列しているリストに対して，１つの要素を正しい場所に挿入する

insert                      :: Ord a => a -> [a] -> [a]
insert x [ ]                = [x]
insert x (y:ys) | x <= y    = x : y : ys
                | otherwise = y : insert x ys


isort   :: Ord a => [a] -> [a]
isort [ ]    = [ ]
isort (x:xs) = insert x (isort xs) 

マージソート

ボトムアップの分割統治法を用いたソートアルゴリズム．

1. データを分割する

2. 各々をソートする

3. マージする

以下 haskell の実装（安定ソートではない）

merge                           :: Ord a => [a] -> [a] -> [a]
merge [ ] [ ]                   = [ ]
merge xs [ ]                    = xs
merge [ ] ys                    = ys
merge (x:xs) (y:ys) | x <=  y   = x : merge xs (y:ys)
                    | otherwise = y : merge (x:xs) ys


msort :: Ord a => [a] -> [a]
msort [ ] = [ ]
msort [x] = [x]
msort xs =  merge  (msort (take center xs)) (msort (drop center xs))
            where
              center = div (length xs) 2

ユークリッドの互除法

ユークリッドの互除法は，２つの自然数または整数の最大公約数（Greatest Common Divisor）を求めるアルゴリズムです．

1. 入力を m, n (m ≧ n) とする。

2. n = 0 なら、 m を出力してアルゴリズムを終了する。

3. m を n で割った余りを新たに n とし、更に 元のnを新たにm とし 2. に戻る。

gcd                 :: Int -> Int -> Int
gcd m n | m < n     = gcd n m
        | n == 0    = n
        | otherwise = gcd n (mod m n)

最小公倍数と最大公約数の以下の関係から，
最小公倍数（Least Common Multiple）を用意に求められる．

gcd(a, b) * lcm(a, b) = a * b

lcm     :: Int -> Int -> Int
lcm m n = m * n / gcd m 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)(3)  # 5

最近 Haskell にはまってるんで，できればこんな感じで呼び出したい．

add     :: Num a=> a -> a -> a
add a b = a + b

main = print (add 2 3)  -- 5

いろいろ試してみる...

# OK
add(2)(3)
add(2) 3
(add 2)(3)
(add 2) 3

# Error
add 2(3)
add 2 3

# OK
increment = add(1)
increment 3  # 4

結論
Haskell っぽく呼ぶのは無理っぽい．

add(2)(3)

これがベターなのか．

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

複数の引数を渡す関数には、例えば和を求める関数があげられる．

add x y = x + y

これの型を調べると以下のようになる．

> :t add
add :: Int -> Int -> Int

Int と Int を引数にとって， Int を返す関数なのだが、
いまいち複数の引数を取っている感が無い．

先日紹介した，「プログラミング Haskell」(邦題 : Programming in Haskell) 3.6 章の解説でようやく理解できた．

そもそも複数の引数を取るというのが間違いであり，カリー化されていただけだ。
先程の型に括弧をつけると以下のようになる．

add :: Int -> (Int -> Int)

つまり，Int 型の引数を一つ取り，"Int 型の引数を取りInt型を返す関数"を返す型ということだ．

カリー化の考案者を Haskell Curry だと勘違いしていました．
実際は Gottlob Frege という人らしい．（wiki）

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

Haskell は，Web上のチュートリアルと連載と，WEB+DB の Dan さんの記事くらいしかやってなかったけど，体系的に学びたくなったから，図書室で「プログラミング言語 Haskell」を借りてきた．

大学にはこの本と，O'Reilly のカブトムシ本？ヘラクレス本？しか無かった． なんでヘラクレスなのか...

電車で読んでたけど，第１章のクイックソートのサンプルが美しすぎる．
Haskell にハマりそうだな．