title: Strong union of two lists
body: <p>I've defined functions:</p>
  
  <pre><code>fun concaten(x,y) =
      if (x = [])
        then y
        else hd(x) :: concaten(tl(x),y);
  </code></pre>
  
  <p>as well as:</p>
  
  <pre><code>fun existsin(x,L) =
    if (L=[])
    then false
    else if (x = hd(L))
           then true
           else existsin(x,tl(L));
  </code></pre>
  
  <p>and am now trying to define a function of type <code>(((list * list) -&gt; list) -&gt; list)</code> that looks vaguely like the following:</p>
  
  <pre><code>fun strongunion(x,y) =
    val xy = concaten(x,y);
    if xy=[]
      then []
    if (existsin(hd(xy),tl(xy)) andalso x!= [])
      then strongunion(tl(x),y)
      else if (existsin(hd(xy),tl(xy)) andalso x = [])
             then strongunion(x,tl(y))
             else if (x != [])
                    then hd(xy) :: strongunion(tl(x),y)
                    else hd(xy) :: strongunion(x,tl(y));
  </code></pre>
  
  <p>which takes the "strong" union of two lists, i.e. it combats faulty inputs (lists with element duplicates). This code is, of course, syntactically invalid, but the reason I included it was to show what such a function would look like in an imperative language. </p>
  
  <p>The way I started going about doing this was to first concatenate the lists, then remove duplicated elements from that concatenation (well, technically I am adding non-duplicates to an empty list, but these two operations are consequentially equivalent). To do this, I figured I would design the function to take two lists (type list*list), transform them into their concatenation (type list), then do the duplicate removal (type list), which would be of type <code>(((list*list) -&gt; list) -&gt; list)</code>.</p>
  
  <p>My issue is that I have no idea how to do this in SML. I'm required to use SML for a class for which I'm a TA, otherwise I wouldn't bother with it, and instead use something like Haskell. If someone can show me how to construct such higher-order functions, I should be able to take care of the rest, but I just haven't come across such constructions in my reading of SML literature.</p>