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 *)
  1. 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"];
  2. 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",...]
  3. 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;
  4. 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]
  5. 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