Here is a screen capture of SML examples similar to class. Each input is meant to illustrate something. The remaining errors are instructive. The Greatest common divisor function. It is designed for the first argument to be smaller than the second: - fun gcd(small, large) = if small=0 then large = else gcd(large mod small, small); val gcd = fn : int * int -> int - gcd(12,15); val it = 3 : int - gcd(55,77); val it = 11 : int - gcd(31,32); val it = 1 : int - gcd(17*11*3, 17*7*19); val it = 17 : int Here is is put inside a "wrapper" function which makes sure the first argument is smaller: - fun gcd2(a,b) = if a int - gcd2(55,44); val it = 11 : int Given a list of integers, we compute the sum of its elements with a recursive method. Add the head to the sum of elements in the tail. The base case is that we output 0 for an empty list, (the identity element for addition). - fun sum(L) = if L=[] then 0 else hd(L)+sum(tl(L)); val sum = fn : int list -> int - sum([1,2,3,10]); val it = 16 : int - sum([]); val it = 0 : int - sum(z); val it = 36 : int Now do the analogous thing to find the max of all elements in a list of integers. First we make a max operation for two integers: - fun max(a,b) = if a>b then a else b; val max = fn : int * int -> int - max(3,4); val it = 4 : int - max(4,3); val it = 4 : int Now a recursive method, maxL(), to find the maximum element of a list. Just take the max of the head with the maxL of the tail. The base case is that we want to output negative infinity for an empty list, because this is the identity element for max, but we use -1 here: - fun maxL(L) = if L=[] then ~1 else max(hd(L), maxL(tl(L))); val maxL = fn : int list -> int - maxL(z); val it = 8 : int - maxL([0]); val it = 0 : int - maxL([]); val it = ~1 : int The above took lists apart, but did not build lists. We can build lists using the "@" operation: - [1] @ [2,3,4,5]; val it = [1,2,3,4,5] : int list The "cons" operator (for "construct") combines an element and a list to make a larger list. The element becomes the head of the resulting list. The list which is given as the second argument to cons becomes the tail of the new list. The cons operator is written with two colons, as "::". - 1 :: [2,3,4,5]; val it = [1,2,3,4,5] : int list Note the element goes on the left and the list on the right. The opposite would generate an error: - [2,3]::1; stdIn:129.1-129.9 Error: operator and operand don't agree [literal] operator domain: int list * int list list operand: int list * int in expression: (2 :: 3 :: nil) :: 1 Lets write a recursive function to create a list with n zeros: - fun zeros(n) = if n=0 then [] else 0::zeros(n-1); val zeros = fn : int -> int list - zeros(7); val it = [0,0,0,0,0,0,0] : int list Lets make a function to generate a "countdown to zero" list. Simply cons n to the front of a smaller countdown list. The base case is that for n=0 we return [0]: - fun down(n) = if n=0 then [0] else n::down(n-1); val down = fn : int -> int list - down(7); val it = [7,6,5,4,3,2,1,0] : int list Combining it with the sum() method from above, we can sum the numbers from 1 to 10: - sum(down(10)); val it = 55 : int Here is the sum of the numbers from 1 to 100: - sum(down(100)); val it = 5050 : int If we want to count up instead, the n goes at the right, so we use the catenation idea instead of consing, because cons only adds an element to the left: - fun up(n) = if n=0 then [0] else up(n-1)@[n]; val up = fn : int -> int list - up(20); val it = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] : int list We can try our maxL() method on that list: - maxL(up(20)); val it = 20 : int A function to reverse a list: The base case is easy; there is no problem reversing an empty list. The general case is to combine the reverse of the tail with the head. we need to catenate, not cons, because the element goes at the end (and cons only builds at the front). Catenation requires two lists, so we put square brackets around the head element, making it a one-element list: - fun rev(L) = if L=[] then [] else rev(tl(L)) @ [hd(L)]; val rev = fn : ''a list -> ''a list - rev(z); val it = [8,7,6,5,4,3,2,1] : int list - rev(rev(z)); val it = [1,2,3,4,5,6,7,8] : int list With reverse(), we could write another version of up() using down(): - fun up2(n) = rev(down(n)); val up2 = fn : int -> int list - up2(50); val it = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27, 28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50] : int list - up(50); val it = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27, 28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50] : int list Recall how we used map to compute the square of each element in a list: - fun s(n) = n*n; val s = fn : int -> int - map s z; val it = [1,4,9,16,25,36,49,64] : int list Lets write our own function like map, which will make a list of the squares of the elements of a given list. Simply square the head of a list and cons that with squaring everything in the tail: - fun mapsq(L) = if L=[] then [] else s(hd(L)) :: mapsq(tl(L)); val mapsq = fn : int list -> int list - mapsq(z); val it = [1,4,9,16,25,36,49,64] : int list Here is the same idea, but add 1 to ("increment") each element of a list: - fun inc(L) = if L=[] then [] else hd(L)+1 :: inc(tl(L)); val inc = fn : int list -> int list - inc (z); val it = [2,3,4,5,6,7,8,9] : int list Lets write a function to extract the nth element from a list, (We assume it has at least n elements, so we don't check for errors.) If you want the first element, easy, that is the head. If you want an element after the first, it is the n-minus-first element of the tail: - fun extract(n,L) = if n=0 then hd(L) else = extract(n-1, tl(L)); val extract = fn : int * 'a list -> 'a - extract(0, [1,2,3]); val it = 1 : int - extract(3, ["a", "b", "c", "d"]); val it = "d" : string It will generate an error if n does not make sense for the list: - extract(100,z); uncaught exception Empty raised at: boot/list.sml:37.38-37.43 To convert n to binary, the "rightmost" bit is easy: it is n mod 2. In a recursive program, we can create everything left of the rightmost bit by converting half of n to binary, i.e., apply the function we are writing to n div 2. We can add a bit to the right by using @ (as above). Finally, a base case is that when n=0 we can create a list [0]: - fun bin(n) = if n=0 then [0] else = bin(n div 2) @ [n mod 2]; val bin = fn : int -> int list - bin(13); val it = [0,1,1,0,1] : int list - bin(6); val it = [0,1,1,0] : int list - map bin z; val it = [[0,1],[0,1,0],[0,1,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],[0,1,0,0,0]] : int list list The base case [0] makes sense if we need 0 to appear as: - bin(0); val it = [0] : int list But we may prefer to remove all leading zeros with this base case: - fun bin(n) = if n=0 then [] else bin(n div 2) @ [n mod 2]; val bin = fn : int -> int list - map bin z; val it = [[1],[1,0],[1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1],[1,0,0,0]] : int list list - bin(0); val it = [] : int list Reversing the above bit sequence, so 2 converts to [0,1] instead of [1,0] would result if we cons the 1's bit to the front instead of appending it to the end. So now the bit with value 2-to-the-i in in position i of the list (assuming 0-based indexing): - fun bin(n) = if n=0 then [] else (n mod 2)::bin(n div 2); - bin(2); val it = [0,1] : int list One last SML example is to generate the power set. This is a good exercise for keeping track of your containers, since we deal with lists of lists, that represent sets of sets. First we define a function to insert an x into every element of a list of lists. Recall the mapsquare(L) method we defined above, which squared each element of a list. Instead of squaring the head of the list, we make a longer list as (x::hd(L)) and this is consed to the recursive call on the tail. The base case is that if there are no lists to insert to, we return []: - fun add(x,L) = if L=[] then [] else (x::hd(L))::add(x,tl(L)); val add = fn : ''a * ''a list list -> ''a list list Here we apply it to add 1 as the head of each of the lists listed here: - add(1, [[2,3], [], [4,5,6,7]]); val it = [[1,2,3],[1],[1,4,5,6,7]] : int list list With that helper function, we can write a function to create the power set P(S). (The elements of a set are unordered, but the elements of a list must be in some order, so we will be happy with the correct elements in any order.) The key idea is that for any element x in S, half the elements in P(S) have x and half don't. The half that don't contain x form the power set of S-{x}. This gives a simple recursive algorithm. Note the base case result is [[]], because the power set of the empty set is the set containing the empty set. - fun P(S) = if S=[] then [[]] else = P(tl(S)) @ add(hd(S),P(tl(S))); val P = fn : ''a list -> ''a list list Try it out: - P([1,2,3]); val it = [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]] : int list list (The peculiar output order is due to the details of the algorithm. We could use a separate function to sort everything.) Try a larger example, with 256 elements in the result: - P([1,2,3,4,5,6,7,8]); val it = [[],[8],[7],[7,8],[6],[6,8],[6,7],[6,7,8],[5],[5,8],[5,7],[5,7,8],...] : int list list They don't all print out until we do this: - Compiler.Control.Print.printLength := 1000; val it = () : unit - P([1,2,3,4,5,6,7,8]); val it = [[],[8],[7],[7,8],[6],[6,8],[6,7],[6,7,8],[5],[5,8],[5,7],[5,7,8],[5,6], [5,6,8],[5,6,7],[5,6,7,8],[4],[4,8],[4,7],[4,7,8],[4,6],[4,6,8],[4,6,7], [4,6,7,8],[4,5],[4,5,8],[4,5,7],[4,5,7,8],[4,5,6],[4,5,6,8],[4,5,6,7], [4,5,6,7,8],[3],[3,8],[3,7],[3,7,8],[3,6],[3,6,8],[3,6,7],[3,6,7,8],[3,5], [3,5,8],[3,5,7],[3,5,7,8],[3,5,6],[3,5,6,8],[3,5,6,7],[3,5,6,7,8],[3,4], [3,4,8],[3,4,7],[3,4,7,8],[3,4,6],[3,4,6,8],[3,4,6,7],[3,4,6,7,8],[3,4,5], [3,4,5,8],[3,4,5,7],[3,4,5,7,8],[3,4,5,6],[3,4,5,6,8],[3,4,5,6,7], [3,4,5,6,7,8],[2],[2,8],[2,7],[2,7,8],[2,6],[2,6,8],[2,6,7],[2,6,7,8],[2,5], [2,5,8],[2,5,7],[2,5,7,8],[2,5,6],[2,5,6,8],[2,5,6,7],[2,5,6,7,8],[2,4], [2,4,8],[2,4,7],[2,4,7,8],[2,4,6],[2,4,6,8],[2,4,6,7],[2,4,6,7,8],[2,4,5], [2,4,5,8],[2,4,5,7],[2,4,5,7,8],[2,4,5,6],[2,4,5,6,8],[2,4,5,6,7], [2,4,5,6,7,8],[2,3],[2,3,8],[2,3,7],[2,3,7,8],[2,3,6],[2,3,6,8],[2,3,6,7], [2,3,6,7,8],[2,3,5],[2,3,5,8],[2,3,5,7],[2,3,5,7,8],[2,3,5,6],[2,3,5,6,8], [2,3,5,6,7],[2,3,5,6,7,8],[2,3,4],[2,3,4,8],[2,3,4,7],[2,3,4,7,8],[2,3,4,6], [2,3,4,6,8],[2,3,4,6,7],[2,3,4,6,7,8],[2,3,4,5],[2,3,4,5,8],[2,3,4,5,7], [2,3,4,5,7,8],[2,3,4,5,6],[2,3,4,5,6,8],[2,3,4,5,6,7],[2,3,4,5,6,7,8],[1], [1,8],[1,7],[1,7,8],[1,6],[1,6,8],[1,6,7],[1,6,7,8],[1,5],[1,5,8],[1,5,7], [1,5,7,8],[1,5,6],[1,5,6,8],[1,5,6,7],[1,5,6,7,8],[1,4],[1,4,8],[1,4,7], [1,4,7,8],[1,4,6],[1,4,6,8],[1,4,6,7],[1,4,6,7,8],[1,4,5],[1,4,5,8], [1,4,5,7],[1,4,5,7,8],[1,4,5,6],[1,4,5,6,8],[1,4,5,6,7],[1,4,5,6,7,8],[1,3], [1,3,8],[1,3,7],[1,3,7,8],[1,3,6],[1,3,6,8],[1,3,6,7],[1,3,6,7,8],[1,3,5], [1,3,5,8],[1,3,5,7],[1,3,5,7,8],[1,3,5,6],[1,3,5,6,8],[1,3,5,6,7], [1,3,5,6,7,8],[1,3,4],[1,3,4,8],[1,3,4,7],[1,3,4,7,8],[1,3,4,6],[1,3,4,6,8], [1,3,4,6,7],[1,3,4,6,7,8],[1,3,4,5],[1,3,4,5,8],[1,3,4,5,7],[1,3,4,5,7,8], [1,3,4,5,6],[1,3,4,5,6,8],[1,3,4,5,6,7],[1,3,4,5,6,7,8],[1,2],[1,2,8], [1,2,7],[1,2,7,8],[1,2,6],[1,2,6,8],[1,2,6,7],[1,2,6,7,8],[1,2,5],[1,2,5,8], [1,2,5,7],[1,2,5,7,8],[1,2,5,6],[1,2,5,6,8],[1,2,5,6,7],[1,2,5,6,7,8], [1,2,4],[1,2,4,8],[1,2,4,7],[1,2,4,7,8],[1,2,4,6],[1,2,4,6,8],[1,2,4,6,7], [1,2,4,6,7,8],[1,2,4,5],[1,2,4,5,8],[1,2,4,5,7],[1,2,4,5,7,8],[1,2,4,5,6], [1,2,4,5,6,8],[1,2,4,5,6,7],[1,2,4,5,6,7,8],[1,2,3],[1,2,3,8],[1,2,3,7], [1,2,3,7,8],[1,2,3,6],[1,2,3,6,8],[1,2,3,6,7],[1,2,3,6,7,8],[1,2,3,5], [1,2,3,5,8],[1,2,3,5,7],[1,2,3,5,7,8],[1,2,3,5,6],[1,2,3,5,6,8], [1,2,3,5,6,7],[1,2,3,5,6,7,8],[1,2,3,4],[1,2,3,4,8],[1,2,3,4,7], [1,2,3,4,7,8],[1,2,3,4,6],[1,2,3,4,6,8],[1,2,3,4,6,7],[1,2,3,4,6,7,8], [1,2,3,4,5],[1,2,3,4,5,8],[1,2,3,4,5,7],[1,2,3,4,5,7,8],[1,2,3,4,5,6], [1,2,3,4,5,6,8],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]] : int list list Check if all 256 of them are there: - length(P([1,2,3,4,5,6,7,8])); val it = 256 : int