GIML: Tutorial Six
Some standard functions
There are several standard, or at least common, list functions.
Everyone uses map, it is a pre-defined function; reduce is pre-defined
as fold in standard ML, however we will continue to our own reduce
as the order of the arguments is different.
The following functions
will be used in further work without comment.
fun map f nil = nil (* pre-defined anyhow *)
| map f (h::t) = (f h)::map f t;
fun reduce f b nil = b
| reduce f b (h::t) = f(h,reduce f b t);
fun filter f nil = nil
| filter f (h::t) = if f h then h::filter f t
else filter f t;
fun member x nil = false
| member x (h::t) = x=h orelse member x t;
fun zip f nil nil = nil
| zip f (h::t) (i::s) = f(h,i)::zip f t s;
fun fst(a,_) = a; (* Also try #1 *)
fun snd(_,b) = b; (* Try #2 *)
- Consider each of the following expressions:
map(fn s => s^"io") ["pat", "stud", "rat"];
map(fn i => [i]) [4, 2, 1];
map hd [[2, 3], [7, 3, 2], [8, 6, 7]];
map(hd o rev o explode)["final","omega","previous","persist"];
- Define each of the following functions using map
ftrl([1, 7, 5, 3])=[3, 21, 15, 9]
fhel(["tom", "dot", "harriet"])=["t", "d", "h"]
fttl(["strange", "shout", "think"])=["range", "out", "ink"]
fsml(["war", "la", "tea", "per"])= ["swarm", "slam",...]
- Determine what each of the following do
val r = reduce (fn(a,b)=>b@[a]) nil;
val p = reduce (op ::);
val dr = reduce (fn(a,b)=>a+10*b) 0;
fun m x = reduce (fn(a,b)=>(a=x) orelse b) false;
fun n x = reduce (fn(a,b)=>(a=x) andalso b) true;
val im = reduce (op ^) "";
val ts = reduce (fn(a,b)=>if a=" " then nil else a::b) nil;
- Define each of the following using reduce
prodlist [4,2,5,1] = 40
flatten [[4,2,5],[],[1]] = [4,2,5,1]
count [3,2,5,1] = 4
duplist [4,2,5,1] = [4,4,2,2,5,5,1,1]
- Determine what each of the following do
fun rm x = filter (fn a=> a<>x);
val mx = reduce max ~1000000;
fun sq (x:int list) = zip (op * ) x x;
fun rprime x = filter (fn i => i mod x <>0);
fun sieve nil = nil
| sieve(h::t) = h::sieve(rprime h t);
Suggested inputs to determine function behaviour:
p [1,2,3] [4,5,6]
dr [3,6,2]
m 3 [2,6,7] m 3 [2,3,6,7] m 3 [3,3,3,3]
n 3 [2,6,7] n 3 [2,3,6,7] n 3 [3,3,3,3]
ts(explode "One fine day")
im(ts(explode "One fine day"))
sieve(upto 2 500)
Answers