Hide State in Haskell - Lazyset

I'm trying to build a datastructure in Haskell that allows efficient lookup in an ordered, infinite list.

If this was Java, I'd do something like this:

class LazySet<T> {

    private Iterator<T> source;
    private NavigableSet<T> set;

    public LazySet(Iterator<T> source){
         this.source = source;
         this.set = new TreeSet<T>() ;               
    }

    public boolean contains(T elem){
        // Fetch items from the source into the set until the element(or one greater than it)
        // has been found
        while (this.set.ceiling(elem) == null){
                if (this.source.hasNext()){
                    this.set.add(this.source.next());
                }else{
                    return false;
                }
        }
        return this.set.contains(elem);
    }    
}

Now while this class clearly has state, that state is purely for optimization and does not affect the user of the class. So It can be used in a functional manner.

The Haskell equivalent of this class would be stateful.

Probably something like this:

type LazySet a = (Set a, [a])

member :: Ord a => LazySet a -> a -> (Bool, LazySet a)

And that would force the user to explicitly pass the LazySet around, which makes it much harder to use.

Is there a way to tell haskell: Yes this thing has state, but treat it as if it didn't?