title: Find all valid addresses of a tree in SML
body: <p>I want to write a procedure which delivers all valid addresses of a simple tree in SML. The datastructure of a tree in this case is:</p>
  
  <pre><code>datatype tree = T of tree list
  </code></pre>
  
  <p>What I have up till now is:</p>
  
  <pre><code>fun address (T ts) = (rev (#2(foldl (fn (s,(sum, liste)) =&gt; (sum+1,[sum]::liste) ) (1, [nil]) ts))) @ (map address ts);
  </code></pre>
  
  <p>My thinking is that foldl creates a list of all addresses for the parent nodes, and by appending the adresses of all children nodes it eventually delivers the list of all possible adresses. The interpreter disagrees:</p>
  
  <blockquote>
    <p>Elaboration failed: Type clash. Functions of type <code>'a list * 'a list → 'a list</code> cannot take an argument of type <code>int list list * int list list list</code>: Cannot merge <code>int list</code> and <code>int</code>.</p>
  </blockquote>
  
  <p>So any ideas?</p>