title: Standard ML polymorphic sorting
body: <p>I am very inexperienced in ML, and I just can't make sense of this.</p>
  
  <p><strong>Start question</strong></p>
  
  <p>Polymorphic Sorting</p>
  
  <p>This function performing insertion sort on a list takes as arguments a comparison function less and a list l of elements to be sorted. The code compiles and runs correctly:</p>
  
  <pre><code>fun sort(less, nil) = nil |
      sort(less, a : : l) =
         let
  
  fun insert(a, nil) = a : : nil |
     insert(a, b : : l) = if less(a,b) then a : : (b: : l)
                                     else b : : insert(a, l)
  
  in
      insert(a, sort(less, l))
  end;
  </code></pre>
  
  <p>What is the type of this sort function? Explain briefly, including the type of the subsidiary function insert. You do not have to run the ML algorithm on this code; just explain why an ordinary ML programmer would expect the code to have this type. (<strong>End of question</strong>)</p>
  
  <p>I've gotten the type of the sort function (by running the code in an SML interpreter), but I just can't get the second part about insert.</p>
  
  <p>Type of sort function:</p>
  
  <pre><code>val sort = fn : ('a * 'a -&gt; bool) * 'a list -&gt; 'a list 
  </code></pre>
  
  <p>Any help would be greatly appreciated.</p>