How does one signify an infinite list to be ascending for elem checks?

Question

I have an infinite list of primes initialized by the following list comprehension:

primes = [x | x <- [2..], 0 `notElem` map (x `mod`) [2..(x `quot` 2)]]

This allows me to make checks like 17 `elem` primes to confirm that 17 is a prime. However, when I check whether a non-prime is in the list, the program does not stop computing. I assume that this is because it does not realize that if the number cannot be found in the list before a prime that is greater than the number, it cannot be found anywhere in the list. Therefore, is there anyway in Haskell to signify to the compiler that a list contains only ascending numbers, so that an elem check will know to stop and return false if it reaches a number in the list greater than its first argument?

score 6 · Accepted Answer · answered Feb 22 '16 at 15:14

6

One possibility would be to use dropWhile:

isPrime n = (head $ dropWhile (< n) primes) == n

answered Feb 22 '16 at 15:14

Vincent Savard

34,979
10
68
73

or in general [`ordElem y xs = take 1 (dropWhile (< y) xs) == [y]`](http://stackoverflow.com/a/28828217/849891) which works with finite lists also. – Will Ness Feb 24 '16 at 11:41

zakyggaps · Answer 2 · 2016-02-22T15:56:58.080

4

Sure. You can define your own OrderedList newtype, wrap the infinite list, define more efficient searching function that takes OrderedList as its argument.

newtype OrderedList a = OL [a]
member a (OL as) = case dropWhile (<a) as of
  []    -> False
  (x:_) -> a == x

You cannot override the behavior of elem eventhough it's a class method of Foldable, since the definition of elem only requires the underlying element type to be Eqable, namely:

member :: (Ord a, Eq a) => a -> OrderedList a -> Bool
elem :: (Eq a, Foldable t) => a -> t a -> Bool

You can verify that by the following code:

instance Foldable OrderedList where
  foldMap f (OL as) = foldMap f as
  elem = member -- error: Could not deduce `Ord a` arising from a use of `member`

Just a note: when your list is not infinite, you'd better consider make use of the tree-like structures (e.g. IntSet), they optimize the complexity of search operaton from O(n) to O(log(n)).

edited Feb 22 '16 at 15:56

answered Feb 22 '16 at 15:13

zakyggaps

3,070
2
15
25

Can you make `member 1 (OL [2..10])` to return `False`, as one would expect? Possibly, also `member 1 (OL [])`. Otherwise, it really requires an infinite list. – chi Feb 22 '16 at 15:23
1

The essence of this answer is "you can't teach `elem` about the ordering; searching a presumed-sorted list is a different operation, so make a different function". The newtype wrapper isn't really directly relevant (though it's a nice answer to the follow up question "how could I keep from accidentally applying `member` to a list that might not be sorted"). – Ben Feb 22 '16 at 20:48
@Ben +1. I'd stress it even more, as "**No**, you **can't** teach `elem`" new tricks; you have to define a new function for that. – Will Ness Feb 24 '16 at 12:01

chi · Answer 3 · 2016-02-24T13:18:50.320

One can code it as a fold:

memberOrd :: (Eq a, Ord a) => a -> [a] -> Bool
memberOrd x = foldr (\y b -> y==x || y<x && b) False

The laziness of || makes it work on infinite lists as well.

(Clearly, we must assume that the list does not contain infinitely many elements < x. We are not suddenly able to solve undecidable problems... ;-) )

Will Ness below suggests the following variant, which performs fewer comparisons:

memberOrd x = foldr (\y b -> y<x && b || y==x) False

How does one signify an infinite list to be ascending for elem checks?

3 Answers3