Jak mogę połączyć skończoną liczbę nieskończonych list w Haskell?

Question

Do zadania muszę napisać jakiś kod Haskella, który ma jako dane wejściowe skończoną listę składającą się z nieskończonej listy liczb całkowitych, każda lista monotonicznie rośnie.

Teraz muszę połączyć je w jedną listę, która zamawia liczby całkowite. Ponadto wiele liczb całkowitych może pojawić się na wielu listach: na liście wyników każda liczba całkowita może pojawić się tylko raz na liście.

Więc jeśli dane wejściowe to na przykład [[1, 2, 6, 10, 28, 40, ...] [3, 4, 10, 28, 100, ...], [dowolna liczba list ]] wtedy wynik powinien wynosić [1, 2, 3, 4, 6, 10, 28, 40, 100, ...]

Trochę utknąłem tutaj. Nie wiem, jak skutecznie używać foldr do łączenia list. Myślę, że powinienem porównać szefów każdej listy i sporządzić z niej nową listę.

Answer 1

Możesz nieco uprościć problem, myśląc o połączeniu dwóch nieskończonych list posortowanych, a następnie spróbuj uogólnić. Szkielet tej seryjnej będzie wyglądać następująco:

mergeSorted :: Ord a => [a] -> [a] -> [a] 
mergeSorted [] ys = ys 
mergeSorted xs [] = xs 
mergeSorted (x:xs) (y:ys) = ??? 

Musisz porównać x i y, a zrobić coś sensownego, prawdopodobnie z udziałem rekurencyjne wywołanie mergeSorted: To nie wygląda tak źle, prawda ?

Teraz wyobraźmy sobie, że mergeSorted działa i możesz zamienić dwie nieskończone posortowane listy w jedną nieskończoną posortowaną listę. Jak zmienić N nieskończonych posortowanych list w jedną posortowaną listę? Dlaczego, to prosty krotnie! Po prostu połącz dwie listy razem, a następnie połącz trzecią z tą i czwartą z tą i tak dalej.

mergeAll :: Ord a => [[a]] -> [a] 
mergeAll xss = foldr ??? 

Answer 2

Możemy połączyć każdą parę nieskończonych monotonicznie rosnącą list (takich jak masz) przez wielokrotne pociągnięcie minimalny elementu z jednej z list, przez unfoldr pull (unfoldr jest w Data.List), z

pull (x:xs,y:ys) | x<y = Just (x, (xs,y:ys)) 
       | x>y = Just (y, (x:xs,ys)) 
       | x==y = Just (x, (xs, ys)) -- pull same from both (NB!) 

i możemy przetworzyć każdą skończoną listę według parach, połowę jej długości:

pairs f (x:y:t) = f (x,y) : pairs f t 
pairs _ t  = t 

Aby powtórzyć krok, dopóki warunek jest spełniony, to praca until:

uniquelyMerge xs = ... (until (...) (pairs (unfoldr pull)) xs) 
..... 

Nie zapomnij obsłużyć pusta lista sprawę.