在Haskell中整理列表理解

Question

所以我试图在Haskell中生成一个出租车编号列表.出租车编号是可以用两种不同方式写成两个不同立方体之和的数字 - 最小的是 1729 = 1^3 + 12^3 = 9^3 + 10^3.

现在,我只是生成了四个"组成"出租车编号的数字,例如(1,12,9,10),并被告知使用列表理解(我不太熟悉) ).此函数将生成所有4元组,其中最大数字最多为n:

taxi n = [(a,b,c,d) | a <- [1..n], b <- [1..n], c <- [1..n], d <- [1..n], a^3 + b^3 == c^3 + d^3, a < b, a < c, c < d]

但是,由于以下几个原因,它很麻烦:

• a,b,c,d的域都是相同的,但我无法弄清楚如何简化这段代码,因此[1..n]只写一次.
• 我想要一个没有上限的无限列表,所以我可以让程序尽可能长时间运行并在我请求时终止它.很明显,如果我只是设置a <- [1..]等等,那么程序永远不会最终评估任何东西.
• 程序非常慢:只需taxi 5019秒.

任何速度优化也都会很好,但如果不是我使用的天真方法就足够了.

Answer 1

你的约束意味着a < c < d < b.所以让我们b运行最外层,让其他人在适当的较低范围内运行:

taxi n = [ (a,b,c,d) | b <- [1..n],
                       d <- [1..b-1],
                       c <- [1..d-1],
                       a <- [1..c-1],
                       a^3 + b^3 == c^3 + d^3 ]

为了无限,只需使用b <- [1..].

另一个重大改进是从其他三个计算四个变量中的一个:

taxi = [ (a,b,c,d) | b <- [1..],
                     c <- [1..b-1],
                     a <- [1..c-1],
                     let d3 = a^3 + b^3 - c^3,
                     let d = round(fromIntegral(d3)**(1/3)),
                     c < d,
                     d^3 == d3 ]

像你一样taxi 50在GHCi中进行基准测试:set +s:

Yours:          (16.49 secs, 17,672,510,704 bytes)
My first:        (0.65 secs,    658,537,184 bytes)
My second:       (0.09 secs,     66,229,376 bytes)  (modified to use b <- [1..n] again)
Daniel's first:  (1.94 secs,  2,016,810,312 bytes)
Daniel's second: (2.87 secs,  2,434,309,440 bytes)