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

Question

我知道不可能对无限列表进行排序，但我正在尝试编写 n 倍数的无限递增列表的定义。

我已经有这个功能了

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

即 returns n 倍数的无限列表。但现在我想构建一个函数，给出一个列表 Integers returns 列表中所有数字的倍数的递增无限列表。所以给定输入 [3,5] 的函数 multiplesList :: [Integer] -> [Integer] 应该产生 [3,5,6,9,10,12,15,18,20,....].

我是 Haskell 的新人，我正在为此苦苦挣扎。我想我应该使用 foldr 或 map 因为我必须将 multiples 应用于输入中的所有数字，但我不知道如何。我无法将所有列表混合成一个。

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

谢谢！

Answer 1

你走对了。下面的评论是您可以完成的模板。


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?

Answer 2

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

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

并且通过巧妙的小调整（由于理查德·伯德，如 Melissa O'Neill 在 the JFP article 中所见），它甚至可以用于折叠无限列表升序列表，前提是它按其头部元素的升序排序，因此第一个参数的头部保证是输出中的第一个，因此无需测试即可生成：

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 是非常糟糕的事情 .希望 OP 应该自己认识到这一点，^(*) 但不幸的是，我觉得有必要发表这个声明，因此无意中向他们透露了这一点，剥夺了他们的幸福-不幸的是，赢得了 a-ha 时刻。}

_{另外，umerge1的定义可以彻底简化。同样，这留给 OP 自行发现。（再一次，如果我不是被迫向他们透露这句话的话，这对他们来说会好得多——自己找到一些东西会更有力量和满足感）}

_{^(*) 并自行寻找用更有效的方法替换它的方法。不，此代码不是作为他们问题的最佳解决方案呈现的。}

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

Build sorted infinite list of infinite lists

haskell

functional-programming

fold