如何在找到正确的三角形时使用Haskells懒惰

Question

我正在http://learnyouahaskell.com/starting-out上关注(优秀的)Haskell教程,并尝试使用正确的三角形示例:

> let triangles = [(a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2]

按照预期运行我得到的:

> triangles 
[(4,3,5),(3,4,5),(8,6,10),(6,8,10)]

现在,我想尝试使用无限列表:

> let triangles = [(a,b,c) | c <- [1..], b <- [1..], a <- [1..], a^2 + b^2 == c^2] 

但是当我尝试它时,像:

> take 2 triangles

...程序只运行并运行,没有输出.我究竟做错了什么？我认为Haskells懒惰会导致它找到两个第一个三角形然后停止？

Answer 1

嗯,懒惰不是问题.这是您在列表中迭代变量的顺序.

基本上会发生什么:

1. c绑定为1
2. b必然是1
3. a必然是1
4. 检查方程式
5. a必然是2
6. 检查方程式
7. a必然是3
8. 检查方程式

它会永远持续下去.

因此,生成器继续迭代和绑定值a,因为它不知道您需要停止并增加b或c更改.

所以你需要以更平衡的方式生成元组.

例如,您可以使用此方法:

triplesN :: Int -> [(Int, Int, Int)]
triplesN n = [(i, j, n - i - j) | i <- [1..n - 2], 
                                  j <- [1..n - i - 1], i>=j, 
                                  let k = n - i - j,   j>=k]

isTriangle (a, b, c) = a^2 == b^2 + c^2

triangles = filter isTriangle $ concatMap triplesN [1..]

tripleN用sum生成所有有序三元组n.通过在所有自然数上映射此函数,我们实际上获得了所有有序对的流.最后,我们只过滤那些三角形的三元组.

通过做:

take 10 triangles

我们得到:

[(5,4,3),(10,8,6),(13,12,5),(15,12,9),(17,15,8),(20,16,12),(25,24,7),(25,20,15),(26,24,10),(29,21,20)]

Answer 2

您可能有兴趣阅读sigfpe博客上的文章A Monad for Combinatorial Search.

他定义了一个名为惩罚列表或PList的新monad ,类似于列表monad,但它也有更复杂解决方案的惩罚概念.当您组合PLists时,生成结果的顺序是最小罚分 - >最大罚分.

在您的示例中,与整数关联的惩罚可能等于整数的大小,与元组关联的惩罚是其元素的惩罚之和.因此元组的(3,4,5)惩罚为3 + 4 + 5 = 12,而元组的(5,12,13)惩罚为5 + 12 + 13 = 30.

使用列表monad,生成的元组的顺序是

(1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,1,5) ...

你永远不会看到一个不是形式的元组(1,1,x).使用PList monad,产生的元组可能是

(1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,1,3), (1,3,1), (3,1,1), (1,2,2) ...

在'较大'之前生成所有'较小'元组.

对于您的特定问题,此解决方案过度,但在更复杂的问题中它非常有用.