CODEWITHSUNDEEP
haskellfunctional-programming
user1068464
user1068464

Reputation: 325

Check if item is in infinite List

I have a fairly basic question, about comparing with infinite lists. The problem is similar to this:

25 `elem` [x^2 | x <- [1..]]

obviously this is true. However, how do I deal with values that are not int the list, like

26 `elem` [x^2 | x <- [1..]]

Because it's an infinite list, Haskell doesn't have an answer for this, although it seems kinda obvious, that once we are past 6^2 we can't reach 26 anymore, so I want to stop there.

Now I could limit the x like:

[x^2 | x <- [1..6]]

Easy.

But what I do in examples like that:

[prod | k <- [1..], let prod = product [1..k]]

and I want to check if my number is in that list? Or what is an alternative way to get the result of this calculation?

Upvotes: 1

Views: 842

Answers (3)

Daniel Wagner
Daniel Wagner

Reputation: 152837

The data-ordlist package has many utility functions for dealing with sorted lists, including member:

Data.List.Ordered> 25 `member` [n^2 | n <- [1..]]
True
Data.List.Ordered> 26 `member` [n^2 | n <- [1..]]
False
Data.List.Ordered> 24 `member` [product [1..k] | k <- [1..]]
True
Data.List.Ordered> 25 `member` [product [1..k] | k <- [1..]]
False

Upvotes: 8

Dan Robertson
Dan Robertson

Reputation: 4360

Suppose that we have some order < and we know that for the lists we are interested in we have a 

sortedElem _ _ [] = False
sortedElem (<) y (x:xs) | y == x = True
                        | x < y  = False
                        | True   = sortedElem (<) y xs

And you could define special cases e.g.

elemIncreasing = sortedElem (<)
elemDecreasing = sortedElem (>)

I’m on my phone so I’ve not tested this. It should work in principle but the compiler may have a few issues. I’m sure they can be fixed.

Upvotes: 4

Ry-
Ry-

Reputation: 224942

If your list is in increasing order, you can find an element that’s at least what you’re looking for and check separately whether it’s the same:

> let elemIncreasing x l = find (>= x) l == Just x
> let factorials = scanl1 (*) [1..]
> 120 `elemIncreasing` factorials
True
> 121 `elemIncreasing` factorials
False

Upvotes: 7

Related Questions