我正试图创建勾股三元组的列表，也就是说，每个元组都包含(x, y, z)，使得x^2 + y^2 = z^2和x、y、z在[1..n]的范围内。
我在列表理解保护程序中遇到了一个类型错误。这是我的代码：
-- integer square root
isqrt :: Int -> Float
isqrt = sqrt . fromIntegral
-- hypotenuse
hyp :: Int -> Int -> Float
hyp x y = isqrt (x^2 + y^2)
-- pythagorean triplets in range [1..n]
pyths :: Int -> [(Int, Int, Int)]
pyths n = [(x, y, truncate (hyp x y)) | x <- [1..n], y <- [x..n], elem (hyp x y) [1..n]]
错误如下：
• Couldn't match expected type ‘Float’ with actual type ‘Int’
• In the expression: n
In the second argument of ‘elem’, namely ‘[1 .. n]’
In the expression: elem (hyp x y) [1 .. n]
|
11 | pyths n = [(x, y, truncate (hyp x y)) | x <- [1..n], y <- [x..n], elem (hyp x y) [1..n]]
|
我可以通过将我的防护从elem (hyp x y) [1..n]编辑为elem (hyp x y) [1..fromIntegral n]来解决这个错误，这向我表明，在列表理解过程中的某个时刻，变量n以某种方式从Int转换为Float。
与[1..5]相比，[1..fromIntegral n]看起来并不是特别简洁或优雅，我是否应该使用其他方法来解决或避免这个问题？
这向我表明，在列表理解过程中的某个时刻，变量n以某种方式从Int转换为Float。
恰恰相反。您已经在类型签名中将n声明为Int，这将永远修复它。这里的Float就是hyp x y。你在问hyp x y是否是[1..n]的elem元素。elem :: a -> [a] -> Bool，所以只有当你有一个与列表元素类型相同的对象时，才有意义问这个问题。这就是不匹配的地方：要将elem与Float和列表一起使用，需要该列表为[Float]。但由于列表是[1..n]，所以它显然是[Int]。
至于你应该做什么不同的事情，我建议这个函数不要使用任何浮点运算。也许这对你正在使用的天平来说很好，但我太担心舍入错误会给我错误的答案。您可以搜索a^2 + b^2 == c^2这样的三元组，而不是搜索sqrt (a^2 + b^2)是一个需要sqrt的整数对。
以下是一些可能的代码重写步骤，
-- pythagorean triplets in range [1..n]
pyths :: Int -> [(Int, Int, Int)]
pyths n =
= [(x, y, truncate (hyp x y)) | x <- [1..n], y <- [x..n],
elem (hyp x y) [1..n]]
------- no good
= [(x, y, truncate h) | x <- [1..n], y <- [x..n]
, let h = (hyp x y)
, elem h [1..n]] -- still no good
= [(x, y, truncate h) | x <- [1..n], y <- [x..n]
, let h = sqrt . fromIntegral $ (x^2 + y^2)
, elem h [1..n]]] -- still not
= [(x, y, h) | x <- [1..n], y <- [x..n]
, let h = truncate . sqrt . fromIntegral $ (x^2 + y^2)
, h^2 == x^2 + y^2 -- truncate, and test...
, elem h [1..n]] -- yep!
= [(x, y, h) | x <- [1..n], y <- [x..n]
, let h = truncate . sqrt $ fromIntegral (x^2 + y^2) + 0.01
, h^2 == x^2 + y^2
, h <= n]
突然它开始工作了。它快吗？让我们看看，
> pyths 100 & length
52
(0.06 secs, 0 bytes)
> pyths 200 & length
127
(0.09 secs, 105081448 bytes)
> pyths 500 & length
386
(0.61 secs, 731602904 bytes)
> pyths 1000 & length
881
(2.31 secs, 2926682600 bytes)
> logBase 2 (231/61)
1.9210117038531713
所以它只是关于二次的。有道理——(x,y)对的枚举已经是这样了，并且直接计算h并用它测试等式，对于每个对来说都是O(1(。
但是为每个(x,y)组合搜索满足等式的h呢？就性能而言，这是个好主意吗？
ps :: Int -> [(Int, Int, Int)]
ps n = [(x, y, h) | x <- [1..n], y <- [x..n], h <- [y..n] , h^2 == x^2 + y^2]
> ps 100 & length
52
(0.41 secs, 486358048 bytes)
> ps 200 & length
127
(2.89 secs, 4268474328 bytes)
> logBase 2 (289/41)
2.8173736778825953 -- almost cubic!
> 0.41 * 10 ** 2.82
270.88431368311427
> 2.89 * 5 ** 2.82
270.39163693305665
这个版本运行到1000的预计时间是270秒，而不是上面最后一次重写的2.3秒。
- 另请参阅：经验增长顺序
枚举两个范围的笛卡尔乘积是二次的；枚举三个范围的笛卡尔乘积是三次的。这很有道理。
另一种可能比第一种更快的方法根本不是搜索任何三元组，而是按的顺序生成它们。