CODEWITHSUNDEEP
haskell
CodyBugstein
CodyBugstein

Reputation: 23322

Haskell function to test if Int is perfect square using infinite list

Purely for pleasure, and practice, I am trying to write a simple Haskell function to determine if an integer is a perfect square. Now I know that there are other solutions out there but I am wondering if there is a way to do it with an infinite list. I've started with this, but for clear reasons, it is not working (it never stops!)

    isSquare :: Integer -> Bool
    isSquare n = sum[ 1 | x <- [1..], x*x == n] /= 0

Also, if I might add, can someone point out how to search an infinite list for the first instance of something and then STOP! ?

Upvotes: 7

Views: 2641

Answers (5)

David Miani
David Miani

Reputation: 14668

About the infinite search function:

There is already a function that searches a list for a value - elem.

If you assume the infinite list is sorted, we could write a version of elem that works on such a list. This can easily be accomplished by firstly rejecting any elements less than the search value. The first value not rejected then must be either equal to or greater than the search element. If equal - return true, else return false

infiniteElem1 :: (Ord a) => a -> [a] -> Bool
infiniteElem1 x list = (== x) $ head $ dropWhile (< x) list

Example usage:

> infiniteElem1 10 [1..]
True
> infiniteElem1 10 [1,3..]
False

There is one problem though with infiniteElem1 though: If used on a finite list, it may throw an exception if the element isn't found:

> infiniteElem1 100 [1,2,3]
*** Exception: Prelude.head: empty list

This is a reason the function head is best avoided. A better solution is this:

infiniteElem :: (Ord a) => a -> [a] -> Bool
infiniteElem x list = case dropWhile (< x) list of
  [] -> False
  (v:_) -> v == x

Now it works with a finite sorted list as well:

> infiniteElem 100 [1,2,3]
False

With this your problem becomes trivial:

let isSquare n = n `infiniteElem` [ x * x | x <- [1..]]

Upvotes: 11

גלעד ברקן
גלעד ברקן

Reputation: 23955

Just for fun, here's another infinite list version:

isSquare n = isSquare' [1..] where
  isSquare' infiniteList@(x:xs)
    | x*x == n  = True
    | x*x > n   = False
    | otherwise = isSquare' xs

Upvotes: 4

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68152

Unfortunately, using Sum on an infinite list will not work. In particular, how can you ever know that every future element of the list is going to be zero? You can't, so you have to get the whole list before calculating the sum. For an infinite list, this can take a little while.

If you really want to use an infinite list--infinite lists are fun, after all--I suggest constructing an infinite list of square numbers. Then check whether n is in that list. You have to be a bit clever about how you do this to ensure it terminates, but I'll leave that as an exercise to the reader. (Man, I love that phrase :P.)

You can find something from an infinite list using a function like, predictable, find. This will actually stop as soon as it finds something. However, if it doesn't find the element, it will never stop. This may not be the behavior you desire. There's no general way of getting around this, but you can figure out how to fix it for any particular problem: for example, if the list is sorted in ascending order, you can do takeWhile (< limit) where limit is the upper bound on the possible answer.

Upvotes: 5

Piotr Lopusiewicz
Piotr Lopusiewicz

Reputation: 2594

let isSquare n = elem n (takeWhile (<=n) [ x*x | x <- [1..]])
ghci> isSquare 25
True
ghci> isSquare 28
False

Upvotes: 4

hammar
hammar

Reputation: 139860

You can use takeWhile or dropWhile. For example:

isSquare n = head (dropWhile (< n) squares) == n
  where squares = [x*x | x <- [0..]]

Upvotes: 6

Related Questions