在Haskell中对无限列表进行燕尾迭代

我想迭代2(或3)个无限列表,找到满足条件的"最小"对,如下所示:

until pred [(a,b,c) | a<-as, b<-bs, c<-cs]
  where pred (a,b,c) = a*a + b*b == c*c
        as = [1..]
        bs = [1..]
        cs = [1..]

在a == b == 1整个计划的运行过程中,上述情况不会太长 .有没有一种很好的方法可以解决问题,例如构建无限序列[(1,1,1),(1,2,1),(2,1,1),(2,1,2),(2,2,1),(2,2,2),(2,2,3),(2,3,2),..]？

额外奖励:是否有可能推广到n元组？

欧米茄,有一个monad .

Prelude> let as = each [1..]
Prelude> let x = liftA3 (,,) as as as
Prelude> let x' = mfilter (\(a,b,c) -> a*a + b*b == c*c) x
Prelude> take 10 $ runOmega x'
[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15),(12,9,15),(8,15,17),(15,8,17)]

使用它的应用功能,您可以推广到任意元组:

quadrupels = (,,,) <$> as <*> as <*> as <*> as   -- or call it liftA4

但是:当然,仅这一点并不能消除重复.它只给你正确的对角化.也许你可以将monad理解与像Thomas这样的方法一起使用,或者只使用另一种mfilter传递(b /= c在这种情况下限制为).

列表理解是解决此类问题的极好(和简洁)方法.首先,你知道你想要的所有组合都(a,b,c)可能满足a^2 + b^2 = c^2- 一个有用的观察是(只考虑正数)总是如此a <= c && b <= c.

为了生成我们的候选人列表,我们可以说c范围从1无穷大a到b范围从1到c.

[(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c]]

要获得解决方案,我们只需要添加您想要的方程式作为后卫:

[(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c], a*a+b*b == c*c]

这是低效的,但输出是正确的:

[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15)...

有比盲测更多的原理方法可以解决这个问题.