# GIML: Tutorial Four

## Recursion with lists

- Define sum and doublist as shown. Execute
both functions on the list [5,3,1].
fun sum nil = 0
| sum(h::t) = h + sum t;
fun doublist nil = nil
| doublist(h::t) = 2*h :: doublist t;
- Define and test the following functions. An example execution has been given for each case.
len [4, 2, 5, 1] = 4
triplist [4, 2, 5, 1] = [12, 6, 15, 3]
duplist [4, 2, 5, 1] = [4, 4, 2, 2, 5, 5, 1, 1]
prodlist [4, 2, 5, 1] = 40
Check the function prodlist. If you always get the result zero it is
probably because you have the base case wrong. Consider how ML executes a
simple case such as prodlist [1]. Consider also that just as the result of
adding all the elements in an empty list is zero - the identity element for
addition, so the result of multiplying all the elements of an empty list is
one, the identity element for multiplication. If you still need convincing
of this then remember that 5
^{3} is five to the power three - what
you get
from multiplying three fives. However 5^{0} is one, the result of
multiplying
no fives.
- Define the function vallist which turns character digits into integers. You will need to use the in-built function ord.
vallist ["4","2","5","1"] = [4,2,5,1]
- Define the function reverse which reverses the order of a list. Note the comments made about adding elements to lists earlier.
fun reverse nil = nil
| reverse(h::t) = (reverse t)@ ??;
- Define the following functions.
space ["a","b","c"] = ["a"," ","b"," ","c"," "]
flatten [[1,2],[3],[4,5]] = [1,2,3,4,5]
count_1s [4,3,1,6,1,1,2,1] = 4
timeslist 4 [4, 2, 5, 1] = [16, 8, 20, 4]
last [4, 2, 5, 1] = 1
member (3, [4, 2, 5, 1]) = false
member (5, [4, 2, 5, 1]) = true

Answers