Combina las entradas ordenadas en Haskell?

Question

Soy un novato en Haskell, y estoy tratando de escribir una función elegante para combinar una cantidad arbitraria de listas ordenadas en una sola lista ordenada ... ¿Alguien puede proporcionar una implementación de referencia elegante y eficiente?

Gracias!

Answer 1

si la eficiencia no era una preocupación me gustaría ir con

merge = sort . concat 

lo contrario:

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 

en cuenta sin embargo que esta aplicación siempre linealmente busca el mínimo (mientras que para un gran número de lista se puede desear mantener un montón etc.)

Answer 2

Algo como esto debería funcionar:

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) 

Aquí, la función merge2 fusiona 2 listas. La función fusionar fusiona una lista de listas. El pred es el predicado que utiliza para ordenar.

Ejemplo:

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

deberían volver

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

Answer 3

ya que me gusta tomar ventaja de los operadores infijos y funciones de orden superior, donde tiene sentido, me gustaría escribir

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

Aquí, xs @@ ys combina dos listas por su orden natural (y descarta el duplicado tes), mientras que merge [xs, ys, zs..] combina cualquier cantidad de listas.

Esto nos lleva a la definición muy natural de la Hamming numbers:

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

---

Stealing 's sin aplicarse idea:

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

donde merge, al igual que mi original, elimina los duplicados, mientras mergeDup los conserva (como Igor 's answer).

Answer 4

a diferencia de los otros mensajes, tendría 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

Solo una nota rápida: si desea tener el comportamiento de log n óptimo al combinar varias listas (como las que obtendría con una cola de prioridad), puede hacerlo muy fácilmente con un ajuste a la hermosa Igor solución arriba. (Hubiera puesto esto como un comentario sobre su respuesta anterior, pero no tengo suficiente reputación.) En particular, trata de:

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) 

Tenga en cuenta que una cola de prioridad real sería un poco más rápido/más eficiente del espacio, pero que esta solución asintótica es tan buena y, como digo, tiene la ventaja de que es un pequeño retoque a la solución hermosamente clara de Igor anterior.

Comentarios?