What's the way to determine if an Int is a perfect square in Haskell?

Question

I need a simple function

is_square :: Int -> Bool

which determines if an Int N a perfect square (is there an integer x such that x*x = N).

Of course I can just write something like

is_square n = sq * sq == n
    where sq = floor $ sqrt $ (fromIntegral n::Double)

but it looks terrible! Maybe there is a common simple way to implement such a predicate?

Answer 1

Think of it this way, if you have a positive int n, then you're basically doing a binary search on the range of numbers from 1 .. n to find the first number n' where n' * n' = n.

I don't know Haskell, but this F# should be easy to convert:

let is_perfect_square n =
    let rec binary_search low high =
        let mid = (high + low) / 2
        let midSquare = mid * mid

        if low > high then false
        elif n = midSquare then true
        else if n < midSquare then binary_search low (mid - 1)
        else binary_search (mid + 1) high

    binary_search 1 n

Guaranteed to be O(log n). Easy to modify perfect cubes and higher powers.