Создание отсортированного списка всех возможных совпадений

Question

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

Таким образом, результирующий список должен быть

[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)...` 

Вот мое решение.

coprimes :: [(Int, Int)] 
coprimes = sortBy (\t1 t2 -> if uncurry (+) t1 <= uncurry (+) t2 then LT else GT) $ helper [2..] 
    where helper xs = [(x,y) | x <- xs, y <- xs, x < y, gcd x y == 1] 

Проблема заключается в том, что я не могу взять n первые пары. Я понимаю, что сортировка не может быть выполнена в бесконечных списках.

Но как я могу генерировать одну и ту же последовательность ленивым способом?

Answer 1

Хотя, вероятно, это не самый оптимальный способ работы, если вы сначала генерируете все возможные пары, а затем фильтруете их.

Так, используя ваши критерии:

pairs :: [(Integer,Integer)] 
pairs = [ (i,l-i) | l <- [1..], i <- [1..l-1] ] 

coprimes :: [(Integer,Integer)] 
coprimes = [ (i,j) | (i,j) <- pairs, 1 < i, i < j,gcd i j == 1] 

производит

λ> take 10 coprimes 
[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)] 

теперь, конечно, вы можете поместить некоторые вещи 1 < i и i < j приходит на ум в pairs определение или даже присоединиться к ним, но я думаю, здесь более очевидно то, что происходит

Answer 2

Как @Bakuriu предлагает, слияние бесконечного списка infini te списки - это решение, но дьявол находится в деталях.

diagonal функция из universe-base пакета может сделать это, так что вы могли бы написать:

import Data.Universe.Helpers 

coprimes = diagonal [ go n | n <- [2..] ] 
    where go n = [ (n,k) | k <- [n+1..], gcd n k == 1 ] 

Примечание - это не удовлетворяет критериям отсортированные, но я упоминаю это потому, что функции в этом пакете полезны знать, и реализовать функцию, например, diagonal, нелегко.

Если вы хотите, чтобы написать свой собственный, рассмотреть разлагающихся бесконечную сетку N х N (где N является натуральные числа) в диагоналей:

[ (1,1) ] ++ [ (1,2), (2,1) ] ++ [ (1,3), (2,2), (3,1) ] ++ ... 

и фильтрации этот список.

Answer 3

Вот возможное решение следующего главы 9 Ричард птичьего мышления Функционально в Haskell:

coprimes = mergeAll $ map coprimes' [2..] 

coprimes' n = [(n, m) | m <- [n+1..], gcd m n == 1] 

merge (x:xs) (y:ys) 
    | s x < s y = x:merge xs (y:ys) 
    | s x == s y = x:y:merge xs ys 
    | otherwise = y:merge (x:xs) ys 
    where s (x, y) = x+y 

xmerge (x:xs) ys = x:merge xs ys 

mergeAll = foldr1 xmerge 

И результат:

> take 10 $ coprimes 
[(2,3),(2,5),(3,4),(3,5),(2,7),(4,5),(3,7),(2,9),(3,8),(4,7)] 

Обратите внимание, что естественное определение mergeAll будет foldr1 merge , но это не работает, потому что он попытается найти минимум первых элементов всего списка перед возвратом первого элемента, и, следовательно, вы окажетесь в бесконечном петля. Однако, поскольку мы знаем, что списки находятся в порядке возрастания, а минимальный - первый элемент первого списка, xmerge делает трюк.

---

Примечание: это решение, как представляется, значительно (например, 2 порядка величин) медленнее, чем Carsten «наивный» ответ. Поэтому я советую избегать этого, если вы заинтересованы в производительности. Тем не менее, это все еще интересный подход, который может быть эффективным в других ситуациях.

Answer 4

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

Итак, мы генерируем восходящие пары суммы и первого элемента и сохраняем только взаимные числа. Легкий дрянной!

[ (first, second) 
| sum <- [3..] 
, first <- [2..sum `div` 2] 
, let second = sum-first 
, gcd first second == 1 
]