GIML: Tutorial Three: More Hints
More hints on simple recursive functions
fun power(x,0) = 1
| power(x,n) = x*power(x,n-1);
fun listcopy(x,0) = []
| listcopy(x,n) = x::listcopy(x,n-1);
fun sumEvens 0 = 0
| sumEvens n = n + sumEvens(n-2);
fun listOdds 1 = [1]
| listOdds n = n::listOdds(n-2);
fun nat 0 = "zero"
| nat n = "succ(" ^ nat(n-1) ^ ")";
fun listTo 0 = nil
| listTo n = listTo(n-1) @ [n];
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;