Haskell'de sıralanmış girdileri birleştirme?

Question

Haskell'e yeni gelen biriyim ve sıralı bir dizi sıralı listeyi tek bir sıralanmış listeye birleştirmek için zarif bir işlev yazmaya çalışıyorum ... Herhangi biri zarif ve verimli bir referans uygulaması sağlayabilir mi?

Teşekkürler! Böyle

Answer 1

verimliliği ben aksi

merge = sort . concat 

ile gider bir endişe olmasa:

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 

notu ancak bu uygulamaya her zaman doğrusal (minimum arar o süre içinde çok sayıda Bir liste, bir yığını korumak isteyebilir.)

Answer 2

şey çalışması gerekir: Burada

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) 

, fonksiyon merge2 2 listeleri birleştirir. birleştirmeyi işlevi, bir liste listesini birleştirir. pred, sıralama için kullandığınız bir yüklemedir.

Örnek: Ben, ben yazardım mantıklı infix operatörleri ve daha yüksek mertebeden fonksiyonlarının yararlanarak sever yana

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

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

Answer 3

dönmelidir

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 (@@) 

Burada, xs @@ ys iki listeyi doğal düzenleriyle birleştirir (ve duplica'yı bırakır tes), merge [xs, ys, zs..], herhangi bir sayıda listeyi birleştirir.

merge, benim orijinal gibi çiftleri ortadan kaldırır

{-# 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 

iken:

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,..] 

---

'ın uygulanmayan idea çalmak:

Bu Hamming numbers çok doğal tanımına yol açar mergeDup onları korur (Igor 's answer gibi).

Answer 4

Diğer yayınların aksine, merge :: [a] -> [a] -> [a]

type SortedList a = [a] 

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

mergeAll :: (Ord a) => [SortedList a] -> SortedList a 
mergeAll = foldr merge [] 

Answer 5

Sadece kısa bir not: birkaç listeyi birleştirirken (örneğin bir öncelik sırasına sahip olmanız gibi) en uygun günlük davranışına sahip olmak istiyorsanız, bunu bir tweak ile Igor'un güzelliğine kolayca yapabilirsiniz. Yukarıdaki çözüm. (Yukarıdaki cevaba bir yorum olarak ekleyebilirdim, ama yeterli bir itibarım yok.) Özellikle, yapmanız: Söylediğim gibi, gerçek bir öncelik sırası biraz daha hızlı/daha fazla yer verimli olacağı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) 

Not, ancak bu çözüm sadece iyi asimptotik olduğunu ve bu kadar avantaja sahiptir Yukarıdaki Igor'ın güzel açık bir çözüm için çok küçük bir çimdik.

Yorumlar?