recursive-merge

整列された二つのリストをマージする関数を再帰で定義してみます。

まずは、関数の型定義から。

マージの型定義

merge::(Ord a) => [a] -> [a] -> [a]

んで、次は、関数自体の定義。

アルゴリズムの教科書に載ってるような普通の手法です。

予め整列された二つのリストから、それぞれ要素を取り出し、小さい方を

新たなリストの要素に追加する、、、これを再帰的に実行する。

単純だスな、大統領。

マージの再帰的な定義

merge::(Ord a) => [a] -> [a] -> [a]

merge [] ys = ys

merge xs [] = xs

merge (xs) (ys)

| x <= y = x : merge cdr_xs ys

| otherwise = y : merge xs cdr_ys

where

x = head xs

y = head ys

cdr_xs = tail xs

cdr_ys = tail ys

⬆のケースが、ちょっとつまらないので、

次に、どちらか片方が、整列していないケースを取り扱ってみます。

この場合、

要は、整列されてないリストの要素を一つづつ、取り出す＆

整列されてるリストのどこにあるべきか？シーケンシャル動作すればいいです。

ここのシーケンシャルの部分を、挿入で実現します。

関数に引き渡す最初のリストが、非整列、二つ目のリストが整列されてるという前提です。

マージ（片方のリストが整列されてないパターン）

insert :: (Ord a) => a -> [a] -> [a]

insert x [] = [x]

insert x (y:ys)

| x <= y = x:y:ys

| otherwise = y:insert x ys

merge :: (Ord a) => [a] -> [a] -> [a]

merge [] (ys) = ys

merge (x:xs) (ys) = merge xs (insert x ys)

この派生系は、何かの伏線で考えたわけじゃあないです。単に気になったから。