GIML: Tutorial Eight: Answers

  1. Use a function such as upto to create a large list. fun upto m n = if m>n then nil else m::upto (m+1) n; You should find that revobv is much slower than revobs. This is is because the append operator adds a large list (revobv t) to a small list [h] at every recursion. This call is expensive - it creates length(revobv t) nodes each time and most of these are not used in the final answer. In all O(n2) "garbage" nodes are created.
  2. Countrep 
    fun countrep (h::t) = let
  fun cr c cn    nil = [(c,cn)]
  |   cr c cn (h::t) = if c=h then cr c (cn+1) t
                            else (c,cn)::(cr h 1 t)
in cr h 1 t end
|   countrep nil = nil;
  3. Averages.

    Mean:
    We can accumulate the sum and the length of the list simultaneously, we simply divide these when we reach the end of the list

    fun mean l = let fun sl(nil ,sum,len) = sum div len | sl(h::t,sum,len) = sl(t,sum+...,len+...) in sl(l,0,0) end; Median:
    We can recurs down the list at double speed throwing away two items at a time, the accumulating parameter starts at the whole list and discards every other item fun median l = let fun med(nil,l) = hd l | med(_::nil,l) = hd l | med(_::_::t,_::t') = med(t,t') in med(l,l) end; this does not work correctly for even length lists - for such lists we do not wish to discard exactly half the list.

    Mode:
    We must accumulate the current item and the number of repetitions and the most frequent so far and the number of occurrences.

    fun mode(h::t)= let fun bestof (c,n) (c',n') = if n>n' then (c,n) else (c',n') fun cb(nil,curr,best) = bestof curr best | cb(h::t,(c,n),best) = if h=c then cb(t,(c,n+1),best) else cb(t,(h,1),bestof(c,n)best) in fst(cb(t,(h,1),(h,1))) end;