GIML: Tutorial Three

Note for Moscow ML users
1. Consider the following function definition:
   

   fun t(0)= 0
   |   t(n)= 2+t(n-1);
   

   This definition should be read as two equations. The first equations states that t is defined to be 0 if the input is 0 the second equation states that where n is not 0 the value of t(n) is "2 more than t(n-1)". This defines t for all non-negative values, moreover it gives us a means of calculating t for any non-negative value.
   

   We have an equation which gives the value of t(0)
   t(0)	= 0	From the first equation: fun t(0)= 0
   We can deduce that t(1)=2 using the defining equations and the above result.
   t(1)	= 2 + t(1-1)	Using the second equation: | t(n)= 2 + t(n-1) with 1 for n
   	= 2 + t(0)
   	= 2 + 0	We know that t(0) = 0 from the above calculation
   	= 2
   Similarly we can calculate t(2)
   t(2)	= 2 + t(2-1)	From the 2nd equation with 2 for n
   	= 2 + t(1)
   	= 2 + 2
   	= 4
   and we can calculate t(3)
   t(3)	= 2 + t(2)
   	= 2 + 4
   	= 6

   Now try evaluating t for the values 4, 5, 6, 7 and 100. Convince yourself that there is a pattern.

   Paste each of the following function definitions into ML and evaluate each a a few values. Be sure that you can see

   • what each function does
   • how each function works

   fun d(0)= "de"
   |   d(n)= "do"^d(n-1)^"da";
   
   fun h(0)= 1
   |   h(n)= h(n-1)+h(n-1);
   
   fun m(a,0) = 0
   |   m(a,b) = a+m(a,b-1);
   
   fun f(0)= true
   |   f(n)= not(f(n-1));
   
   fun g(0)= nil
   |   g(n)= 0::g(n-1);
   
   fun l(0)= nil
   |   l(n)= n mod 10 :: l(n div 10);
   
   fun j(0)= 0
   |   j(n)= (n mod 10) + j(n div 10);
   

   You should find that the call h 20; takes several seconds to evaluate while h 40; takes several weeks - why is this?
   To save typing you might consider using map to evaluate the functions over a list of values for example:

   map t [1,2,3,4,5,6];
   

2. Each of the following functions can be defined in a similar way. An example has been given in each case: sumto(4) = 4+3+2+1+0 = 10 listfrom(4) = 4::3::2::1::nil = [4,3,2,1] strcopy("ab",4) ="ab"^"ab"^"ab"^"ab"^"" = "abababab" power(3,4) = 3*3*3*3*1 = 81 listcopy(7,4) = 7::7::7::7::nil = [7,7,7,7] sumEvens(8) = 8+6+4+2+0 = 20 listOdds(7) = 7::5::3::1::nil = [7,5,3,1] nat(2) ="succ("^"succ("^ "zero"^")"^")" ="succ(succ(zero))" listTo(4) = nil@[1]@[2]@[3]@[4] = [1,2,3,4] Example: sumto We require two equations for this function, the base equation, in this case a value for sumto 0; and a recursive equation, how to get sumto n given sumto(n-1) fun sumto(0)= ?? | sumto(n)= ?? sumto(n-1); Example listcopy Given two parameters we must choose which one to recurse on. For listcopy the second parameter givens the number of copies to be made - this is the one to recurse on. There must be a base case, the value of listcopy(x, 0) for any value x; and the recursive case, the value of listcopy(x, n) given listcopy(x, n-1) fun listcopy(x, 0) = ?? | listcopy(x, n) = ?? listcopy(x,n-1) Hints:

fun t(0) = 0
|   t(n) = 2 + t(n-1);


fun t 0 = 0
|   t n = 2 + t(n-1);