ML语言
ML（Meta Language：元语言），是一个函数式、指令式的通用的编程语言，它著称于使用了多态的Hindley–Milner类型推论。ML能自动的指定多数的类型，不要求显式的类型标注，而且能够确保类型安全，已经正式证明了有良好类型的ML程序不会导致运行时间类型错误。
ML提供了对函数实际参数的模式匹配、垃圾回收、指令式编程、传值调用和柯里化。它被大量的用于编程语言研究之中，并且是全面规定了的和使用形式语义验证了的少数语言之一。它的类型和模式匹配使得它非常适合并且经常用于在其他形式语言上进行操作，比如在编译器构造、自动化定理证明和形式验证中。
在1970年代早期，ML由爱丁堡大学的罗宾·米尔纳及他人研制出来，用于在定理证明器中开发证明策略。LCF的语言是“PPλ”，它是一阶逻辑演算与有类型的多态λ演算的结合，以ML作为元语言。ML的语法从ISWIM及其扩展实现PAL得到了启发，LCF ML运行在DEC-10/TOPS-10主机的Stanford LISP下。
在1980年，于爱丁堡大学的VAX/VMS系统上开发了ML编译器，它被称为“VAX ML”，以区别于LCF版本的“DEC-10 ML”。VAX ML的编译器和运行时间系统二者，都是用Pascal书写而建立在“函数抽象机器”（FAM）之上。在1982年，爱丁堡大学的Kevin Mitchell，用VAX ML重写了VAX ML编译器，随即John Scott和加入了开发，在又进行一系列重写改进之后，新的编译器被称为“Edinburgh ML”。
在1981年，INRIA的，将最初的LCF ML适配到Multics系统的Maclisp下，并且增加了编译器。这个实现被描述于INRIA内部文档“ML手册”之中，它被开发者自称为“Le_ML”。剑桥大学的用它开发了基于Franz Lisp的Cambridge LCF，进而剑桥大学的又用它开发了基于Common Lisp的第一版的。
在1983年，Robin Milner由两个动机驱使开始重新设计ML。其一是爱丁堡大学的及其小组在规定上的工作，具体化为规定语言CLEAR，和表达可执行规定的函数式语言HOPE。这项工作与ML有关的是两方面成果：首先，HOPE拥有优雅的编程特征，特别是模式匹配，和子句式函数定义；其次，是使用在接口中的签名，进行规定的模块化构造的想法。其二是在VAX ML上的工作，通过增加命名记录和可变类型，扩展了ML中数据类型的品目。
在1984年，贝尔实验室的David MacQueen提出了对Standard ML的模块系统的设计。在Standard ML的持续设计期间，Edinburgh ML被渐进的修改，充当了Standard ML的近似原型实现。在1986年，普林斯顿大学的和贝尔实验室的David MacQueen，以Edinburgh Standard ML作为起步开发环境，开始了专注于生成高质量机器代码的Standard ML of New Jersey的活跃开发。
在1990年，Robin Milner、和制定的Standard ML的正式规定《The Definition of Standard ML》最终完成；在1997年，这个标准规定增补了David MacQueen为作者并进行了修订。在1989年，、Nick Rothwell和David N. Turner于爱丁堡大学开始开发ML Kit编译器，为了强调清晰性而非高效，将标准定义直接转译成一组Standard ML模块；在1992年和1993年期间，主要通过爱丁堡大学的Nick Rothwell和哥本哈根大学（DIKU）的Lars Birkedal的工作，ML Kit第一版完成并开源发行。
在1987年，INRIA的Ascánder Suárez，基于巴黎第七大学的的“”（CAM），利用Le Lisp的运行时间系统重新实现了Le_ML，并正式命名为Caml。在1990年和1991年，INRIA的基于用C实现的字节码解释器，利用提供的内存管理系统重新实现了Caml，并称其为Caml Light。在1995年，Xavier Leroy又增加了机器代码编译器和高层模块系统，这个版本也称为“Caml Special Light”。在1996年，INRIA的Didier Rémy和Jérôme Vouillon，向Caml Special Light增加了面向对象特征，从而形成了OCaml。
今天ML家族的两个主要的方言是Standard ML和OCaml。ML的实力大多被用于语言设计和操作，比如建构编译器、分析器、定理证明器，但是它作为通用语言也被用于生物信息和财务系统等领域。ML确立了静态类型函数式编程范型，从而在编程语言历史上占有显要地位，它的思想在影响了众多的语言，例如Haskell、Nemerle、和Elm。
ML代码片段很容易通过将其录入到“顶层”来研习，它也叫作读取﹣求值﹣输出循环或REPL。这是打印结果或定义的表达式的推论类型的交互式会话。很多SML实现提供交互式REPL，比如SML/NJ：
$ sml Standard ML of New Jersey v110.79 [built: Sat Oct 26 12:27:04 2019]
可以在提示符codice_1后键入代码。例如计算codice_2: - 1 + 2 * 3; val it = 7 : int 顶层推论这个表达式的类型为codice_3并给出结果codice_4。如果输入不完全则打印第二提示符codice_5，这时经常可以用codice_6终结输入。codice_7是给未指定变量的表达式的标准变量。输入control-C可返回解释器顶层，输入control-D可退出解释器。
下面是hello, world!的程序代码在SML/NJ解释器下执行的结果：
- val _ = print "Hello, world!\n"; Hello, world!
和使用MLton编译器进行编译执行的例子：
$ echo 'print "Hello, world!\n";' > hello-world.sml $ mlton hello-world.sml $ ./hello-world Hello, world! 不同于纯函数式编程语言，ML是兼具一些指令式特征的函数式编程语言。ML的特征包括：传值调用的求值策略，头等函数，带有垃圾收集的自动内存管理，参数多态，静态类型，类型推论，，模式匹配和异常处理。不同于Haskell，ML与大多数编程语言一样使用及早求值。
用ML书写的程序构成自要被求值的，而非语句或命令，尽管一些表达式返回一个平凡的codice_8值并且只为其副作用而求值。以下章节介绍采用Standard ML的语法和语义。
就像所有的函数式语言一样，ML的关键特征是函数，它被用于进行抽象。例如阶乘函数用纯ML可表达为： fun fac 0 = 1 这里将阶乘描述为递归函数，具有一个单一的终止基础情况。它类似于在数学教科书见到的阶乘描述。多数ML代码在设施和语法上类似于数学。
凭借类型推论编译器能推导出，codice_9接受整数codice_10作为实际参数，则形式参数codice_11也是整数类型codice_3，而codice_13的结果是整数codice_14，则函数codice_9的结果也是整数类型。函数codice_9接受一个整数的形式参数并返回一个整数结果，它作为一个整体从而有着“从整数到整数的函数”类型codice_17。函数及其形式参数的"类型"还可以用类型标注（annotation）来描述，使用codice_18表示法，它可以被读作表达式codice_19有类型codice_20，它是可选也可忽略的。使用类型标注，这个例子可重写为如下： fun fac 0 = 1 这个函数还依赖于模式匹配，这是ML语言的重要部份。注意函数形式参数不必须在圆括号内但要用空格分隔。当一个函数的实际参数是codice_10，它将返回整数codice_14。对于所有其他情况，尝试第二行。这是一个递归，并且再次执行这个函数直到达到基础情况。它可以使用codice_23表达式重写为： fun fac n = case n  这里codice_23介入了模式和对应表达式的序列。它还可以重写为将标识符绑定到lambda函数： val rec fac = 这里的关键字codice_25介入了标识符到值的绑定，codice_26介入了匿名函数的定义，它可以用在codice_27的位置上，但使用codice_28算符而非codice_5。绑定到递归的匿名函数需要使用codice_30关键字来指示。
通过将主要工作写入尾递归风格的内部迭代函数，借助于语言编译或解释系统进行的尾调用优化，这个函数可以得以增进性能，它的调用栈不需要随函数调用数目而成比例的增长。对这个函数可以采用向内部函数增加额外的“累加器”形式参数codice_31来实现： fun fact n = let codice_32表达式的值是在codice_33和codice_34之间表达式的值。这个递归函数的实现不保证能够终止，因为负数实际参数会导致递归调用的无穷降链条件。更健壮的实现会在递归前检查实际参数为非负数，并在有问题的情况，即codice_11是负数的时候，启用异常处理： fun fact n = let 有一些基本类型可以当作是“内建”的，因为它们是在Standard ML标准基本库中预先定义的，并且语言为它们提供表示法，比如codice_36是整数，而codice_37是字符串。一些最常用的基本类型是：
包括上述基本类型的各种类型可以用多种方式组合。一种方式是元组，它是值的有序集合，比如表达式codice_64的类型是codice_65，而codice_66的类型是codice_67。可以使用codice_68这样的语法来提取元组的指定次序的成员。
有0元组codice_69，它的类型指示为codice_8。但是没有1元组，或者说在例子codice_71和codice_14之间没有区别，都有类型codice_3。元组可以嵌套，codice_74不同于codice_75和codice_76二者。前者的类型是codice_77，其他两个的类型分别是codice_78和codice_79。
组合值的另一种方式是记录。记录很像元组，除了它的成员是有名字的而非有次序的，例如codice_80有类型codice_81，这同于类型codice_82。可以使用codice_83这样的语法来选取记录的指定名字的字段。
Standard ML中的函数只接受一个值作为参数，而不是参数的一个列表，可以使用上述元组模式匹配来实际上传递多个参数。函数还可以返回一个元组。例如：
fun sum (a, b) = a + b fun average pair = sum pair div 2
infix averaged_with fun a averaged_with b = average (a, b) val c = 3 averaged_with 7
fun int_pair (n : int) = (n, n)
这里第一段创建了两个类型是codice_84的函数codice_85和codice_86。第二段创建中缀算子codice_87，接着定义它为类型codice_84的函数。最后的codice_89函数的类型是codice_90。
下列函数是多态类型的一个例子：
fun pair x = (x, x)
编译器无法推论出的codice_91的特殊化了的类型，它可以是codice_90、codice_93甚至是codice_94。在Standard ML中，它可以简单指定为多态类型codice_95，这里的codice_96（读作“alpha”）是一个类型变量，指示任何可能的类型。在上述定义下，codice_97和codice_98都是有良好定义的，分别产生codice_99和codice_100。
SML标准基本库包括了重载标识符：codice_101、codice_1、codice_103、codice_104、codice_105、codice_106、codice_107、codice_108、codice_59、codice_57、codice_60、codice_58。标准基本库提供了多态函数：codice_113、codice_114、codice_115、codice_116、codice_117。中缀运算符可以有从缺省最低codice_10到最高codice_119的任何运算符优先级。标准基本库提供了如下内建中缀规定：
infix 7 * / div mod infix 6 + - ^ infixr 5 :: @ infix 4 = <> > >= < <= infix 3 := o infix 0 before 算符codice_5和codice_56分别被定义为多态的等式和不等式。codice_5它确定两个值是否相等，有着类型codice_123。这意味着它的两个运算数必须有相同的类型，这个类型必须是等式类型（codice_124）。上述基本类型中除了codice_41之外，codice_3、codice_41、codice_45、codice_48和codice_51都是等式类型。
例如：codice_131、codice_132、codice_133和codice_134，都是有效的表达式并求值为codice_52；而codice_136是有效表达式并求值为codice_53，codice_138是无效表达式而被编译器拒绝。这是因为IEEE浮点数等式打破了ML中对等式的一些要求。特别是codice_139不等于自身，所以关系不是自反的。
元组和记录类型是等式类型，当时且仅当它的每个成员类型是等式类型；例如codice_140、codice_141和codice_8是等式类型，而codice_143和codice_144不是。函数类型永远不是等式类型，因为一般情况下不可能确定两个函数是否等价。
类型声明或同义词（synonym）使用codice_145关键字来定义。下面是给在平面中的点的类型声明，计算两点间距离，和通过海伦公式计算给定角点的三角形的面积的函数。
type loc = real * real
fun heron (a: loc, b: loc, c: loc) = let Standard ML提供了对（ADT）的强力支持。一个ML数据类型可以被当作是元组的不交并（之和）。数据类型使用codice_146关键字来定义，比如：
datatype int_or_string
这个数据类型声明建立一个全新的数据类型codice_147，还有一起的新构造子（一种特殊函数或值）codice_148、codice_149和codice_150；每个这种类型的值都是要么codice_148具有一个整数，要么codice_149具有一个字符串，要么codice_150。写为如下这样：
val i = INT 3 val s = STRING "qq" val n = NEITHER val INT j = i
这里最后的一个声明通过模式匹配，将变量codice_154绑定到变量codice_155所绑定的整数codice_39。codice_157是绑定的一般形式，它是良好定义的，当且仅当模式和表达式有相同的类型。
数据类型可以是多态的：
datatype 'a pair
这个数据类型声明建立一个新的类型codice_158家族，比如codice_159，codice_160等等。
数据类型可以是递归的：
datatype int_list
这个数据类型声明建立一个新类型codice_161，这个类型的每个值是要么codice_162（空列表），要么是一个整数和另一个codice_161的接合。
通过codice_146创建的类型是等式类型，如果它的所有变体，要么是没有参数的空构造子，要么是有等式类型参数的构造子，并且在多态类型情况下所有类型参数也都是等式类型。递归类型在有可能情况下是等式类型，否则就不是。
基础库提供的复杂数据类型之一是列表codice_165。它是一个递归的、多态的数据类型，可以等价的定义为：
datatype 'a list
这里的codice_166是中缀算符，例如codice_167是三个整数的列表。列表是ML程序中最常用的数据类型之一，语言还为生成列表提供了特殊表示法codice_168。
codice_169当然不是等式类型。但是没有codice_170不能是等式类型的理由，所以它就是等式类型。注意类型变量不同就是不同的列表类型，比如codice_171是无效的，因为两个表达式有不同的类型，即使它们有相同的值。但是codice_172和codice_173都是有效的。
基本库codice_174函数“反转”一个列表中的元素。它的类型是codice_175，就是说它可以接受其元素有任何类型的列表，并返回相同类型的列表。更准确的说，它返回其元素相较于给定列表是反转次序的一个新列表，比如将codice_176映射成codice_177。中缀算符codice_178表示两个列表的串接。
codice_174和codice_178一般被实现为基本库函数codice_181的简单应用：
fun revAppend ([], l) = l
fun rev l = revAppend(l, [])
fun l1 @ l2 = revAppend(rev l1, l2) Standard ML的数据类型可以轻易的定义和用于编程，在很大程度上是由它的模式匹配，还有多数Standard ML实现的模式穷尽性检查和模式冗余检查。
模式匹配可以在语法上嵌入到变量绑定之中，比如：
val ((m: int, n: int), (r: real, s: real)) = ((2, 3), (2.0, 3.0))
val url : hyperlink = val {protocol=port, address=addr, title=name} = url
val x as (fst, snd) = (2, true)
第一个codice_25绑定了四个变量codice_183、codice_11、codice_185和codice_186；第二个codice_25绑定了一个变量codice_188；第三个codice_25绑定了三个变量codice_190、codice_191和codice_192，第四个叫分层模式，绑定了三个变量codice_193、codice_194和codice_195。
模式匹配可以在语法上嵌入到函数定义中，比如：
datatype shape
fun area (Circle (_, r)) = 3.14 * r * r 次序在模式匹配中是紧要的：模式按文本次序来依次进行匹配。在特定计算中，使用下划线codice_196，来省略不需要它的值的子成员，这也叫做通配符（wildcard）模式。所谓的“子句形式”风格的函数定义，这里的模式紧随在函数名字之后出现，只是如下形式的一种语法糖：
fun area shape = case shape 模式穷尽性检查将确保数据类型的每个情况都已经顾及到。 如果有遗漏，则产生警告。 如果模式存在冗余，也会导致一个编译时间警告。
函数可以接受函数作为实际参数，比如：
fun applyToBoth f x y = (f x, f y) 函数可以产生函数作为返回值，比如：
fun constantFn k = (fn anything => k) 函数可以同时接受和产生函数，比如：
fun compose (f, g) = (fn x => f (g x)) 基本库的函数codice_197，是在Standard ML中最常用的Curry化高阶函数，它在概念上可定义为：
fun map' _ [] = []
在基本库中将函数复合定义为多态中缀算符codice_198，codice_199和codice_200高阶函数有较高效率的实现。
异常可以使用codice_201关键字发起，并通过模式匹配codice_202构造来处理：
exception Undefined;
fun max [x] = x
fun main xs = let 这里的codice_203是字符串串接算符。可以利用异常系统来实现非局部退出，例如这个函数所采用技术：
exception Zero;
fun listProd ns = let 异常codice_204在codice_10情况下发起，控制从函数codice_206中一起出离。
初始化基础库还以引用的形式提供了可变的存储。引用codice_207可以在某种意义上被认为是如下这样定义的： datatype 'a ref = ref of 'a 还定义了内建的codice_114函数来修改引用的内容，和codice_113函数来检索引用的内容。阶乘函数可以使用引用定义为指令式风格：
fun factImperative n = let
这里使用圆括号对以codice_6分隔的表达式进行了顺序复合。
可变类型codice_211是等式类型，即使它的成员类型不是。两个引用被称为是相等的，如果它们标识相同的“codice_207单元”，就是说相同的对codice_207构造子调用生成的同一个指针。因此codice_214和codice_215都是有效的，并且都求值为codice_53，因为即使两个引用碰巧指向了相同的值，引用自身是分立的，每个都可以独立于其他而改变。
模块是ML用于构造大型项目和库的系统。
一个模块构成自一个签名（signature）文件和一个或多个结构文件。签名文件指定要实现的API（就像C语言头文件或Java接口文件）。结构实现这个签名（就像C语言源文件或Java类文件）。解释器通过codice_217命令导入它们。ML的标准库被实现为这种方式的模块。
例如，下列定义一个算术签名：
signature ARITH = sig end
和这个签名使用有理数的实现：
structure Rational : ARITH = struct end
下面是这个结构的简单用例：
infix == local open Rational in val c = let  end structure R = Rational R.fromReal(3.245)
Standard ML只允许通过签名函数同实现进行交互，例如不可以直接通过这个代码中的codice_218来建立数据对象。结构块对外部隐藏所有实现细节。这里的codice_219叫做透明归属（ascription），可以通过所绑定的变量见到此结构的数据内容，与之相对的是codice_220，它叫做不透明归属，此结构的数据内容对外完全不可见。比如上面用例有结果：codice_221，如果改为不透明归属则有结果：codice_222。
要用有理数进行实际上的数值计算，需要处理分数形式中分母快速增大导致溢出整数类型大小范围等问题。
函子接受指定签名的一个结构作为参数，并返回一个结构作为结果，下面示例的函子能在codice_223签名的结构上计算移动平均：
signature MOVINGLIST =  sig end functor MovingList (S: ARITH) : MOVINGLIST =  struct end
和这个函子的简单用例：
structure R = Rational structure MLR = MovingList (Rational) val d = MLR.fromList [R.fromIntPair (4, 5), R.fromIntPair (2, 3)] val d = MLR.expand (d, R.fromIntPair (5, 6)) val d = MLR.move (d, R.fromIntPair (7, 8)) val d = MLR.shrink d val d = MLR.trunc d
这个用例承上节示例，codice_224结构采用了透明归属，有结果如：codice_225。如果它改为不透明归属，则对应结果为：codice_226。
下列例子使用了Standard ML的语法和语义。
下面是求素数的试除法实现：
fun prime n = let
基本库codice_227和codice_228函数在不存在符合条件元素的时候会遍历整个列表， 这里采用了特殊化了的codice_229，用以在后续元素都不满足条件时立即结束运算。
下面是埃拉托斯特尼筛法实现：
fun prime n = let
这里基于列表的筛法实现符合埃拉托斯特尼的原初算法。筛法还有基于数组的直观实现。 下面是其解释器下命令行运行实例：
- fun printIntList (l: int list) = = print ((String.concatWith " " (map Int.toString l)) ^ "\n"); val printIntList = fn : int list -> unit - val _ = printIntList (prime 100); 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 正规数是形如formula_1的整数，对于非负整数formula_2、formula_3和formula_4，它是可以整除formula_5的数。计算升序的正规数的算法经由戴克斯特拉得以流行，理查德·汉明最初提出了这个问题，故而这个问题被称为“汉明问题”，这个数列也因而被称为汉明数。Dijkstra计算这些数的想法如下： 示例汉明数程序代码，一般用来展示，确使计算只在需要时进行的纯函数式编程方式。
fun Hamming_number n = let
产生指定范围内的汉明数需要多轮运算，后面每轮中的三个列表元素乘积运算中都可能产生超出这个范围的结果，它们不需要出现在后续的运算之中。 基本库codice_236函数与它所映射的函数，通过基于codice_237结构的codice_238和codice_239构造子的协定，可以将所映射函数认为不符合条件的元素或者结果排除掉，它会遍历整个列表。 由于这个算法采用升序列表，故而这里将它改写为codice_240函数，用来在特定条件不满足条件就立即结束。下面是汉明数程序在解释器下命令行运行实例：
- fun printIntList (l: int list) = = print ((String.concatWith " " (map Int.toString l)) ^ "\n"); val printIntList = fn : int list -> unit - val _ = printIntList (Hamming_number 400); 1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54 60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180 192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400 下面是（CPS）的高阶函数foldr和map的实现，和达成一个整数列表的合计函数的简单用例：
fun foldr' f b l = let
fun map' f l =
fun sum l = 对于输入codice_241，codice_85函数等价于函数复合codice_243，它应用于codice_10上得到codice_245。
SML/NJ支持头等对象的续体。头等续体对一门语言而言是能完全控制指令执行次序的能力。它们可以用来跳转到产生对当前函数调用的那个函数，或者跳转到此前已经退出了的函数。头等续体保存了程序执行状态，它不保存程序数据，只保存执行上下文。
排序算法关注计算复杂度，特别是时间复杂度，基本库函数的实现细节也要考虑在内，比如串接函数codice_178，它被实现为codice_247，除非必需的情况避免使用遍历整个列表的codice_174和codice_249函数。 通过比较于这些排序算法的周知过程式编程语言比如C语言的实现，可以体察到ML在控制流程和列表数据结构上的相关限制，和与之相适应的采用尾递归的特色函数式编程风格。
下面是简单的插入排序算法的尾递归和等价的普通递归实现：
插入排序算法是稳定的，它在输入列表趋于正序的时候性能最佳，在输入列表趋于反序的时候性能最差，因此在算法实现中，需要codice_250函数所插入列表保持为反序，在插入都完成后经codice_174函数再反转回正序。在预期输入数据趋于随机化或者预知它经过了反转的情况下，可以采用保持要插入列表为正序的变体插入排序算法实现，它在输入列表趋于反序的时候性能最佳，在输入列表趋于正序的时候性能最差，它比自适应实现少作一次全列表反转。 采用codice_252函数可以相应的保持要插入列表为正序，由于codice_253，它等同于对反转过的列表应用变体插入排序。
希尔排序算法是对插入排序的改进，保持了，放弃了稳定性。 下面是希尔排序的实现：
fun shellSort l = let
这里采用的间隔序列是OEIS ，即formula_6，它是徳田尚之在1992年提出的。这个序列用递推公式表示为：codice_254，这里的codice_255而codice_256。假定一个列表的长度codice_186位于序列两个元素之间，即codice_258，如果codice_259，这里的codice_260，则选择初始间隔为codice_232，否则为codice_232。在这个阈值下，对于不同长度codice_186的列表和对应的初始间隔codice_232，每个列表的这些初始子列表的平均长度codice_265，约在codice_266范围之内。间隔序列还可以采用OEIS ，它是Marcin Ciura在2001年通过实验得到的。
下面是快速排序算法的自顶向下实现：
fun quickSort [] = []
基本库codice_267函数实现对快速排序而言有不必要的反转， 这里采用了它的简化改写。在ML中快速排序应采用自底向上实现：
fun quickSort l = let  下面是归并排序算法的自底向上法实现：
fun mergeSort l = let
考虑输入列表codice_268，这里在codice_193和codice_193之间的codice_271个codice_272，具有相同的值并且需要保持其下标表示的次序，这里的codice_273并且codice_274，并且在这个区段前后的元素总数都能被codice_39整除，则它被分解成子列表的列表codice_276，这里有codice_277；假定这codice_278个含有codice_272的子列表两两归并，在归并正序子列表的归并条件codice_280下，能得到codice_281；继续推演下去，在归并反序子列表的归并条件codice_282下，能得到codice_283。可以看出这种归并操作能够保证排序算法的稳定性，即具有相同值的元素之间的相对次序保持不变。
分解初始的子列表采用了插入排序，还可进一步增加其大小。归并排序也有自顶向下实现。
下面是堆排序的基于数组的实现：
fun heapSort l = let
在数组实现中，codice_284函数融合了插入和筛选功能，它首先在暂时位于堆顶的要插入的元素，和从堆顶节点左右子堆的两个堆顶元素中筛选出的那个元素，二者中选择出哪个适合作堆顶元素；如果要插入元素适合，则以它为新堆顶元素而结束整个过程，否则以筛选出元素为新堆顶元素，并自顶向下逐级处理提供了新堆顶元素的子堆，将要插入元素暂时作为其堆顶元素并对它继续进行codice_284；codice_284只要到达了某个堆底，就插入要插入的元素而结束整个过程。
在提取堆顶元素生成结果列表时，先提取走堆顶元素的内容，再摘掉最后的堆底元素将它的内容暂时放置在堆顶，这时堆的大小也相应的减一，随后的codice_284函数，筛选出新的堆顶元素，并把原最后堆底元素插入回堆中。
在codice_288函数建造堆的时候，首先自列表中间将元素分为前后两组，后组中的元素被视为只有一个元素的堆，然后从后往前处理前组中的元素，这时它的左右子节点已经是已有的堆或者为空，在其上进行codice_284，从而合成一个新堆。建造堆也可以采用codice_290函数来实现，它自第二个元素开始从前往后逐个处理列表元素，其前面是已有的堆，将这个新元素自堆底向上插入到这个堆中。
堆排序算法也可以使用二叉树数据结构来实现二叉堆：
fun heapSort l = let
二叉树实现不能直接访问堆底元素，从而不适宜通过摘掉它使堆的大小减一。这里的codice_250函数，在原堆顶元素和要插入元素中选择适合者作为新的堆顶元素，将落选的另一个元素作为新的要插入元素，插入到利于保持这个堆平衡的那个子树之中。这里的codice_292函数只筛选不插入，它将堆的大小减一。
这里的codice_250和codice_292函数也可以直接转写为等价的尾递归形式，与列表情况不同，只要树结构能保持良好的平衡，采用尾递归形式就没有太大的必要性。 在二叉树实现下，也可以采用codice_284函数来初始建造堆，而不需要在节点中保存关于树状态的统计信息。
下面是针对非负整数的基数排序算法的实现：
fun radixSort l = let
这里采用的基数是codice_296的codice_39次幂codice_298，代码所使用的列表元组大小与基数大小成正比，运算量与列表中元素的总数与最大数的位数的乘积成正比。
编写排序算法进行测试除了使用简单的数列， 测试用列表还可以使用线性同余伪随机数函数来生成：
fun randList (n, seed) = let
定义和处理一个小型表达式语言是相对容易的： exception Err; datatype ty datatype exp fun typeOf (True) = BoolTy
fun eval (True) = True fun exp_repr e = let (* 忽略TypeOf的返回值，它在类型错误时发起Err *)  fun evalPrint e = (ignore (typeOf e); print (exp_repr (eval e))); 将这段代码录入文件比如codice_299，并在命令行下执行codice_300，可以用如下在正确类型的和不正确类型上运行的例子，测试这个新语言：
- val e1 = Add (Int 1, Int 2); (* 正确的类型 *) val e1 = Add (Int 1,Int 2) : exp - val _ = evalPrint e1; 3 - val e2 = Add (Int 1, True); (* 不正确的类型 *) val e2 = Add (Int 1,True) : exp - val _ = evalPrint e2;
uncaught exception Err