Haskell list comprehension type error: Couldn't match expected type ‘Float’ with actual type ‘Int’

Question

我正在尝试创建一个毕达哥拉斯三元组列表，即每个包含 (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 转换为a Float 在列表理解过程中的某个时刻。

与[1..5]相比，[1..fromIntegral n]看起来不是特别简洁或优雅，我应该使用另一种方法来解决或避免这个问题吗？

Answer 1

which indicates to me that the variable n is somehow transformed from an Int to a Float at some point during the list comprehension.

恰恰相反。您已在类型签名中将 n 声明为 Int，这将永远修复它。这里的Float是hyp x y。您在问 hyp x y 是否是 [1..n] 的 element。 elem :: a -> [a] -> Bool，因此只有当您拥有与列表元素类型相同的对象时才问这个问题才有意义。这就是不匹配：要将 elem 与 Float 和列表一起使用，您需要该列表是 [Float]。但由于列表是 [1..n]，它显然是 [Int].

至于您应该采取哪些不同的做法，我建议您完全不要为此函数使用任何浮点运算。对于您正在使用的秤来说可能没问题，但我太担心舍入误差会给我错误的答案。您可以搜索 a^2 + b^2 == c^2.

这样的三元组，而不是搜索 sqrt (a^2 + b^2) 是一个整数的对，这需要一个 sqrt

Answer 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]]
                                        ------- 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 秒。

另请参阅：Empirical orders of growth

枚举两个范围的笛卡尔积是二次的；枚举三个范围的笛卡尔积是立方的。这才有意义。

另一种甚至可能比这里的第一种方法更快的方法根本不会搜索任何三元组，而是生成他们顺序.

Haskell list comprehension type error: Couldn't match expected type ‘Float’ with actual type ‘Int’

Haskell list comprehension type error: Couldn't match expected type ‘Float’ with actual type ‘Int’

haskell

list-comprehension

typeerror