MIFFS Is Fun For Sums

by rich

Intermediates

MIFFS is a fairly powerful and quite flexible (though inefficient) language, and it's certainly Turing Complete: so you should be able to write anything that it is possible to write.

If you have some experience of functional languages (especially ML), then you should find MIFFS quite familiar.

Lists

One of the main datatypes in ML (and hence MIFFS) are linked lists. A list is either the null list, written [], or a node containing a head, which can hold any value (including another list), and a tail, which is a list (of the same type). You can constuct one of these nodes by joining a value to the front of a list, using the :: operator, known as "cons". You can also write lists a bit like tuples, using square brackets.

[]
val ans = [] : α list
1::[]
val ans = [1] : int list
[1,2,3]
val ans = [1,2,3] : int list
[3]::[[1]]
val ans = [[3], [1]] : (int list) list
[sin, cos]
val ans = [fn, fn] : (α -> α) list

There are some basic list operations built in: cons ::, list concatenation @, list reversal rev and map, which applies a function to every element of a list:

[1,2] @ [3,4]
val ans = [1,2,3,4] : int list
rev [1,2,3]
val ans = [3, 2, 1] : int list
map sin [0, pi/2, pi]
val ans = [0.0, 1.0, 0.0] : real list

map is a very useful function for calculations as well as writing programs: it can be a very easy way to perform a repetitive calculation.

Functions by Cases - Pattern Matching

If you define a function as we saw earlier, for example:

fun f (a, b) = a+b
val f = fn : α -> α

Then when it is applied to a value, MIFFS attempts to bind the argument to the pattern (a,b). This means it will ensure the argument is a 2-tuple, and bind its components to a and b respectively. What if this is not possible? In this case, it is forced to give up, and throws an exception. But you can give it alternatives if you define the function by cases:

fun len [] = 0 | len x::xs = 1 + len xs
fun len = fn : α -> α
len [1,2,3,4,5]
ans = 5 : int

In this example, MIFFS first tests [1,2,3,4,5] to see if it can unify it with []. As it cannot, it moves on to the next pattern.

The next pattern is x :: xs, which it can unify with 1 :: [2,3,4,5], so the result of the function is (1 + len [2,3,4,5]), which in turn is expanded to (1 + 1 + len [3,4,5]) and so on.

There is a wildcard pattern, "_", which matches anything -- and ignores it.

fun hd x::_ = x
fun hd = fn : α -> α
fun ignore _ = ()
fun ignore = fn : α -> α

An Example - Mergesort

We have enough language constructs to make a pretty version of mergesort now:

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

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

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

mergesort [2,4,6,2,1,8,4,2,6,4,3]
ans = [1, 2, 2, 2, 3, 4, 4, 4, 6, 6, 8] : int list

This is the end of the intermediate section: it's not very long, I'm afraid. It's much more fun writing MIFFS than writing these tutorials! Check out the functions page and the formal language definition to see what else you can do, if you like. Have fun with sums!