haskell - 实现 Bresenham 算法

Question

嗨，我正在尝试编写一些基本代码来实现 Bresenham 算法，但我一直在尝试使用 round和/ 。我的代码是:

bresenhamAlgorithm :: Coord -> Coord -> Int -> Int
bresenhamAlgorithm (x1, y1) (x2, y2) x'= round $ (fromIntegral ((y2 - 
y1) * (x' - x1)) / fromIntegral (x2 - x1)) + y1

我不断收到 No instance for (Fractional Int) arising from a use of ‘/’和No instance for (RealFrac Int) arising from a use of ‘round’发生错误。我不明白，因为我相信 fromIntegral 会将分子和分母转换为小数，从而允许使用 /操作？

Answer 1

I don't understand as I believed that fromIntegral would convert the numerator and denominator to fractionals which would allow for the use of the / operation?

是的，你的理解基本上是正确的，但你犯了一个小疏忽。

<小时/>

以下代码的格式略有不同:

bresenhamAlgorithm :: Coord -> Coord -> Int -> Int
bresenhamAlgorithm (x1, y1) (x2, y2) x'= round $
  (
    fromIntegral ((y2 - y1) * (x' - x1)) 
  / fromIntegral (x2 - x1)
  ) + y1

这(因为 + 绑定(bind)比 $ 更强)相当于:

bresenhamAlgorithm :: Coord -> Coord -> Int -> Int
bresenhamAlgorithm (x1, y1) (x2, y2) x'= round (
  (
    fromIntegral ((y2 - y1) * (x' - x1)) 
  / fromIntegral (x2 - x1)
  ) + y1)

这里的问题实际上既不是round也不是/，而是你最后的+ y1。由于 y1 已知为 Int，因此类型检查器会尝试统一

fromIntegral ((y2 - y1) * (x' - x1)) / fromIntegral (x2 - x1)

与 Int 一起使用，这当然会失败，因为 / 不允许与 Int 一起使用。

解决方案是添加另一个 fromIntegral:

bresenhamAlgorithm :: Coord -> Coord -> Int -> Int
bresenhamAlgorithm (x1, y1) (x2, y2) x'= round $
  (
    fromIntegral ((y2 - y1) * (x' - x1)) 
  / fromIntegral (x2 - x1)
  ) + fromIntegral y1 -- we need y1 as a fractional

或者，您也可以将 + y1 之前的所有内容 - 包括 round - 括在括号中，这也可以。

<小时/>

现在，这个问题没有被更早捕获的原因是因为 fromIntegral 实际上可以将整数类型转换为任何数字类型......包括它们自己。因此，在本例中，由于表达式的编写方式，类型检查器推断您的意思是 fromIntegral 再次将 Int 转换为... Int。这不是你的意思，但编译器不知道这一点。

如果我们添加一个小辅助函数:

toDouble :: Int -> Double
toDouble = fromIntegral

并在定义中使用它而不是 fromIntegral

bresenhamAlgorithm :: Coord -> Coord -> Int -> Int
bresenhamAlgorithm (x1, y1) (x2, y2) x'= round $
  (
    toDouble ((y2 - y1) * (x' - x1)) 
  / toDouble (x2 - x1)
  ) + y1

为了强制转换，我们实际上得到了一条更有帮助的错误消息:

• Couldn't match expected type ‘Double’ with actual type ‘Int’
• In the second argument of ‘(+)’, namely ‘y1’
  In the second argument of ‘($)’, namely
    ‘(toDouble ((y2 - y1) * (x' - x1)) / toDouble (x2 - x1)) + y1’
  In the expression:
    round
      $ (toDouble ((y2 - y1) * (x' - x1)) / toDouble (x2 - x1)) + y1

    ) + y1
        ^^