Объединить отсортированные входы в Haskell?

Question

Я новичок в Haskell, и я пытаюсь написать элегантную функцию для объединения произвольного числа отсортированных списков в один отсортированный список ... Кто-нибудь может предоставить элегантную и эффективную справочную реализацию?

Спасибо!

Answer 1

Примерно так должно работать:

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 объединяет список списков. pred - это предикат, который вы используете для сортировки.

Пример:

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

должен вернуть

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

Answer 2

Поскольку мне нравится использовать преимущества инфиксных операторов и функций более высокого порядка там, где это имеет смысл, я написал бы

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 объединяет два списка по их естественному порядку (и удаляет дубликаты), а merge [xs, ys, zs..] объединяет любое количество списков.

Это приводит к очень естественному определению чисел Хэмминга :

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

---

Воровство Яирчу Не реализовано Идея :

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

, где merge, как и мой оригинал, удаляет дубликаты, а mergeDup сохраняет их (например, Игорь ответ ).

Answer 3

Просто короткое замечание: если вы хотите иметь оптимальное поведение log 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)

Обратите внимание, что очередь с реальным приоритетом будет немного быстрее / более эффективно использовать пространство, но это решение асимптотически так же хорошо и, как я уже сказал, имеет преимущество в том, что оно очень незначительно подправляет красиво ясное решение Игоря выше.

Комментарии

Answer 4

В отличие от других постов, у меня будет 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

если бы эффективность не была проблемой, я бы пошел с

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

обратите внимание, однако, что эта реализация всегда линейно ищет минимум (в то время как для большого числа списков можно поддерживать кучу и т. Д.)