构建无限列表的排序无限列表

Question

我知道对无限列表进行排序是不可能的，但我正试图为n个数的倍数的无限递增列表写一个定义。

我已经有这个功能了

multiples :: Integer -> [Integer]
multiples n = map (*n) [1..]

它返回n的无限倍数列表。但现在我想构建一个函数，给定一个整数列表返回列表中所有数字的倍数的无限递增列表。所以函数multiplesList:：[Integer]-

我是Haskell的新手，我正在努力解决这个问题。我想我应该使用foldr或map，因为我必须对输入中的所有数字应用倍数，但是我不知道怎么做。我不能把所有列表混合成一个。

如果有人能帮我，我将不胜感激。

非常感谢。




Answer 1

我们可以很容易地将两个无限列表按位置编织在一起，每一步从每个列表中提取一个元素，

weave (x:xs) ys = x : weave ys xs

或者我们可以每次使用更长的前缀，

-- warning: expository code only
weaveN n xs ys = take n xs ++ weaveN n ys (drop n xs)

但假设两个列表不仅是无限的，而且是严格递增的（即列表中没有重复项），我们可以通过相反列表的头值来引导前缀的选取：

umerge :: Ord a => [a] -> [a] -> [a]
-- warning: only works with infinite lists
umerge xs (y:ys) = a ++ [y | head b > y ] ++ umerge ys b
  where
    (a,b) = span (< y) xs

因此，这是唯一合并操作的一种可能编码（“唯一”意思是，其输出中不会有任何重复项）。

在测试中，它似乎按预期工作：

> take 20 $ umerge [3,6..] [5,10..]
[3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,36,39,40,42]

> [3,6..42] ++ [5,10..42] & sort & nub
[3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,36,39,40,42]

> [ p | let { ms :: [Integer] ; ms = takeWhile (< 25^2) $
          foldl1 umerge [[p*p,p*p+p..] | p <- [2..25]] },
    p <- [2..545],  not $ elem p ms ]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
 97,101,...........,499,503,509,521,523,541]

> length it
100

通过一个巧妙的小调整（由于理查德·伯德在梅利莎·奥尼尔的JFP文章中看到），它甚至可以用来折叠一个无限的升序列表，前提是它是按照头部元素的升序排序的，所以第一个参数的头部保证是输出中的第一个，因此可以在没有测试的情况下生成：

umerge1 :: Ord a => [a] -> [a] -> [a]
-- warning: only works with infinite lists
--          assumes x < y
umerge1 (x:xs) ~(y:ys) = x : a ++ [y | head b > y ] ++ umerge ys b
  where
    (a,b) = span (< y) xs

现在

> take 100 [ p | let { ms :: [Integer] ;
          ms = foldr1 umerge1 [[p*p,p*p+p..] | p <- [2..]] },
    p <- [2..],  not $ elem p $ takeWhile (<= p) ms ]

[2,3,5,7,11,13, ...... 523,541]

同样的计算无限期地起作用。

对观众中的文字主义者来说：是的，在这里叫elem是非常糟糕的事情。希望操作人员自己也能认识到这一点，但不幸的是，我觉得有必要发表这一声明，从而无意中向他们透露了这一点，不幸的是，剥夺了他们本应获得的哈哈时刻。

_{此外，umerge1的定义可以大大简化。同样，这是留给OP自己去发现的。（同样，如果我不是被迫说这句话来向他们揭示这一点的话，对他们来说，这会好得多——自己去寻找一些东西会更有力量和满足感）}

_{^（*），并自行寻找更有效的方法来取代它。不，这段代码并不是解决他们问题的最佳方案}

Answer 2

你走在正确的道路上。下面的评论是一个你可以完成的模板。

multiples :: Integer -> [Integer]
multiples n = map (*n) [1..]

-- This is plain old gold recursion.
mergeSortedList :: [Integer] -> [Integer] -> [Integer]
mergeSortedList [] xs = undefined
mergeSortedList xs [] = undefined
mergeSortedList (x:xs) (y:ys)
    | x < y  = x:mergeSortedList xs (y:ys) -- Just a hint ;)
    | x == y = undefined
    | x > y  = undefined

multiplesList :: [Integer] -> [Integer]
multiplesList ms = undefined -- Hint: foldX mergeSortedList initial xs
                             -- Which are initial and xs?
                             -- should you foldr or foldl?