title: Extracting Leaf paths from n-ary tree in F#
body: <p>Inspired by <a href="https://stackoverflow.com/questions/277106/looking-for-some-interesting-c-programming-problems">this question</a>, I wanted to try my hand at the latest <a href="http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/November2008.html" rel="nofollow noreferrer">ponder this challenge</a>, using F#</p>
  
  <p>My approach is probably completely off course, but in the course of solving this problem, I'm trying to get a list of all the permutations of the digits 0-9.</p>
  
  <p>I'm looking at solving it using a n-ary tree like so:</p>
  
  <pre><code>type Node = 
      | Branch of (int * Node list)
      | Leaf of int
  </code></pre>
  
  <p>I'm quite pleased with myself, because I've managed to work out how to generate the tree that I want. </p>
  
  <p>My problem now is that I can't work out how to traverse this tree and extract the 'path' to each leaf as an int. Thing thing that is confusing me is that I need to match on individual Nodes, but my 'outer' function needs to take a Node list.</p>
  
  <p>My current attempt almost does the right thing, except that it returns me the sum of all the paths...</p>
  
  <pre><code>let test = Branch(3, [Branch(2, [Leaf(1)]);Branch(1, [Leaf(2)])])
  
  let rec visitor lst acc = 
      let inner n = 
          match n with
          | Leaf(h) -&gt; acc * 10 + h
          | Branch(h, t) -&gt; visitor t (acc * 10 + h)
      List.map inner lst |&gt; List.sum
  
  visitor [test] 0 //-&gt; gives 633 (which is 321 + 312)
  </code></pre>
  
  <p>And I'm not even sure that this is tail-recursive.</p>
  
  <p>(You're quite welcome to propose another solution for finding permutations, but I'm still interested in the solution to this particular problem)</p>
  
  <p>EDIT: I've posted a generic permutations algorithm in F# <a href="https://stackoverflow.com/questions/286427/calculating-permutations-in-f">here</a>.</p>