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. Copy the following data structure taken from the CIA world factbook: 
    val europe =
  [("Andorra",450.0,65780.0,760000000.0),
   ("Austria",83850.0,7986664.0,139300000000.0),
   ("Belgium",30510.0,10081880.0,181500000000.0),
   ("Denmark",43070.0,5199437.0,103000000000.0),
   ("Estonia",45100.0,1625399.0,10400000000.0),
   ("Finland",337030.0,5085206.0,81800000000.0),
   ("France",547030.0,58109160.0,1080100000000.0),
   ("Germany",356910.0,81337541.0,1452200000000.0),
   ("Greece",131940.0,10647511.0,93700000000.0),
   ("Ireland",70280.0,3550448.0,49800000000.0),
   ("Italy",301230.0,58261971.0,998900000000.0),
   ("Latvia",64100.0,2762899.0,12300000000.0),
   ("Liechtenstein",160.0,30654.0,630000000.0),
   ("Lithuania",65200.0,3876396.0,13500000000.0),
   ("Luxembourg",2586.0,404660.0,9200000000.0),
   ("Malta",320.0,369609.0,3900000000.0),
   ("Monaco",1.0,31515.0,558000000.0),
   ("Netherlands",37330.0,15452903.0,275800000000.0),
   ("Norway",324220.0,4330951.0,95700000000.0),
   ("Portugal",92080.0,10562388.0,107300000000.0),
   ("San Marino",60.0,24313.0,380000000.0),
   ("Spain",504750.0,39404348.0,515800000000.0),
   ("Sweden",449964.0,8821759.0,163100000000.0),
   ("Switzerland",41290.0,7084984.0,148400000000.0),
   ("United Kingdom",244820.0,58295119.0,1045200000000.0)
];
fun name(x,_,_,_) = x;
fun area(_,x,_,_) = x;
fun pop (_,_,x,_) = x;
fun gdp (_,_,_,x) = x;
    The figures are area in sq km, population, and GDP in US dollars.
  4. The following function will sort a list in descending order according to a given (real) function of the list elements: 
    fun sort (f:'a -> real) nil = nil
|   sort f (h::t) = let
  fun insert x nil    = [x]
  |   insert x (h::t) = if f x > f h then x::h::t else
					  h::insert x t
in insert h (sort f t) end;
    Use this function to determine the largest European country in terms of:
  5. 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;
  6. 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]
  7. 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