CODEWITHSUNDEEP
haskell
spicy boi
spicy boi

Reputation: 33

Implementing the Bresenham Algorithm

Hi I'm trying to write some basic code to implement the Bresenham Algorithm but I'm stuck trying to use round and /. My code is:

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

I keep getting the No instance for (Fractional Int) arising from a use of ‘/’ and No instance for (RealFrac Int) arising from a use of ‘round’ errors occuring. 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?

Upvotes: 3

Views: 240

Answers (1)

Cubic
Cubic

Reputation: 15683

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?

Yes, your understanding is basically correct but you made a small oversight.

Here is your code formatted slightly differently:

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

this is (because + binds stronger than $) equivalent to:

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

The problem here is actually neither round nor /, it's your + y1 at the end. Because y1 is already known to be Int, the type checker tries to unify 

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

with Int, which of course fails because / isn't allowed with Int.

The solution is to add another 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

Alternatively you could also wrap the everything before + y1 - including the round - in parentheses, that would work too.

Now the reason this wasn't caught earlier is because fromIntegral can actually convert integer types to any number type... including themselves. So in this case, because of how the expression was written the typechecker inferred that you meant fromIntegral to convert Int to... Int again. Which is not what you meant, but the compiler doesn't know that.

If we add a small helper function:

toDouble :: Int -> Double
toDouble = fromIntegral

and use it in your definition instead of fromIntegral

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

to force the conversion, we actually get a more helpful error message:

• 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
        ^^

Upvotes: 5

Related Questions