Content deleted Content added
JackNocturne (talk | contribs) m Adding a back reference to Kotlin article (Influenced) |
m Task 70: Update syntaxhighlight tags - remove use of deprecated <source> tags |
||
Line 39:
The [[factorial]] function expressed as pure ML:
<
fun fac (0 : int) : int = 1
| fac (n : int) : int = n * fac (n - 1)
</syntaxhighlight>
This describes the factorial as a recursive function, with a single terminating base case. It is similar to the descriptions of factorials found in mathematics textbooks. Much of ML code is similar to mathematics in facility and syntax.
Line 48:
Part of the definition shown is optional, and describes the ''types'' of this function. The notation E : t can be read as ''expression E has type t''. For instance, the argument n is assigned type ''integer'' (int), and fac (n : int), the result of applying fac to the integer n, also has type integer. The function fac as a whole then has type ''function from integer to integer'' (int -> int), that is, fac accepts an integer as an argument and returns an integer result. Thanks to type inference, the type annotations can be omitted and will be derived by the compiler. Rewritten without the type annotations, the example looks like:
<
fun fac 0 = 1
| fac n = n * fac (n - 1)
</syntaxhighlight>
The function also relies on pattern matching, an important part of ML programming. Note that parameters of a function are not necessarily in parentheses but separated by spaces. When the function's argument is 0 (zero) it will return the integer 1 (one). For all other cases the second line is tried. This is the [[recursion]], and executes the function again until the base case is reached.
Line 57:
This implementation of the factorial function is not guaranteed to terminate, since a negative argument causes an [[infinite descending chain]] of recursive calls. A more robust implementation would check for a nonnegative argument before recursing, as follows:
<
fun fact n = let
fun fac 0 = 1
Line 65:
else fac n
end
</syntaxhighlight>
The problematic case (when n is negative) demonstrates a use of ML's [[exception handling|exception system]].
Line 71:
The function can be improved further by writing its inner loop in a [[tail-recursive]] style, such that the [[call stack]] need not grow in proportion to the number of function calls. This is achieved by adding an extra, "accumulator", parameter to the inner function. At last, we arrive at
<
fun fact n = let
fun fac 0 acc = acc
Line 79:
else fac n 1
end
</syntaxhighlight>
===List reverse===
The following function "reverses" the elements in a list. More precisely, it returns a new list whose elements are in reverse order compared to the given list.
<
fun reverse [] = []
| reverse (x::xs) = (reverse xs) @ [x]
</syntaxhighlight>
This implementation of reverse, while correct and clear, is inefficient, requiring [[quadratic time]] for execution. The function can be rewritten to execute in [[linear time]] in the following more efficient, though less easy-to-read, style:
<
fun reverse xs = let
fun rev [] acc = acc
Line 98:
rev xs []
end
</syntaxhighlight>
Notably, this function is an example of parametric polymorphism. That is, it can consume lists whose elements have any type, and return lists of the same type.
Line 105:
Modules are ML's system for structuring large projects and libraries. A module consists of a signature file and one or more structure files. The signature file specifies the [[API]] to be implemented (like a C header file, or Java interface file). The structure implements the signature (like a C source file or Java class file). For example, the following define an Arithmetic signature and an implementation of it using Rational numbers:
<
signature ARITH =
sig
Line 114:
val sum : t * t -> t;
end
</syntaxhighlight>
<
structure Rational : ARITH =
struct
Line 124:
fun sum (Rat(a,b), Rat(c,d)) = Rat(a*d+ c*b , b*d) : t ;
end
</syntaxhighlight>
These are imported into the interpreter by the 'use' command. Interaction with the implementation is only allowed via the signature functions, for example it is not possible to create a 'Rat' data object directly via this code. The 'structure' block hides all the implementation detail from outside.
| |||