合格的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 - cor一样 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]

我们甚至可以缩小界限c <- [1..quot p 2],注意为了a < b < c配合a+b+c == p,我们必须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]

这就是优化这个特定代码所能实现的.为了进一步提高性能,我们需要完全切换算法.