如何的每一个元素与另一个列表中的每个元素在Haskell划分在一个列表

Question

假设我有一个无限列表A = [1..]我想每个元素在A在列表B = [1..10]所有元素划分如果在列表A任何元素除尽所有B中的元素需要打印。 我需要继续这个，直到我得到10个这样的数字。

下尝试没有工作：

print(minimum([x | x <- [1..], y <- [1..10], rem x y == 0])) 

Answer 1

你尝试

您写道：

print(minimum([x | x <- [1..], y <- [1..10], rem x y == 0])) 

现在，这不会有以下几个原因工作：

1. 它会将x添加到列表理解列表中，因为有任何元素y在[1..10]中除以x。此外，对于任何此类y，我们将一次添加x。所以给定x是6，它会将它添加三次四次，因为6可以被1,2,3和6除尽;
2. 结果将是一个无限列表，因此无法计算该列表的最小值。这是因为Haskell不知道列表已经被排序，因此最小值只是第一个元素。你可以采取第一个元素head;
3. minimum只会产生一个元素，但你要第10

暴力方法

首先，我们可以使用列表解析生成所有这些数字（任意名单as和bs）：

divide_all as bs = [a | a <- as, all ((0 ==) . mod a) bs] 

所以这里的名单理解迭代as环节都分配给a。接下来我们有一个过滤器all ((0 ==) . mod a) bs，这是一个紧凑的形式all (\b -> mod a b == 0) bs。因此它检查是否b中的所有成员bs,mod a b == 0（因此a可由b分割）。如果过滤器得到满足，则我们将a（在列表理解的头部）添加到结果中。请注意，这样的列表是懒散地构建的，因此as具有无限数量的元素的事实不是问题。

现在我们可以使用take :: Int -> [a] -> [a]采取这些数字的第一个10，从而打印这些：

mapM_ print (take 10 $ divide_all [1..] [1..10]) 

它打印：

Prelude> mapM_ print (take 10 $ divide_all [1..] [1..10]) 
2520 
5040 
7560 
10080 
12600 
15120 
17640 
20160 
22680 
25200 

最小公倍数

上述方法效率不高：对于a的每个元素，我们需要检查它是否可以用b的每个元素进行分割。我的机器用了2.16秒来计算这个列表的第1000个元素，用了10.21秒找到第5000个元素。

可加快我们的最后一个，通过计算最小公倍数（LCM）的b所有的元素，并检查是否一个数是由LCM可分：所以现在

divide_all as bs = [a | a <- as, mod a lcmb == 0] -- optimized version 
    where lcmb = foldr1 lcm bs 

我们只需要执行一次支票。现在计算第1000个元素需要0.95秒，计算第5000个元素需要4.54秒。

如果as = [1..]

如果as被称为是[1..]我们可以显着提升该代码，因为我们知道，a的元素是lcmb倍数。因此，我们可以放下as参数，并使用：

divide_all bs = [lcmb*a | a <- [1..]] -- optimized version 
    where lcmb = foldr1 lcm bs 

现在计算的第1000个元素需要0.01秒，并计算第5000元0.03秒。但当然这只有在假设的情况下才有效。

Answer 2

let divcheck = (take 10 .) . filter . flip (all . ((0 ==) .) . mod) 

divcheck [1..10] [1..] 
-- [2520,5040,7560,10080,12600,15120,17640,20160,22680,25200] 

divcheck [1,2,3] [1..] 
-- [6,12,18,24,30,36,42,48,54,60]