generate list with guards and recursion

Bailey 0
Viewed 53

I am trying to generate a list of perfect squares between 2 values i and n using recursion and guards. I can achieve this with list comprehension (i is not taken as an argument):

isPerfectSquare :: Integral a => a -> Bool
isPerfectSquare n = sq * sq == n
    where sq = floor(sqrt(fromIntegral n :: Double))

squares :: Int -> [Int]
squares x = [y | y <- [1..x], isPerfectSquare y]

But I'm having trouble using recursion and guards for this. I'm trying to implement this without using higher order functions or list comprehension. I would appreciate someone pointing me in the right direction.

haskell
1 Answers

The usual trick is to generalize the task: instead of producing the squares in 1..x, produce those in a..b. This means writing an auxiliary function that takes both a and b as arguments.

Here's some skeleton code, to be adapted as needed.

squares :: Int -> [Int]
squares x = squaresFromTo 1 x

squaresFromTo :: Int -> Int -> [Int]
squaresFromTo a b
   | a > b     = ...  -- no squares here!
   | good a    = ...  -- keep a
   | otherwise = ...  -- discard a
   where
   otherSquares = squaresFrom (a+1) b

Now the question becomes: "how can we compute the squares in a..b knowing the recursive result otherSquares of the squares in a+1..b ?"

usernAzd0
Related