title: Fast element lookup for a functional language(Haskell)
body: <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>