More List Examples                            CSE 215 Fall 2007


1) Removing Duplicates from a List

   This function has been defined in class via an auxiliary
   function remove. Given below are definitions for remove and
   removedupl using pattern matching. 

   In function remove, we could not write a pattern
   remove(x, x::ys), because SML does not allow us
   to repeat a variable. Here x has been used twice.
   Not allowed. Correct definitions are:


   fun remove (x, nil) = nil
    |  remove (x, y::ys) = if x = y then ys
            else y::remove(x, ys);


   fun removedupl(nil) = nil
    |  removedupl(x::xs) = x::remove(x, removedupl(xs));


   Try an example:

   removedupl([1, 2, 1, 2, 2, 1, 3, 1]);

    
2) Constructing Sublists

   In class a function for constructing all sublists of
   a given list was defined using an auxiliary function
   insertL, which inserts its first argument at the front
   of its second (list) argument. Here is a definition
   of insertL.

   fun insertL(x, L) = if L = nil then []
        else [x::hd(L)] @ insertL(x, tl(L));

   fun sublists(L) = if L = nil then [ [] ]
               else sublists(tl(L))
              @ insertL(hd(L), sublists(tl(L)));

   Try this example:

   sublists([1, 2, 3]);

   Why do we need to enclose the expressions x::hd(L) within
   brackets?