合格Haskell列表解析的高效替代方案

Question

作为Haskell中合格列表解析的一个例子，Learn You a Haskell教程提供了一个列表理解的例子，该列表理解建议寻找具有给定边界p的正确三角形的一般方法，表示为元组：

λ> let rightTriangles p = [ (a,b,c) | c <- [1..(quot p 2)], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a + b + c == p] 

但是，这种方法变得非常慢作为p变大。

是否有一个普遍更快，但惯用的Haskell方式来完成大p相同的事情？

Answer 1

这些评论意味着你真正需要的是更好的算法。

但是，让我们尝试不同的东西，看看我们可以对当前代码什么的优化：

let rightTrianglesCubic p = [ (a,b,c) | c <- [1..quot p 2], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a + b + c == p] 

首先，请注意我们如何遍历的[1..b]所有的值，直到我们找到一个地方a + b + c == p。但是，在保存的唯一价值是a = p - b - c，所以我们完全可以跳过循环，并制作成二次算法如下：

let rightTrianglesQuadraticA p = [ (a,b,c) | c <- [1..quot p 2], b <- [1..c], let a = p - b - c, a^2 + b^2 == c^2] 

有一个小问题，这种方法：

λ rightTrianglesCubic 120 
[(30,40,50),(24,45,51),(20,48,52)] 
λ rightTrianglesQuadraticA 120 
[(40,30,50),(30,40,50),(45,24,51),(24,45,51),(48,20,52),(20,48,52),(0,60,60)] 

我们得到一些额外的结果！这是因为我们忽略了a <- [1..b]所做的隐含条件，即1 <= a和a <= b。因此，让我们添加这些回

let rightTrianglesQuadraticB p = [ (a,b,c) | c <- [1..quot p 2], b <- [1..c], let a = p - b - c, a^2 + b^2 == c^2, 1 <= a, a <= b] 

而现在我们得到正确的答案：

λ rightTrianglesQuadraticB 120 
[(30,40,50),(24,45,51),(20,48,52)] 

由于b每个值都有一个唯一的a，条件1 <= a和a <= b 可以表述为条件在b。 1 <= a与1 <= p - b - c或 b <= p - c - 1相同。 a <= b与p - b - c <= b或p - c <= 2*b或 div (p - c + 1) 2 <= b相同。

这让我们缩小环路b <- [1..c]界限：

let rightTrianglesQuadraticC p = [ (a,b,c) | c <- [1..quot p 2], b <- [max 1 (div (p - c + 1) 2) .. min c (p - c - 1) ], let a = p - b - c, a^2 + b^2 == c^2] 

我们甚至可以通过提的是，为了a < b < c与a+b+c == p，我们必须收缩对c <- [1..quot p 2]边界c > p/3：

let rightTrianglesQuadraticD p = [ (a,b,c) | c <- [1 + quot p 3..quot p 2], b <- [max 1 (div (p - c + 1) 2) .. min c (p - c - 1) ], let a = p - b - c, a^2 + b^2 == c^2] 

这是关于优化这个特定的代码可以去。为了进一步提高性能，我们需要完全切换算法。