title: Haskell: Turning a tree into a map
body: <p>Basically I want to turn a BST tree into a map where the nodes are the keys and the number of occurrences of the nodes are the values.  So if I inputted this:</p>
  
  <blockquote>
    <p>toMap (leaf 13)</p>
  </blockquote>
  
  <p>I would get </p>
  
  <pre><code>&gt; [(13,1)]
  </code></pre>
  
  <p>Here is what I have so far:</p>
  
  <pre><code>data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
  leaf x = Node x Empty Empty
  
  toMap' :: Int -&gt; Tree a -&gt; ([(a, Int)], Int)
  toMap' a Empty = ([], a)
  toMap' a (Node x xl xr) = ((x, a): xl' ++ xr', k)
                        where (xl', i) = toMap' (a+1) xl
                              (xr', k) = toMap' (i) xr
  
  toMap :: Tree a -&gt; [(a, Int)]
  toMap = fst. toMap' 1
  </code></pre>
  
  <p>This program returns a map but the values are incorrect.  Each value is one greater than the previous value (so if there are 3 nodes than the value of the third node will be three).  I think I have to place a counter on each new key, but I'm not sure how.  Thanks in advance </p>