Fast element lookup for a functional language(Haskell)

Question

Say we are traversing a graph and want to quickly determine if a node has been seen before or not. We have a few set preconditions.

1. Nodes have been marked with integers values 1..N
2. Graph is implemented with nodes having an adjacency list
3. Every integer value from 1..N occurs in the graph, which is of size N

Any ideas for doing this in a purely functional way?(No Hash tables or arrays allowed).

I want a data structure with two functions working on it; add(adds an encountered integer) and lookup(checks if integer has been added). Both should preferably take O(n) time amortized for N repetitions.

Is this possible?

Answer 1

You can use a Data.Set. You add an element by creating a new set from the old one with insert and pass the new set around. You look up whether an element is a member of the set with member. Both operations are O(log n).

Perhaps, you could consider using a state monad to thread the passing of the set.

Answer 2

Efficient element lookup in functional languages is quite hard. Data.Set (as shown above) is implemented using a binary tree which can be built up in a purely functional way providing lookup operations in O(log n). HashTables (which aren't purely functional) would have O(1).

Answer 3

I believe that Data.BitSet might be O(n).