recursion - Integer square root function in Haskell

Question

The integer square root of a positive integer n is the largest integer whose square is less than or equal to n. (E.g. the integer square root of 7 is 2, and that of 9 is 3).

Here is my attempt:

intSquareRoot :: Int -> Int
intSquareRoot n
    | n*n > n   = intSquareRoot (n - 1) 
    | n*n <= n  = n

I'm guessing its not working because n decreases along with the recursion as required, but due to this being Haskell you can't use variables to keep the original n.

Answer 1

... but due to this being Haskell you cant use variables to keep the original n.

I don't know what makes you say that. Here's how you could implement it:

intSquareRoot :: Int -> Int
intSquareRoot n = aux n
  where
    aux x
      | x*x > n = aux (x - 1)
      | otherwise = x

This is good enough to play around, but it's not a very efficient implementation. A better one can be found on Haskell's wiki:

(^!) :: Num a => a -> Int -> a
(^!) x n = x^n

squareRoot :: Integer -> Integer
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n =
   let twopows = iterate (^!2) 2
       (lowerRoot, lowerN) =
          last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows
       newtonStep x = div (x + div n x) 2
       iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot)
       isRoot r  =  r^!2 <= n && n < (r+1)^!2
  in  head $ dropWhile (not . isRoot) iters