haskell - 整理 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 50需要 19 秒。

任何速度优化都很好，但如果不是的话，我使用的简单方法就足够了。

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)