Haskellでソートされた入力をマージしますか？

Question

私はHaskellの初心者です。並べ替えられたリストの任意の数を1つのソートされたリストにマージするエレガントな関数を書こうとしています...誰もエレガントで効率的なリファレンス実装を提供できますか？

ありがとうございます！このような

Answer 1

効率が、私はそう

merge = sort . concat 

で行くだろう心配しなかった場合：

merge :: Ord a => [[a]] -> [a] 
merge [] = [] 
merge lists = 
    minVal : merge nextLists 
    where 
    heads = map head lists 
    (minVal, minIdx) = minimum $ zip heads [0..] 
    (pre, ((_:nextOfMin):post)) = splitAt minIdx lists 
    nextLists = 
     if null nextOfMin 
     then pre ++ post 
     else pre ++ nextOfMin : post 

ノートしかし、この実装は常に直線的最小を検索すること（多数のためしばらくリストはヒープなどを維持したいかもしれない）

Answer 2

何か作業をする必要があります。ここでは

merge2 pred xs [] = xs 
merge2 pred [] ys = ys 
merge2 pred (x:xs) (y:ys) = 
    case pred x y of 
     True -> x: merge2 pred xs (y:ys) 
     False -> y: merge2 pred (x:xs) ys 

merge pred [] = [] 
merge pred (x:[]) = x 
merge pred (x:xs) = merge2 pred x (merge pred xs) 

、機能MERGE2は、2つのリストをマージします。 マージは、リストのリストをマージします。 述語は、ソートに使用する述語です。

例：私はそれは、私が書くだろうことは理にかなって中置演算子と高階関数を利用することが好きので

merge (<) [[1, 3, 9], [2, 3, 4], [7, 11, 15, 22]] 

は

[1,2,3,3,4,7,9,11,15,22] 

Answer 3

を返す必要があります

infixr 5 @@ 
(@@) :: (Ord a) => [a] -> [a] -> [a] 
-- if one side is empty, the merges can only possibly go one way 
[] @@ ys = ys 
xs @@ [] = xs 
-- otherwise, take the smaller of the two heads out, and continue with the rest 
(x:xs) @@ (y:ys) = case x `compare` y of 
    LT -> x : xs @@ (y:ys) 
    EQ -> x : xs @@ ys 
    GT -> y : (x:xs) @@ ys 

-- a n-way merge can be implemented by a repeated 2-way merge 
merge :: (Ord a) => [[a]] -> [a] 
merge = foldr1 (@@) 

ここでは、xs @@ ysは、自然順序付けによって2つのリストをマージします（そして、 tes）、merge [xs, ys, zs..]は任意の数のリストをマージします。

mergeは、私のオリジナルのように、重複を排除

{-# LANGUAGE ViewPatterns #-} 

import qualified Data.Map as M 
import Data.List (foldl', unfoldr) 
import Data.Maybe (mapMaybe) 

-- merge any number of ordered lists, dropping duplicate elements 
merge :: (Ord a) => [[a]] -> [a] 
-- create a map of {n: [tails of lists starting with n]}; then 
-- repeatedly take the least n and re-insert the tails 
merge = unfoldr ((=<<) step . M.minViewWithKey) . foldl' add M.empty where 
    add m (x:xs) = M.insertWith' (++) x [xs] m; add m _ = m 
    step ((x, xss), m) = Just (x, foldl' add m xss) 

-- merge any number of ordered lists, preserving duplicate elements 
mergeDup :: (Ord a) => [[a]] -> [a] 
-- create a map of {(n, i): tail of list number i (which starts with n)}; then 
-- repeatedly take the least n and re-insert the tail 
-- the index i <- [0..] is used to prevent map from losing duplicates 
mergeDup = unfoldr step . M.fromList . mapMaybe swap . zip [0..] where 
    swap (n, (x:xs)) = Just ((x, n), xs); swap _ = Nothing 
    step (M.minViewWithKey -> Just (((x, n), xs), m)) = 
     Just (x, case xs of y:ys -> M.insert (y, n) ys m; _ -> m) 
    step _ = Nothing 

、しばらく：

hamming :: (Num a, Ord a) => [a] 
hamming = 1 : map (2*) hamming @@ map (3*) hamming @@ map (5*) hamming 
hamming = 1 : merge [map (n*) hamming | n <- [2, 3, 5]] -- alternative 

-- this generates, in order, all numbers of the form 2^i * 3^j * 5^k 
-- hamming = [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40,45,48,50,..] 

---

がの未実装ideaを盗む：

これはHamming numbersの非常に自然な定義につながりますmergeDupはそれらを保存します（Igorのanswerなど）。

Answer 4

他の投稿とは異なり、私はmerge :: [a] -> [a] -> [a]

Answer 5

簡単な注意：複数のリストをマージするとき（優先キューを使用するなど）、最適なログnの動作が得られたい場合は、イーゴールの美しいものを微調整して簡単に行うことができます上記のソリューション。 （私は上の彼の答えにこれをコメントとして書いたが、私は十分な評判を持っていない。）具体的には、あなたが：本当のプライオリティキューが少し速く/より多くのスペース効率的であることが、このソリューションは、私が言うように、漸近的に同じように良いとされていること

merge2 pred xs [] = xs 
merge2 pred [] ys = ys 
merge2 pred (x:xs) (y:ys) = 
    case pred x y of 
     True -> x: merge2 pred xs (y:ys) 
     False -> y: merge2 pred (x:xs) ys 

everyother [] = [] 
everyother e0:[] = e0:[] 
everyother (e0:e1:es) = e0:everyother es 

merge pred [] = [] 
merge pred (x:[]) = x 
merge pred xs = merge2 pred (merge pred . everyother $ xs) 
       (merge pred . everyother . tail $ xs) 

注意することは、それはだという利点があり上記のIgorの美しくクリアな解決策には、非常に微妙な調整が必要です。

コメント？