MIFFS Is Fun For Sums

by rich

Examples

This manual really is a woeful resource to try to learn (what is essentially) ML from, but if I'm honest, I'm only writing this because I enjoy it. So this section is gratuitously for me to write some fun or useful code and write it up. It may be helpful if you are using MIFFS and want to see what it can do, or more specifically if you're doing a Stats Examples Sheet.

Quicksort

Sorting is great for some really elegant code. I'm told the majority of computer time is spent sorting things, or at least it was from the very earliest days up until fairly recently. As such, a lot of very clever people have spent lots of time devising sorting algorithms that are, mathematically speaking, perfect. Quicksort is not quite it, but if you add some extra logic to catch deliberately nasty cases (such as reverse-sorted data) then can be.

So how does it work? It has most benefits in a language like C (for arrays), but works fine with linked lists. We first need to divide a list about a pivot - into two halves, one half smaller than (or equal to) the pivot, the other half greater than it. (Put MIFFS into multi line mode and make it a little wider if you want to try this.)

fun pivot (a::l) = let
       fun part([],   bef,aft) = (bef,aft)
        |  part(x::xs,bef,aft) = if x <= a then part(xs,x::bef,aft) 
                                           else part(xs,bef,x::aft)
       val (p,q) = part(l,[],[])
    in 
       (p, a, q)
    end
val pivot = fn : α -> α
pivot [0,-1,1,1,-1,-1,1]
val ans = ([-1, -1, -1], 0, [1, 1, 1]) : int list * int * int list

This function uses the first element of the list as the pivot - faster versions sometimes use the median of the first, last and middle element. Try it on some (non-empty) lists if you like.

All that remains is to use the power of recursion - just as you might use mathematical induction.

We can sort an empty list and we can sort a list of length 1 - so we have our base cases. The inductive step is to split a large list into two (using pivot) and recursively sort the pieces, then join them up:

fun qsort [] = []
 |  qsort [x] = [x]
 |  qsort list = let 
      val (p, a, q) = pivot list
    in
      (qsort p) @ (a :: (qsort q))
    end
val qsort = fn : α -> α

Try it out!

ANOVA

I used MIFFS to do an analysis of variance on my stats sheet and thought it might be a nice example. I won't bother to make up new numbers, so you can check my working if you did the same sheet!

The data are four groups of samples: lets get them and some basic stats functions into MIFFS:

val data = [[20.8,20.9,20.7,20.6,20.7],
            [20.6,20.3,20.2,20.3,20.5],
		    [20.9,20.8,20.8,20.7],
		    [20.8,20.9,20.9,20.4]]
val data = [ ... ] : (real list) list
fun sum [] = 0 | sum (x::xs) = x + sum xs
val sum = fn : α -> α
fun mean list = sum list / length list
val mean = fn : α -> α
fun sxx list = let 
   val xbar = mean list 
 in sum (map (fn x => (x-xbar)^2) list) end
val sxx = fn : α -> α

Now we want to calculate the total mean, and the mean of each group:

val totmean = sum (map sum data) / sum (map length data)
val totmean = 20.655555555555555 : real
val samplemeans = map mean data
val samplemeans = [20.740000000000002, 20.380000000000003,
                   20.799999999999997, 20.75] : real list

We need the between groups variation, defined as the sum over the groups of the size of each group times the square of the difference between the group mean and the total mean. We also want the within group variation, which is the sum over all samples of the square of the difference between the sample and that sample's group mean. The total variation would also help - that's the squared deviation of the entire set.

val betweenvar = let 
  fun inner([],[]) = 0 
   |  inner(n::ns,mean::means) = n*(mean-totmean)^2 + inner(ns,means)
 in inner(map length data, map mean data) end
val betweenvar = 0.5344444444444357 : real

val withinvar = let 
  fun inner([],[]) = [] 
   |  inner(mean::means,list::lists) = 
         (map (fn x=>(x-mean)^2) list) :: inner(means,lists)
 in sum (map sum (inner(map mean data, data))) end
val withinvar = 0.35000000000000003 : real

val totalvar = sum (map sum
                    (map 
                     (map (fn x=>(x-totmean)^2))
                       data))
val totalvar = 0.8844444444444424 : real

Ok, these are moderately complex functions, and it might even have been quicker to do it all manually (although in this case I would argue not), but this way is so much more fun ;-)

Mergesort

After all that, let's have another elegant recursive sorting function. First we need to split a list into two:

fun split([], a, b) = (a, b) 
 |  split([x], a, b) = (x::a, b)
 |  split(x::y::list, a, b) = split(list, x::a, y::b)
val split = fn : α -> α

Now we need to merge two already sorted lists:

fun merge([], ys) = ys
 |  merge(xs, []) = xs
 |  merge(x::xs, y::ys) = if x <= y then x :: merge(xs,y::ys)
                                    else y :: merge(x::xs,ys)
val merge = fn : α -> α

Now we use induction again: sort trivial lists trivially, and sort big lists by splitting them - inductively sort the parts - and merge them back together.

fun mergesort [] = []
 |  mergesort [x] = [x]
 |  mergesort list = let 
         val (a,b) = split(list, [], [])
     in merge(mergesort a, mergesort b) end
val mergesort = fn : α -> α