<p>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.</p>

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

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

<p>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.</p>

<p>Is this possible?</p>

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.