title: How to write function for N-ary tree traversal in Haskell
body: <p>I need to traverse N-ary tree and to the each node add number when I visited in in preorder. I have n-ary tree defined like this:</p>
  
  <pre><code>data NT a = N a [NT a] deriving Show
  </code></pre>
  
  <p><strong>Example:</strong>
  If I have following tree:</p>
  
  <pre><code>let ntree = N "eric" [N "lea" [N "kristy" [],N "pedro" [] ,N "rafael" []],N "anna" [],N "bety" []]
  </code></pre>
  
  <p>I want to transform it to </p>
  
  <pre><code>let ntree = N (1,"eric") [N (2,"lea") [N (3,"kristy") [],N (4,"pedro") [] ,N (5,"rafael") []],N (6,"anna") [],N (7,"bety") []]
  </code></pre>
  
  <p>"Preordedness"  isnt that important.</p>
  
  <p>I want to see how to write a function that <strong>passes values between levels</strong>, like how to pass number down to successor list and how to pass updated number to parent and go with that number to other branches.</p>
  
  <p>So far I has been able to write functions like this: </p>
  
  <pre><code>traverse :: NT String -&gt; String
  traverse (N val []) =" "++val++" "
  traverse (N val list) =val++" " ++ (concat $ map  traverse list)
  </code></pre>
  
  <p>which outputs</p>
  
  <pre><code>"eric lea  kristy  pedro  rafael  anna  bety "
  </code></pre>
  
  <p><strong>EDIT:</strong> Question is:</p>
  
  <p>How can I write a function </p>
  
  <pre><code>numberNodes :: NT a -&gt; NT (a,Int)
  </code></pre>
  
  <p>that numbers nodes according to the preorder traversal of the tree?</p>
  
  <p>Hard part for me to understand is passing auxilliary data around, could you please elaborate on that ? </p>
  
  <p>In this concrete case it is one Int that means "time" or order in which I traverse this tree.</p>