Editing Standard ML (section)

==Code examples==
{{wikibook|Standard ML Programming}}
{{unreferenced section|date=June 2013}}
Snippets of SML code are most easily studied by entering them into an [[Read–eval–print loop|interactive top-level]].

===Hello, world!===
The following is a [["Hello, World!" program]]:

{| class="wikitable"
|-
! hello.sml
|-
|
<syntaxhighlight lang="sml" line>
print "Hello, world!\n";
</syntaxhighlight>
|-
! sh
|-
|
<syntaxhighlight lang="console">
$ mlton hello.sml
$ ./hello
Hello, world!
</syntaxhighlight>
|}

===Algorithms===
====Insertion sort====
Insertion sort for {{code|lang=sml|int list}} (ascending) can be expressed concisely as follows:

<syntaxhighlight lang="sml">
fun insert (x, []) = [x] | insert (x, h :: t) = sort x (h, t)
and sort x (h, t) = if x < h then [x, h] @ t else h :: insert (x, t)
val insertionsort = List.foldl insert []
</syntaxhighlight>

====Mergesort====
{{main|Merge sort}}

Here, the classic mergesort algorithm is implemented in three functions: split, merge and mergesort. Also note the absence of types, with the exception of the syntax {{code|lang=sml|op ::}} and {{code|lang=sml|[]}} which signify lists. This code will sort lists of any type, so long as a consistent ordering function {{code|cmp}} is defined. Using [[Hindley–Milner type inference]], the types of all variables can be inferred, even complicated types such as that of the function {{code|cmp}}.

'''Split'''

{{code|lang=sml|fun split}} is implemented with a [[State (computer science)|stateful]] closure which alternates between {{code|true}} and {{code|false}}, ignoring the input:

<syntaxhighlight lang="sml">
fun alternator {} = let val state = ref true
    in fn a => !state before state := not (!state) end

(* Split a list into near-halves which will either be the same length,
 * or the first will have one more element than the other.
 * Runs in O(n) time, where n = |xs|.
 *)
fun split xs = List.partition (alternator {}) xs
</syntaxhighlight>

'''Merge'''

Merge uses a local function loop for efficiency. The inner {{code|loop}} is defined in terms of cases: when both lists are non-empty ({{code|lang=sml|x :: xs}}) and when one list is empty ({{code|lang=sml|[]}}).

This function merges two sorted lists into one sorted list. Note how the accumulator {{code|acc}} is built backwards, then reversed before being returned. This is a common technique, since {{code|lang=sml|'a list}} is represented as a [[Linked list#Linked lists vs. dynamic_arrays|linked list]]; this technique requires more clock time, but the [[Asymptotic analysis#Applications|asymptotics]] are not worse.

<syntaxhighlight lang="sml">
(* Merge two ordered lists using the order cmp.
 * Pre: each list must already be ordered per cmp.
 * Runs in O(n) time, where n = |xs| + |ys|.
 *)
fun merge cmp (xs, []) = xs
  | merge cmp (xs, y :: ys) = let
    fun loop (a, acc) (xs, []) = List.revAppend (a :: acc, xs)
      | loop (a, acc) (xs, y :: ys) =
        if cmp (a, y)
        then loop (y, a :: acc) (ys, xs)
        else loop (a, y :: acc) (xs, ys)
    in
        loop (y, []) (ys, xs)
    end
</syntaxhighlight>

'''Mergesort'''

The main function:

<syntaxhighlight lang="sml">
fun ap f (x, y) = (f x, f y)

(* Sort a list in according to the given ordering operation cmp.
 * Runs in O(n log n) time, where n = |xs|.
 *)
fun mergesort cmp [] = []
  | mergesort cmp [x] = [x]
  | mergesort cmp xs = (merge cmp o ap (mergesort cmp) o split) xs
</syntaxhighlight>

====Quicksort====
{{main|Quicksort}}

Quicksort can be expressed as follows. {{code|lang=sml|fun part}} is a [[Closure (computer programming)|closure]] that consumes an order operator {{code|lang=sml|op <<}}.

<syntaxhighlight lang="sml">
infix <<

fun quicksort (op <<) = let
    fun part p = List.partition (fn x => x << p)
    fun sort [] = []
      | sort (p :: xs) = join p (part p xs)
    and join p (l, r) = sort l @ p :: sort r
    in
        sort
    end
</syntaxhighlight>

===Expression interpreter===
Note the relative ease with which a small expression language can be defined and processed:

<syntaxhighlight lang="sml">
exception TyErr;

datatype ty = IntTy | BoolTy

fun unify (IntTy, IntTy) = IntTy
  | unify (BoolTy, BoolTy) = BoolTy
  | unify (_, _) = raise TyErr

datatype exp
    = True
    | False
    | Int of int
    | Not of exp
    | Add of exp * exp
    | If  of exp * exp * exp

fun infer True = BoolTy
  | infer False = BoolTy
  | infer (Int _) = IntTy
  | infer (Not e) = (assert e BoolTy; BoolTy)
  | infer (Add (a, b)) = (assert a IntTy; assert b IntTy; IntTy)
  | infer (If (e, t, f)) = (assert e BoolTy; unify (infer t, infer f))
and assert e t = unify (infer e, t)

fun eval True = True
  | eval False = False
  | eval (Int n) = Int n
  | eval (Not e) = if eval e = True then False else True
  | eval (Add (a, b)) = (case (eval a, eval b) of (Int x, Int y) => Int (x + y))
  | eval (If (e, t, f)) = eval (if eval e = True then t else f)

fun run e = (infer e; SOME (eval e)) handle TyErr => NONE
</syntaxhighlight>

Example usage on well-typed and ill-typed expressions:
<syntaxhighlight lang="sml">
val SOME (Int 3) = run (Add (Int 1, Int 2)) (* well-typed *)
val NONE = run (If (Not (Int 1), True, False)) (* ill-typed *)
</syntaxhighlight>

===Arbitrary-precision integers===
The {{code|IntInf}} module provides arbitrary-precision integer arithmetic. Moreover, integer literals may be used as arbitrary-precision integers without the programmer having to do anything.

The following program implements an arbitrary-precision factorial function:

{| class="wikitable"
|-
! fact.sml
|-
|
<syntaxhighlight lang="sml" line>
fun fact n : IntInf.int = if n = 0 then 1 else n * fact (n - 1);

fun printLine str = TextIO.output (TextIO.stdOut, str ^ "\n");

val () = printLine (IntInf.toString (fact 120));
</syntaxhighlight>
|-
! bash
|-
|
<syntaxhighlight lang="console">
$ mlton fact.sml
$ ./fact
6689502913449127057588118054090372586752746333138029810295671352301
6335572449629893668741652719849813081576378932140905525344085894081
21859898481114389650005964960521256960000000000000000000000000000
</syntaxhighlight>
|}

===Partial application===
Curried functions have many applications, such as eliminating redundant code. For example, a module may require functions of type {{code|lang=sml|a -> b}}, but it is more convenient to write functions of type {{code|lang=sml|a * c -> b}} where there is a fixed relationship between the objects of type {{code|a}} and {{code|c}}. A function of type {{code|lang=sml|c -> (a * c -> b) -> a -> b}} can factor out this commonality. This is an example of the [[adapter pattern]].{{Citation needed|date=May 2015}}

In this example, {{code|lang=sml|fun d}} computes the numerical derivative of a given function {{code|f}} at point {{code|x}}:

<syntaxhighlight lang="sml" highlight="1">
- fun d delta f x = (f (x + delta) - f (x - delta)) / (2.0 * delta)
val d = fn : real -> (real -> real) -> real -> real
</syntaxhighlight>

The type of {{code|lang=sml|fun d}} indicates that it maps a "float" onto a function with the type {{code|lang=sml|(real -> real) -> real -> real}}. This allows us to partially apply arguments, known as [[currying]]. In this case, function {{code|d}} can be specialised by partially applying it with the argument {{code|delta}}. A good choice for {{code|delta}} when using this algorithm is the cube root of the [[machine epsilon]].{{Citation needed|date=August 2008}}

<syntaxhighlight lang="sml" highlight="1">
- val d' = d 1E~8;
val d' = fn : (real -> real) -> real -> real
</syntaxhighlight>

The inferred type indicates that {{code|d'}} expects a function with the type {{code|lang=sml|real -> real}} as its first argument. We can compute an approximation to the derivative of <math>f(x) = x^3-x-1</math> at <math>x=3</math>. The correct answer is <math>f'(3) = 27-1 = 26</math>.

<syntaxhighlight lang="sml" highlight="1">
- d' (fn x => x * x * x - x - 1.0) 3.0;
val it = 25.9999996644 : real
</syntaxhighlight>