haskell - Haskellで有限ソートリストをマージする

Question

Haskellは初めてです。有限のソートされた整数のリストを受け入れ、それらをマージ（ソート）する関数をHaskellで作成する方法を考えています。どんなコードでも大歓迎です！

Answer 1

あなたの目標が2つのリストをマージすることだけである場合、これはそれほど複雑ではありません

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

これは、merge2つのリストを取り、定義された順序関係を持つ任意のタイプのリストを生成することを意味します

merge [] x = x
merge x [] = x

これは、空のリストを何かとマージすると、その何かを取得することを意味します

merge (x:xs) (y:ys) | y < x     = y : merge (x:xs) ys
merge (x:xs) (y:ys) | otherwise = x : merge xs (y:ys)

これは、if2つのリストをマージすると、2番目のリストの最初の要素が低くなり、新しいリストの先頭に配置される必要があります。それ以外の場合は、最初のリストの最初の要素を使用する必要があります。

O(n)編集：他のいくつかのソリューションとは異なり、上記のマージは安定していることに注意してください。それが何を意味するのかわからない場合は、ウィキペディアで確認してください。

リストのリストをマージすることが目標である場合は、通常、一度に2つのリストをマージすることにより、これをボトムアップで実行します。

mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs [] = []
mergePairs [ls] = [ls]
mergePairs (x:y:ls) = (merge x y):mergePairs ls

merges :: Ord a => [[a]] -> [a]
merges [] = []
merges [x] = x
merges ls = merges $ mergePairs ls

すべての初期リストが同じ長さである場合、これが漸近的に最適であることを示すことができます（O(m n log n)ここで、はソートされたmリストの長さであり、はソートされnたリストの数です）。

これは、漸近的に効率的なマージソートにつながる可能性があります

mergeSort :: Ord a => [a] -> [a]
mergeSort ls = merges $ map (\x -> [x]) ls

Answer 2

これは、リストが有限であることを必要とせずに、それを行う必要があります。

merge :: Ord a => [a] -> [a] -> [a]
merge (x:xs) (y:ys) = if x < y
                        then x:(merge xs (y:ys))
                        else y:(merge (x:xs) ys)
merge [] xs = xs
merge xs [] = xs

英語では、各リストの最初の要素を確認し、小さい方の要素を次の要素にしてから、残っているリストをマージします。

Answer 3

(sort . concat) [[30..32],[1..3]] == [1,2,3,30,31,32]