haskell - Haskell List 理解无限列表问题

Question

我正在尝试学习 Haskell 和理解列表，但找不到解决方案：

mylist = [x*y | x <- [1..], y <- [1..]]

经过我的试验，结果是这样的

mylist = [1,2,3,4,5,...]

因为在列表推导中，x取值1，然后y反复更改值。

但我的目标是完成不同的任务，以便获得以下结果：

mylist = [1,2,2,4,3,3,6.....]

我的意思是我想要混合组合而不是分开，因为我有一个严重的问题来获得合适的结果。

我将举一个更具体的例子。

我想要一个包含这种形式的所有数字的列表：

num = 2^x * 3^y 

x并且y必须取所有值>= 0。

我的方法如下：

powers = [2^x * 3^y | x <- [0..], y <- [0..]]

但这样我只取 3 的幂，因为x一直是 0。

我试过这个

multiples = nub (merge (<=) powers2 powers3)
powers3 = [2^x * 3^y | x <- [0..], y <- [0..]]
powers2 = [2^x * 3^y | y <- [0..], x <- [0..]]

以便合并不同的值，但再次合并值 6,12 等。丢失 - 结果是这样的：

mylist = [1,2,3,4,8,9,16,27,32,64,81...]

标签： haskelllist-comprehensioninfinitehamming-numberssmooth-numbers

Answer 1

您显示的代码，

multiples = nub (merge (<=) powers2 powers3)
powers3 = [2^x * 3^y | x <- [0..], y <- [0..]]
powers2 = [2^x * 3^y | y <- [0..], x <- [0..]]

相当于

powers3 = [2^x * 3^y | x <- [0], y <- [0..]]
        = [2^0 * 3^y | y <- [0..]]
        = [3^y | y <- [0..]]
powers2 = [2^x * 3^y | y <- [0], x <- [0..]] 
        = [2^x * 3^0 | x <- [0..]]
        = [2^x | x <- [0..]]

所以你只产生2和3的幂，没有任何混合倍数。因此，保证流中没有重复项，并且nub没有必要。当然，它是不完整的。

但是让我们从另一个角度来看它。评论中建议用这些数字创建一个 2D 网格：

mults23_2D = [[2^x * 3^y | y <- [0..]] | x <- [0..]]
{-
   1   3   9   27  81  ...
   2   6  18   54  ...
   4  12  36  108  ...
   8  24  72  ...
  16  ...
  .......     
-}

现在我们正在取得进展。至少现在没有一个被跳过。我们只需要了解如何将它们加入一个排序的、不断增加的数字流中。简单concat的当然不行。我们需要按顺序合并它们。一个众所周知的函数merge可以做到这一点，前提是参数已经排序，增加列表。

生产的每一行都已经按递增顺序排列，但它们的数量是无限的。不怕，foldr能行。我们定义

mults23 = foldr g [] [[2^x * 3^y | y <- [0..]] | x <- [0..]]
  -- foldr g [] [a,b,c,...] == a `g` (b `g` (c `g` (....)))
 where
 g (x:xs) ys = 

这里有点棘手。如果我们定义g = merge，我们将有一个失控的递归，因为每个merge人都想知道它的“正确”（第二个）参数流的头元素。

为了防止这种情况，我们立即生成最左边的元素。

                x : merge xs ys

就是这样。