В Haskell, как вы можете отсортировать список бесконечных списков строк?

Question

Итак, если у меня есть (конечный или бесконечный) список (конечных или бесконечных) списков строк, можно ли отсортировать список по длине сначала, а затем по лексикографическому порядку, исключая дубликаты? Входной образец/вывода будет:

Входной сигнал:

[[ "а", "б", ...], [ "а", "аа", "ааа"], [ "б », "бб", "БББ", ...], ...]

Выход:

[ "а", "б", "аа", "бб", "ааа", "bbb", ...]

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

Если кто-то не понял, что я имел в виду по порядку сортировки, я имел в виду, что кратчайшие строки сначала сортируются, и если одна или несколько строк имеют одинаковую длину, то они сортируются с использованием оператора <.

Спасибо!

Answer 1

Ну, я проигнорирую ваш запрос на сортировку бесконечных данных.

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

Начнем с образцом:

> s 
[["a","b"],["a","aa","aaa"],["b","bb","bbb"]] 

А затем построить программу постепенно.

Первая сортировка по длине (с использованием Data.Ord.comparing для построения тела сортировки):

> sortBy (comparing length) s 
[["a","b"],["a","aa","aaa"],["b","bb","bbb"]] 

Ok. Это выглядит разумно. Итак, давайте просто контактируем и сортируем длину, а затем альфа:

> sortBy (comparing length) . nub . concat $ s 
["a","b","aa","bb","aaa","bbb"] 

Если ваш вход отсортирован. В противном случае вам понадобится немного другое тело для сортировки.

Answer 2

• В общем, невозможно сортировать бесконечные списки. Поскольку наименьший элемент может находиться в бесконечном положении, и мы должны найти его, прежде чем выводить его.

• Merging бесконечные отсортированные списки возможны.

• В общем, объединение бесконечного списка отсортированных списков невозможно. По той же причине, что их сортировка.

• Слияние бесконечного списка отсортированных списков, отсортированных по головам (forall i j. i < j =>head (lists !! i) <= head (lists !! j)), возможно.

Так что я предполагаю, что вы действительно хотите объединить отсортированный список отсортированных списков. Это даже задача, которая имеет смысл.Там даже some existing code, который использует его, реализуемый для монадических списков там - своего рода уродливого синтаксиса-накрест и т.д. Так вот версия для обычных списков:

mergeOnSortedHeads :: Ord b => (a -> b) -> [[a]] -> [a] 
mergeOnSortedHeads _ [] = [] 
mergeOnSortedHeads f ([]:xs) = mergeOnSortedHeads f xs 
mergeOnSortedHeads f ((x:xs):ys) = 
    x : mergeOnSortedHeads f (bury xs ys) 
    where 
    bury [] ks = ks 
    bury js [] = [js] 
    bury js ([]:ks) = bury js ks 
    bury jj@(j:js) ll@(kk@(k:ks):ls) 
     | f j <= f k = jj : ll 
     | otherwise = kk : bury jj ls 

ghci> take 20 $ mergeOnSortedHeads id $ [[0,4,6], [2,3,9], [3,5..], [8]] ++ map repeat [12..] 
[0,2,3,3,4,5,6,7,8,9,9,11,12,12,12,12,12,12,12,12] 

кстати: что вам нужно?

Answer 3

В конечном счете, вы не можете сортировать бесконечный список, потому что элементы в хвосте списка могут просачиваться полностью до конца результата, поэтому вы не можете закончить сортировку бесконечного списка, пока не увидите последний элемент, но ваш список бесконечен, поэтому вы никогда туда не попадете.

Единственный способ, которым вы могли бы попытаться отсортировать бесконечный список, потребует ограничений для жителей списка. Если значения элементов списка относятся к well-founded set, и содержимое списка уникально, вы могли бы хотя бы сделать некоторый прогресс в возвращении элементам исходных элементов списка. Например, если список имеет разные натуральные числа, вы можете вернуть первое 0, которое вы видите, первое и т. Д., Но вы не смогли бы добиться какого-либо прогресса в результате, пока не увидите 2, независимо от того, как далеко вниз по списку ты пошел. В конечном счете, если вы когда-либо пропустили элемент в наборе, потому что его не было в источнике, вы перестали бы создавать новые выходные элементы, пока у вас не будет весь вход.

Вы можете сделать то же самое со строками, потому что они хорошо обоснованы, но это даже отдаленно жизнеспособно, если вы планируете возвращать все возможные строки.

Короче говоря, если вам это нужно, вы собираетесь решить проблему, которую вы имеете не так. Это не приемлемый путь к любому решению, которое вы хотите использовать.

Как отметил yairchu, объединение конечного числа отсортированных бесконечных списков работает нормально.

Answer 4

Может ли это быть сделано, в значительной степени зависит от характера ваших входных данных. Если вы можете «перестать искать» списки определенной длины, когда вы видели более длинный номер и, существует только конечное количество списков каждой длины, тогда вы можете пройти по длине в порядке возрастания, сортировать их и конкатенировать результаты. Нечто подобное должно работать:

listsUptoLength n xss = takeWhile (\xs -> length xs <= n) $ xss 
listsUptoLength' n [] = [] 
listsUptoLength' n (xss:xsss) = case listsUptoLength n xss of 
    [] -> [] 
    xss' -> xss' : listsUptoLength' n xsss 
listsOfLength n xsss = concatMap (\xss -> (filter (\xs -> length xs == n) xss)) (listsUptoLength' n xsss) 

sortInfinite xsss = concatMap (\n -> sort . nub $ (listsOfLength n xsss)) [0..] 

f xs y = [xs ++ replicate n y | n <- [1..]] 
test = [ map (\x -> [x]) ['a'..'e'], f "" 'a', f "" 'b', f "b" 'a', f "a" 'b' ] ++ [f start 'c' | start <- f "" 'a'] 

(имена, вероятно, может быть выбран, чтобы быть более освещая :)

Я угадывание вы работаете с регулярными выражениями, так что я думаю, что-то вроде этого можно заставить работать; Повторяю просьбу об увеличении фона!

Answer 5

Спасибо всем за их вклад и извините за поздний ответ. Оказывается, я просто подошел к проблеме неправильно. Я пытался сделать то, что показал Яирчу, но я использовал встроенную функцию length, чтобы выполнить слияние, но длина не работает по бесконечному списку по очевидным причинам. В любом случае, я решил свою проблему, отсортировав, как я создал список на ходу, а не на конечный результат. Интересно, какие другие языки предлагают бесконечные списки? Такая странная, но полезная концепция.

Answer 6

Вот алгоритм, который пусть вам онлайн вид:

это не является эффективным, но достаточно ленив, чтобы позволить вам GOTO разных поколений сортировки, даже если вы сортировать бесконечные списки. Это хороший трюк, но не очень удобный. Например сортировка бесконечного списка [10.9 ..]:

*Main> take 10 $ sortingStream [10,9..] !! 0 
[9,8,7,6,5,4,3,2,1,0] 
*Main> take 10 $ sortingStream [10,9..] !! 1 
[8,7,6,5,4,3,2,1,0,-1] 
*Main> take 10 $ sortingStream [10,9..] !! 2 
[7,6,5,4,3,2,1,0,-1,-2] 
*Main> take 10 $ sortingStream [10,9..] !! 3 
[6,5,4,3,2,1,0,-1,-2,-3] 
*Main> take 10 $ sortingStream [10,9..] !! 4 
[5,4,3,2,1,0,-1,-2,-3,-4] 
*Main> take 10 $ sortingStream [10,9..] !! 1000 
[-991,-992,-993,-994,-995,-996,-997,-998,-999,-1000] 

Как вы можете видеть, что сортировка улучшает каждое поколение.Код:

produce :: ([a] -> [a]) -> [a] -> [[a]] 
produce f xs = f xs : (produce f (f xs)) 


sortingStream :: (Ord a) => [a] -> [[a]] 
sortingStream = produce ss 

ss :: (Ord a) => [a] -> [a] 
ss [] = [] 
ss [x] = [x] 
ss [x,y] | x <= y = [x,y] 
      | otherwise = [y,x] 
ss (x:y:xs) | x <= y = x: (ss (y:xs)) 
      | otherwise = y:(ss (x:xs))