GIML: Tutorial Three: More Hints

More hints on simple recursive functions

Comments
• power:
  The power calculation may be done in O(log n) time rather than O(n) time using a faster recursion fun square (n:int) = n * n; fun power(x,0) = 1 | power(x,n) = if n mod 2 = 0 (* is n even? *) then square(power(x, n div 2)) else x*square(power(x, n div 2));
• sumEvens:
  We note that this is a partial function. If you attempt to run this with an odd input then it will loop forever... sumEvens 3 ....:1::~1::sumEvens(~3) We allow partial functions. If you really feel the need to make your functions total then we can fix this: exception Whoops; fun sumEvens 0 = 0 | sumEvens n = if n<0 then raise Whoops else n+sumEvens(n-2);
• listTo:
  This is a clumsy definition. The "natural" way to add to a list is to the left, the list is essentially a stack and adding to the left is equivalent to a push operation. Adding to the right involves appending a (potentially) big list to a singleton list. This is expensive. It is a fairly common problem - getting your lists the wrong way round. It may be fixed by using an accumulating parameter or by using the standard function rev. val listTo = rev o listfrom; fun listTo n = let fun lt(0,acc) = acc | lt(n,acc) = lt(n-1,n::acc) in lt(n, nil) end;