281CS 538 Spring 2006©Power Sets RevisitedLet’s compute power sets in ML.We want a functionpow that takes alist of values, viewed as a set, andwhich returns a list of lists. Eachsublist will be one of the possiblesubsets of the original argument.For example,pow [1,2] = [[1,2],[1],[2],[]]We first define a version of cons incurried form:fun cons h t = h::t;val cons = fn : 'a -> 'a list -> 'a list282CS 538 Spring 2006©Now we define pow. We define thepowerset of the empty list,[], to be[[]]. That is, the power set of theempty set is set that contains onlythe empty set.For a non-empty list, consisting ofh::t, we compute the power set of t,which we callpset. Then the powerset forh::t is just h distributedthroughpset appended to pset.We distributeh through pset veryelegantly: we just map the function(cons h) to pset. (cons h) adds hto the head of any list it is given.Thus mapping(cons h) to psetadds h to all lists in pset.283CS 538 Spring 2006©The complete definition is simplyfun pow [] = [[]] | pow (h::t) = let val pset = pow t in (map (cons h) pset) @ pset end;val pow = fn : 'a list -> 'a list listLet’s trace the computation ofpow [1,2].Hereh = 1 and t = [2]. We need tocomputepow [2].Nowh = 2 and t = [].We knowpow [] = [[]],sopow [2] =(map (cons 2) [[]])@[[]] =([[2]])@[[]] = [[2],[]]284CS 538 Spring 2006©Therefore pow [1,2] =(map (cons 1) [[2],[]])@[[2],[]] =[[1,2],[1]]@[[2],[]] =[[1,2],[1],[2],[]]285CS 538 Spring 2006©Composing FunctionsWe can define a composition functionthat composes two functions intoone:fun comp (f,g)(x) = f(g(x));val comp = fn :('a -> 'b) * ('c -> 'a) -> 'c -> 'bIn curried form we havefun comp f g x = f(g(x));val comp = fn :('a -> 'b) ->('c -> 'a) -> 'c -> 'bFor example,fun sqr x:int = x*x;val sqr = fn : int -> intcomp sqr sqr;val it = fn : int -> int286CS 538 Spring 2006©comp sqr sqr 3;val it = 81 : intIn SML o (lower-case O) is the infixcomposition operator.Hencesqr o sqr ≡ comp sqr sqr287CS 538 Spring 2006©Lambda TermsML needs a notation to write downunnamed (anonymous) functions,similar to the lambda expressionsScheme uses.That notation isfn arg => body;For example,val sqr = fn x:int => x*x;val sqr = fn : int -> intIn fact the notation used to definefunctions,fun name arg = body;is actually just an abbreviation for themore verboseval name = fn arg => body;288CS 538 Spring 2006©An anonymous function can be usedwherever a function value is needed.For example,map (fn x => [x]) [1,2,3];val it =[[1],[2],[3]] : int list listWe can use patterns too:(fn [] => [] |(h::t) => h::h::t);val it = fn : 'a list -> 'a list(What does this function do?)289CS 538 Spring 2006©Polymorphism vs. OverloadingML supports polymorphism.A function may accept a polytype (aset of types) rather than a singlefixed type.In all cases, the same functiondefinition is used. Details of thesupplied type are irrelevant and maybe ignored.For example,fun id x = x;val id = fn : 'a -> 'afun toList x = [x];val toList = fn : 'a -> 'a list290CS 538 Spring 2006©Overloading, as in C++ and Java,allows alternative definitions of thesame method or operator, withselection based on type.Thus in Java+ may represent integeraddition, floating point addition orstring concatenation, even thoughthese are really rather differentoperations.In ML+, -, * and = are overloaded.When= is used (to test equality), MLdeduces that an equality type isrequired. (Most, but not all, types canbe compared for equality).When ML decides an equality type isneeded, it uses a type variable thatbegins with two tics rather than one.fun eq(x,y) = (x=y);val eq = fn : ''a * ''a -> bool291CS 538 Spring 2006©Defining New Types in MLWe can create new names for existingtypes (type abbreviations) usingtype id = def;For example,type triple = int*real*string;type triple = int * real * stringtype rec1= {a:int,b:real,c:string};type rec1 = {a:int, b:real, c:string}type 'a triple3 = 'a*'a*'a;type 'a triple3 = 'a * 'a * 'atype intTriple = int triple3;type intTriple = int triple3These type definitions are essentialitymacro-like name substitutions.292CS 538 Spring 2006©The Datatype MechanismNew types are defined using thedatatype mechanism, whichspecifies new data value constructors.For example,datatype color = red|blue|green;datatype color = blue | green | redPattern matching works on user-defined types using theirconstructors:fun translate red = "rot" | translate blue = "blau" | translate green = "gruen";val translate = fn : color -> string293CS 538 Spring 2006©fun jumble red = blue | jumble blue = green | jumble green = red;val jumble = fn : color -> colortranslate (jumble green);val it = "rot" : stringSML ExamplesSource code for most of the SMLexamples presented here may befound in~cs538-1/public/sml/class.sml294CS 538 Spring 2006©Parameterized ConstructorsThe constructors used to define datatypes may be parameterized:datatype money = none | coin of int | bill of int | iou of real * string;datatype money = bill of int | coin of int | iou of real * string | noneNow expressions like coin(25) orbill(5) or iou(10.25,"Lisa")represent valid values of type money.295CS 538 Spring 2006©We can also define values andfunctions of typemoney:val dime = coin(10);val dime = coin 10 : moneyval deadbeat =iou(25.00,"Homer Simpson");val deadbeat = iou (25.0,"Homer Simpson") : moneyfun amount(none) = 0.0 | amount(coin(cents)) = real(cents)/100.0 | amount(bill(dollars)) = real(dollars) | amount(iou(amt,_)) = 0.5*amt; val amount = fn : money -> real296CS 538 Spring 2006©Polymorphic DatatypesA user-defined data type may bepolymorphic. An excellent example isdatatype 'a option = none | some of 'a;datatype 'a option = none | some of 'aval zilch = none;val zilch = none : 'a optionval mucho =some(10e10);val mucho =some 100000000000.0 : real optiontype studentInfo = {name:string, ssNumber:int option};type studentInfo = {name:string,ssNumber:int option}297CS 538 Spring 2006©val newStudent ={name="Mystery Man", ssNumber=none}:studentInfo;val newStudent ={name="Mystery Man", ssNumber=none} : studentInfo298CS 538 Spring 2006©Datatypes may be RecursiveRecursive datatypes allow linkedstructures without explicit pointers.datatype binTree = null| leaf| node of binTree * binTree;datatype binTree =leaf | node of binTree * binTree | nullfun size(null) = 0 | size(leaf) = 1 | size(node(t1,t2)) = size(t1)+size(t2) + 1val size = fn : binTree -> int299CS 538 Spring 2006©Recursive Datatypes may