4

複数のx個のソート済みリストを取得し、それらを増分値（最小から最大）で1つのソート済みリストにマージするマージ関数を作成したいと思います。2つのリストを作成して1つに結合することはできると思いますが、複数のリストを1つに結合してソートする場合の基本ケースを理解することはできません。

merge :: [[a]] -> [a]
4

6 に答える 6

10

多分より速い実装：

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

mergePairs :: Ord a => [[a]] -> [[a]]
mergePairs [] = []
mergePairs (x:[]) = [x]
mergePairs (x:y:tail) = mergePairs ((mergeTwo x y):(mergePairs tail))

mergeAll :: Ord a => [[a]] -> [a]
mergeAll [] = []
mergeAll x = head $ mergePairs x

mergeTwoは、2つのリストをマージするだけです。mergeAllはmergePairsを実行し、ヘッドがある場合はそれを返します。マジックはmergePairsで発生します。これは、リストのリストを取得してペアをマージしますが、これを再度実行する場合などは、少なくとも2つのリストがあります。

それは速いかもしれません、あなたが走っていると想像してください

merge = foldl merge2 []

1つの長いリストが必要で、マージしてマージします。[[1,2,3]、[4,5,6]、[7,8,9]、[10,11,12]]で実行すると、次のようにマージされます。

[]と[1,2,3]

[1,2,3]と[4,5,6]

[1,2,3,4,5,6]と[7,8,9]

[1,2,3,4,5,6,7,8,9]と[10,11,12]

ただし、ほぼ同じ長さのリストを保持する必要があります。したがって、マージする必要があります。

[1,2,3]と[4,5,6]

[7,8,9]と[10,11,12]

[1,2,3,4,5,6]と[7,8,9,10,11,12]

また、mergePairsの並列実装を検討することもできます。これは、マルチコアプロセッサで役立つ可能性があります。しかし、私はこれについての経験がありません：/

于 2013-03-10T21:05:09.657 に答える
8

2つのリストの関数を定義できる場合は、各サブリストを調べて、すべてのリストをマージするまで現在の結果とマージするだけで、任意の数のリストに一般化できます。これは、次のように折りたたむと表現できます。

merge = foldr merge2 []
于 2013-03-10T20:30:47.270 に答える
6

@ sepp2kの答えは良いですが、有限数の入力リストでしか機能しません。無限に多くのリストを与えると、最小の開始要素を見つけるのに永遠に時間がかかります。

入力リストが最初の要素を増やすことによって既にソートされていることを要求することで、これを修正できます。次に、「左上」要素 (最初のリストの最初の要素) を生成できることがわかります。これは、すべての下限になるためです。これにより、再帰的に使用して完全なマージを生成するのに十分な情報が得られます。

merge :: (Ord a) => [[a]] -> [a]
merge [] = []
merge ([]:xss) = merge xss
merge ((x:xs):xss) = x : merge2 xs (merge xss)

書くmerge2ことはまだ読者の練習として残されています :-)

于 2013-03-10T21:01:57.803 に答える
3

concat最初に と でリストをマージすると、はるかに簡単になりますsort。

import Data.List(sort)

mergeSort = sort . concat
于 2013-03-10T22:49:34.817 に答える
-3 
import Data.List ( sort )

sortLists :: (Ord a) => [[a]] -> [a]
sortLists cs = concatMap sort cs

test = [ [3,1,2],
         [5,4],
         [6,8,9,7] ]

main = print $ sortLists test

Haskell を本当に楽しむには、 と をよく見て暗記してPreludeくださいData.List。これらは、すべての Haskell プログラマーのパンとバターです。

于 2013-03-10T21:32:08.713 に答える