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

user_3826634 0
Viewed 175

I am attempting to create a list of pythagorean triplets, that is, a list of tuples that each contain (x, y, z) such that x^2 + y^2 = z^2 and x, y, z are in range [1..n].

I've run into what seems to be a type error inside my list comprehension guard. Here is my code:

-- 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]]

Here is the error:

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

I can resolve the error by editing my guard from elem (hyp x y) [1..n] to elem (hyp x y) [1..fromIntegral n], which indicates to me that the variable n is somehow transformed from an Int to a Float at some point during the list comprehension.

The [1..fromIntegral n] doesn't look particularly concise or elegant compared to [1..5], is there another method that I should be using to either resolve or avoid this problem?

typeerror list-comprehension haskell
2 Answers

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

Quite the opposite. You've declared n to be an Int in the type signature, and that fixes it forever. The Float here is hyp x y. You're asking whether hyp x y is an element of [1..n]. elem :: a -> [a] -> Bool, so it only makes sense to ask that question when you have an object that's the same type as the list's elements. That's the mismatch: to use elem with a Float and a list, you need that list to be a [Float]. But since the list is [1..n], it's clearly a [Int].

As for what you should do differently, I would suggest not using any floating-point arithmetic at all for this function. Probably it's fine for the scales you're working at, but I'd be too worried about rounding errors giving me wrong answers. Instead of searching for pairs such that sqrt (a^2 + b^2) is an integer, which requires a sqrt, you can search for triples such that a^2 + b^2 == c^2.

user_6254030

Here's some possible re-writing steps for your code,

-- 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]

and suddenly it's working. Is it fast? Let's see,

> 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

So it's just about quadratic. Makes sense -- the enumeration of the (x,y) pairs already is such, and calculating the h directly and testing the equality with it, is O(1) for each pair.

But what about searching for the h that fulfills the equality, for each (x,y) combination? Is it a good idea, performance-wise?

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

The projected time for this version to run up to 1000 is 270 seconds, instead of the 2.3 seconds of the last re-write above.

Enumerating Cartesian product of two ranges is quadratic; enumerating Cartesian product of three ranges is cubic. It only makes sense.

Another approach that could be faster than even the first one here wouldn't be searching for any triples at all but would instead generate them in order.

user_8498910
Related