合格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] 

這是關於優化這個特定的代碼可以去。爲了進一步提高性能，我們需要完全切換算法。