Unlike most of the other languages I have described, SML is a functional language operating on a very high level. This makes it possible in very short statements to express even very difficult problems in very short statements. In the beginning, I, like many others, disliked the functional approach to the solutions, but once I learned the strength and disadvantages of the functional approach, I came to like it. Especially the possibility of creating type-independent functions are very powerful.
To more precisely show the structure of the language, I will show you some code:
fun g(n) = n + 4;
fun g: int -> int
This code defines a function with the name g. g takes a parameter, n (of type int) and returns an int equal to n+4.
Unlike imperative languages, you cannot assign a value to n (n is not a variable - it is a value) so you have to take a different approach to many programming questions.
Lets take a more complex piece of code:
fun fact (0) = 1
| fact (n) = fact(n-1)*n;
fun fact: int -> int
This defines the factorial function - see how it recursively calls itself. You cannot apply the usual iterative solution to this problem (the solution where you loop through all values and multiply) since you do not have access to structures such as loops
In programming you often need to manipulate lists of items. In SML, a list is a native type and consists of an series of items of the same type. When using lists in SML it is important to realise that most of the time you do not index your list like an array, but instead you process it one item at a time from the beginning to the end by extracting the first element. This could look like this:
fun insert(y, []) = [y]
| insert(y, a::al) = if y<a then y::a::al else a::insert(y, al);
fun insert: int list -> int list
This code will insert an element (y) in an ordered list a. This is done by keep taking the first element off the list, and if it is less than y (the element to insert) y is placed in front of the list created by putting a in front of the list al (thats what :: means). If the list is empty ([]), y is returned as the sole element in a list. You also see how the function uses itself to recursively insert the element in the rest of the list if the condition is not fulfilled.
Pretty simply uptill now, don't you think. But just you wait and see what I have for you!
fun rev([]) = []
| rev(x::xl) = rev(xl) @ [x];
fun rev: 'a list -> 'a list
Now, what does this code do? Well, lets see...
It picks the first element (x) off a list, the remainder known as xl. Calls itself on the remaining list and puts the result in front of the list created by the element it picked from the input (the @ is append). So in essence, it reverses the list. Now unlike before, where we had a type for the list, the type is now 'a. This is because the ML interpreter concluded, that no particular type was required by the function, so it decided that any type would do. Only thing it could tell without doubt was the fact that the elements in the output is of same type as the ones in the input.
Well, in C/C++/Pascal, we had pointers to functions. In ML, we have higher-order functions. They work the same way but are a bit more delicately implemented in ML. Basically, it is possible to for instance do the following:
fun map _ ( [] ) = []
| map f ( x::xl ) = (f(x))::(map f (xl))
fun map: ('a -> 'b) -> 'a list -> 'b list
What?!?!? - well, simple once you see it. It picks the first element off the input, applies f (which then must be a function) on the element and puts the result in front of the list created by doing the same for the rest of the elements (in essence, it applies the same function on the entire list). A very powerful function worth studying.
For your pleasure, I wrote the two basic sorting functions - Insertion- and Quicksort - just to show you how small and powerful the language is:
local
fun insert(x, []) = [x]
| insert(x, y::L) = if (x<y) then x::y::L else y::insert(x,L)
in
fun bubblesort([]) = []
| bubblesort(x::L) = insert(x, bubblesort(L));
end;
fun quicksort([]) = []
| quicksort(x::L) =
let
val (M,N) = List.partition (fn y => y<x) (L)
in
quicksort( M ) @ [x] @ quicksort( N )
end
Michael R. Hansen & Hans Rischel: Introduction to programming using SML [Addison-Wesley, ISBN:0-201-39820-6]
A very good introduction to ML written by to persons from this university!
Please note that there may be errors in the code, since it is untested even though unlikely. Of course, no warranties of any kind are given!