For this project, your ML program does not need to read any input from the user.  You should test your ML functions by using them interactively in the ML shell.

ML is concise and elegant compared to common languages such as Java and C. It may be harder to write the first version of a program in ML than in C, but it is much easier to write a program in ML that is perfectly bug-free.  The beauty of ML is that if a program compiles successfully, it is much more likely to be correct than a similar program in a lower-level language such as C or Java.  All computer science requires attention to detail. ML does even more than C, but there are many details that ML takes care of completely automatically, such as memory allocation.

If your program gets correct answers for easy sequences, it is very likely to be correct for all sequences. But it may use too much memory.  If you implement iterative deepening as described in the handout, in a simple and elegant way, you won't use too much memory.

The ML compiler is very good at implementing recursive functions and recursive data structures efficiently. If your translation into C is less efficient than the ML compiler, then it is possible for your C version to be much slower.  If your C version is much slower than expected on machine A, but fast on machine B, one possible explanation is excessive paging on A. If your program uses a lot of memory, and B has enough main memory, but A does not, then swapping of virtual memory can make A hundreds of times slower. You can use "top" under Unix to see how much memory each process is using.

When you expand all leaf nodes, the number of expressions at depth 1 is 1, depth 2 is 20, depth 3 is 20*40, depth 4 is 20*40*60 etc. The number of leaves is the same as the depth.

If you use your human intelligence to figure out the answers for the test cases, you can see what depth the answers will be at for your program. Note that different programs may have slightly different definitions of depth.  How to figure out the answer yourself? Try looking at the first derivative, the second derivative, etc. For example:

0.5 2 4.5 8
1.5 2.5 3.5
1 1

With some further algebra you get that the formula is 0.5n^2 + n + 0.5. There are various ways of writing this expression with as few leaves as possible where each leaf is either n or 1. One way is (n+1)*(n+1)/(1+1) which has six leaves. So your program needs to be able to search up to at least six leaves without running out of memory.

Note that the evaluation function explained in section does not take a string as an argument. It takes an expression, in the form of the recursive expression datatype defined before. And again you must execute eval for every candidate formula solution for n = 0...n, where n is the length of the list minus 1.

You can think of a state as the symbolic arithmetic expression represented by the tree X. Two different trees could represent expressions that are equivalent, due to commutativity etc. So state(X) might be a non-trivial computation depending on X.

But for this project you can ignore this extra difficulty. You can assume that state(X) just means X, for simplicity.

You may make these assumptions:
(1) The input list will always have length between 1 and 6.
(2) If an expression can yield division by zero for some n >= 0, then it is not a valid solution.  For example 1/n and 1/(n-3) are not valid, but 1/(n+2) is valid.

Given a sequence of numbers, if the expression that is the answer has d leaves, then it takes time exponential in d to find this answer.  You need to make sure that your implementation only uses space that is polynomial in d, even though the time used is exponential in d.  Otherwise, you will run out of memory ("stack overflow") way before you run out of patience.  The big-O time and space usage of DFS etc. is discussed in the handout on iterative deepening.

Consider the example

datatype 'a b_tree = Empty | Node of 'a b_tree * 'a * 'a b_tree;

As stated in the project description, you should assume that the input is always a list of reals, not a list of integers: val solve = fn : real list -> real list If your code uses integers now, you'll have to make changes in a few places, but not many.  Remember that real constants have a decimal point, such as 1.0. Also remember that = is defined for integers but not for reals.

Whether you use integers or reals, you need to define your own "safe" functions for division and power, to deal with division by zero and 0^0.

If you have a function that only accepts lists of integers, most likely you have used an operation that only exists for integers somewhere. The automatic type inference will then assume that you mean integers only. Remember that real constants have a decimal point, such as 1.0. Also remember that = is defined for integers but not for reals.

To call the exponential and ln functions in ML just call Math.exp and Math.ln, respectively. For example, typing Math.exp(0.0); returns 1.0 and Math.ln(1.0); returns 0.0. Both functions take and return reals.  When a calculation with real numbers is performed, the answer may not be precisely correct. So Math.pow(2.0,3.0) may be slightly less than 8. And when a real number is printed, it is rounded. So the number slightly less than 8 may be printed as 8.0.  Results that are not perfectly accurate are the reason why equality testing is not allowed for real numbers in ML.

You have to think differently when programming in ML. Often, instead of using assignment and looping, you use recursion and build new values using old ones.  For example, here is a function that creates a list of integers from 1 to n:

fun range n = if n=0 then [] else (range (n-1))@[n]

A note about ML efficiency, and being wary about how you use language features [by Greg Hamerly]:

Suppose you want to build a list of numbers in ML. You could use the :: operator to prepend element E to the beginning of list L, like this: (E::L). Doing this is constant-time, since it simply puts E at the start of L, and the start of L is known.  Another option is to use the @ operator to append an element E to a list L, like this: L @ [E]. However, this option requires searching to the end of L every time, which is an O(n) operation (where n is the length of list L).  If we need to create a list of n numbers, then using :: is linear in time (O(n)), while using @ is quadratic in time (O(n^2)). I performed a simple timing test to show this:

fun timeit f a =
    let
        val ct = Timer.startRealTimer()
        val result = f a
    in
        (result, Timer.checkRealTimer(ct))
    end;

fun prepend x max list =
    if (x > max) then list
    else prepend (x+1) max (x::list);

fun append x max list =
    if (x > max) then list
    else append (x+1) max (list @ [x]);

- timeit (prepend 0 10000) [];
val it = ([10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,9989,...],
TIME {sec=0,usec=354}) : int list * Time.time

- timeit (append 0 10000) [];
val it = ([0,1,2,3,4,5,6,7,8,9,10,11,...],TIME {sec=3,usec=282373})
: int list * Time.time