ML语言

MLMeta Language:元语言)是一个通用的函數式編程语言。ML是静态作用域的。ML知名于使用了多态Hindley–Milner类型系统,它自动的指定多数表达式英语Expression (computer science)类型,不要求显式的类型标注,而且能够确保类型安全,已经正式证明了有良好类型的ML程序不会导致运行时间类型错误[1]

ML
编程范型多范型函数式指令式
設計者Robin Milner & 爱丁堡大学其他人
发行时间1973年,​48年前​(1973
穩定版本
Standard ML '97
(1997年,​24年前​(1997
型態系統类型推论静态类型强类型
衍生副語言
Standard ML, OCaml, F#
啟發語言
ISWIM
影響語言
ClojureCoqCyclone英语Cyclone (programming language)C++ElmF#F*HaskellIdrisMirandaNemerleOCamlOpa英语Opa (programming language)ErlangRustScalaStandard MLUr

ML提供了对函数实际参数的模式匹配垃圾回收指令式编程传值调用柯里化。它被大量的用于编程语言研究之中,并且是全面规定了的和使用形式语义验证了的少数语言之一。它的类型和模式匹配使得它非常适合并且经常用于在其他形式语言上进行操作,比如在编译器构造自动化定理证明形式验证中。

概述编辑

ML是由爱丁堡大学Robin Milner及他人在二十世纪七十年代早期开发的[2],它的语法是从ISWIM得到的灵感。ML是为了帮助在LCF英语Logic for Computable Functions定理证明器中寻找证明策略而构想出来的,LCF的语言是“pplambda”,联合了一阶逻辑演算和有类型的多态λ演算,拥有ML作为元语言

ML特性包括:传值调用的求值策略头等函数,带有垃圾收集的自动内存管理参数多态静态类型类型推论代数数据类型英语Algebraic data type模式匹配异常处理

不同于Haskell,ML与大多数编程语言一样使用及早求值,也就是说所有的子表达式总是被求值,尽管可以通过使用闭包来完成惰性求值。因此可以像Haskell那样建立和使用无限串流,但是它们的表达是间接的。

今天在ML家族中有好几种语言:两种主要的方言是Standard MLOCaml,其他的包括F#,它是针对Microsoft .NET平台的开放研究项目。Standard ML在1984年就拥有了完全的模块系统[3]。ML的思想影响了众多的语言,例如HaskellCyclone英语Cyclone (programming language)NemerleATS英语ATS (programming language)[4]Elm[5]

ML的实力大多被用于语言设计和操作(编译器、分析器、定理证明器),但是它作为通用语言也被用于生物信息和财务系统等领域。

语言特征编辑

ML特别是Standard ML是具有一些不纯粹特征的函数式语言。用ML书写的程序构成自要被求值的表达式英语Expression (computer science),而非语句或命令,尽管一些表达式返回一个平凡的unit值并且只为其副作用而求值。

函数编辑

就像所有的函数式语言一样,ML的关键特征是函数,它被用于进行抽象。例如阶乘函数用纯ML可表达为:

fun fac 0 = 1
  | fac n = n * fac (n - 1)

这里将阶乘描述为递归函数,具有一个单一的终止基础情况。它类似于在数学教科书见到的阶乘描述。多数ML代码在设施和语法上类似于数学。

凭借类型推论编译器能推导出,fac接受整数0作为实际参数,则形式参数n也是整数类型int,而fac 0的结果是整数1,则函数fac的结果也是整数类型。函数fac接受一个整数的形式参数并返回一个整数结果,它作为一个整体从而有着“从整数到整数的函数”类型int -> int。函数及其形式参数的"类型"还可以用类型标注(annotation)来描述,它是可选也可忽略的。它使用E : t表示法,可以被读作表达式E有类型t。使用类型标注,这个例子可重写为如下:

fun fac 0 = 1
  | fac (n : int) : int = n * fac (n - 1)

这个函数还依赖于模式匹配,这是ML语言的重要部份。注意函数形式参数不必须在圆括号内但要用空格分隔。当一个函数的实际参数是0,它将返回整数1。对于所有其他情况,尝试第二行。这是一个递归,并且再次执行这个函数直到达到基础情况。它可以使用case表达式重写为:

fun fac n = case n 
    of  0 => 1
     |  n => n * fac (n - 1)

这里case介入了模式和对应表达式的序列。它还可以重写为将标识符绑定到lambda函数

val rec fac =
    fn  0 => 1
     |  n => n * fac (n - 1)

这里的关键字val介入了标识符到值的绑定,fn介入了匿名函数的定义,它可以用在fun的位置上,但使用=>算符而非=。绑定到递归的匿名函数需要使用rec关键字来指示。

通过将主要工作写入尾递归风格的内部迭代函数,借助于语言编译或解释系统进行的尾调用优化,这个函数可以得以增进性能,它的调用栈不需要随函数调用数目而成比例的增长。对这个函数可以采用向内部函数增加额外的“累加器”形式参数acc来实现:

fun fact n = let
    fun fac (0, acc) = acc
      | fac (n, acc) = fac (n - 1, n * acc)
    in
        fac (n, 1)
    end

let表达式的值是在inend之间表达式的值。这个递归函数的实现不保证能够终止,因为负数实际参数会导致递归调用的无限降链条件。更健壮的实现会在递归前检查实际参数为非负数,并在有问题的情况,即n是负数的时候,启用异常处理

fun fact n = let
    fun fac (0, acc) = acc
      | fac (n, acc) = fac (n - 1, n * acc)
    in
        if (n < 0) 
        then raise Fail "negative argument"
        else fac (n, 1)
    end

类型编辑

有一些基本类型可以当作是“内建”的,因为它们是在Standard ML Basis库中预先定义的,并且语言为它们提供文字英语Literal (computer programming)表示法,比如34是整数,而"34"是字符串。一些最常用的基本类型是:

  • int 整数,比如3~12。注意波浪号~表示负号。
  • real浮点数,比如4.2~6.4。Standard ML不隐含的提升整数为浮点数,因此表达式2 + 5.67 是无效的。
  • string字符串,比如"this is a string"""(空串)。
  • char字符,比如#"y"#"\n"(换行符)。
  • bool布尔值,它是要么true要么false。产生bool值的有比较算符=<>>>=<<=,逻辑函数not短路求值的中缀算符andalsoorelse

包括上述基本类型的各种类型可以用多种方式组合。一种方式是元组,它是值的有序集合,比如表达式(1, 2)的类型是int * int,而("foo", false)的类型是string * bool。可以使用#1 ("foo", false)这样的语法来提取元组的指定次序的成员。

有0元组(),它的类型指示为unit。但是没有1元组,或者说在例子(1)1之间没有区别,都有类型int。元组可以嵌套,(1, 2, 3)不同于((1, 2), 3)(1, (2, 3))二者。前者的类型是int * int * int,其他两个的类型分别是(int * int) * intint * (int * int)

组合值的另一种方式是记录。记录很像元组,除了它的成员是有名字的而非有次序的,例如{a = 5.0, b = "five"}有类型{a : real, b : string},这同于类型{b : string, a : real}。可以使用#a {a = 5.0, b = "five"}这样的语法来选取记录的指定名字的字段。

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)

这里第一段创建了两个类型是int * int -> int的函数sumaverage。第二段创建中缀算子averaged_with,接着定义它为类型int * int -> int的函数。最后的int_pair函数的类型是int -> int * int

下列函数是多态类型的一个例子:

fun pair x = (x, x)

编译器无法推论出的pair的特殊化了的类型,它可以是int -> int * intreal -> real * real甚至是(int * real -> string) -> (int * real -> string) * (int * real -> string)。在Standard ML中,它可以简单指定为多态类型'a -> 'a * 'a,这里的'a(读作“alpha”)是一个类型变量,指示任何可能的类型。在上述定义下,pair 3pair "x"都是有良好定义的,分别产生(3, 3)("x", "x")

算符=被定义为多态等式,它确定两个值是否相等,有着类型''a * ''a -> bool。这意味着它的两个运算数必须有相同的类型,这个类型必须是等式类型(eqtype)。上述基本类型中除了real之外,intrealstringcharbool都是等式类型。

例如:3 = 3"3" = "3"#"3" = #"3"true = true,都是有效的表达式并求值为true;而3 = 4是有效表达式并求值为false3.0 = 3.0是无效表达式而被编译器拒绝。这是因为IEEE浮点数等式打破了ML中对等式的一些要求。特别是nan不等于自身,所以关系不是自反的。

元组和记录类型是等式类型,当时且仅当它的每个成员类型是等式类型;例如int * string{b : bool, c : char}unit是等式类型,而int * real{x : real}不是。函数类型永远不是等式类型,因为一般情况下不可能确定两个函数是否等价。

数据类型编辑

Standard ML提供了对代数数据类型英语Algebraic data type(ADT)的强力支持。一个ML数据类型可以被当作是元组不交并英语Product type)。数据类型使用datatype关键字来定义,比如:

datatype int_or_string
  = INT of int
  | STRING of string
  | NEITHER

这个数据类型声明建立一个全新的数据类型int_or_string,还有一起的新构造子(一种特殊函数或值)INTSTRINGNEITHER;每个这种类型的值都是要么INT具有一个整数,要么STRING具有一个字符串,要么NEITHER。写为如下这样:

val i = INT 3
val s = STRING "qq"
val n = NEITHER
val INT j = i

这里最后的一个声明通过模式匹配,将变量j绑定到变量i所绑定的整数3val 模式 = 表达式是绑定的一般形式,它是良好定义的,当且仅当模式和表达式有相同的类型。

数据类型可以是多态的:

datatype 'a pair
  = PAIR of 'a * 'a

这个数据类型声明建立一个新的类型'a pair家族,比如int pairstring pair等等。

数据类型可以是递归的:

datatype int_list
  = EMPTY
  | INT_LIST of int * int_list

这个数据类型声明建立一个新类型int_list,这个类型的每个值是要么EMPTY(空列表),要么是一个整数和另一个int_list的接合。

通过datatype创建的类型是等式类型,如果它的所有变体,要么是没有参数的空构造子,要么是有等式类型参数的构造子,并且在多态类型情况下所有类型参数也都是等式类型。递归类型在有可能情况下是等式类型,否则就不是。

列表编辑

基础库提供的复杂数据类型之一是列表list。它是一个递归的、多态的数据类型,可以等价的定义为:

datatype 'a list
  = nil 
  | :: of 'a * 'a list

这里的::是中缀算符,例如3 :: 4 :: 5 :: nil是三个整数的列表。列表是ML程序中最常用的数据类型之一,语言还为生成列表提供了特殊表示法[3, 4, 5]

real list当然不是等式类型。但是没有int list不能是等式类型的理由,所以它就是等式类型。注意类型变量不同就是不同的列表类型,比如(nil : int list) = (nil : char list)是无效的,因为两个表达式有不同的类型,即使它们有相同的值。但是nil = nil(nil : int list) = nil都是有效的。

基本库rev函数“反转”一个列表中的元素。它的类型是'a list -> 'a list,就是说它可以接受其元素有任何类型的列表,并返回相同类型的列表。更准确的说,它返回其元素相较于给定列表是反转次序的一个新列表,比如将[ "a", "b", "c" ]映射成[ "c", "b", "a" ]。中缀算符@表示两个列表的串接。

rev@一般被实现为基本库函数revAppend的简单应用:

fun revAppend ([], l) = l
  | revAppend (x :: r, l) = revAppend(r, x :: l)

fun rev l = revAppend(l, [])

fun l1 @ l2 = revAppend(rev l1, l2)

类型声明编辑

类型声明或同义词(synonym)使用type关键字来定义。下面是给在平面中的点的类型声明,计算两点间距离,和通过海伦公式计算给定角点的三角形的面积的函数。

type loc = real * real

fun heron (a: loc, b: loc, c: loc) = let
    fun dist ((x0, y0), (x1, y1)) = let
        val dx = x1 - x0
        val dy = y1 - y0
        in
            Math.sqrt (dx * dx + dy * dy)
        end
    val ab = dist (a, b)
    val bc = dist (b, c)
    val ac = dist (a, c)
    val s = (ab + bc + ac) / 2.0
    in
        Math.sqrt (s * (s - ab) * (s - bc) * (s - ac))
    end

模式匹配编辑

Standard ML的数据类型可以轻易的定义和用于编程,在很大程度上是由它的模式匹配,还有多数Standard ML实现的模式穷尽性检查和模式冗余检查。

模式匹配可以在语法上嵌入到变量绑定之中,比如:

val ((m: int, n: int), (r: real, s: real)) = ((2, 3), (2.0, 3.0))

type hyperlink = {protocol: string, address: string, title: string}

val url : hyperlink =
    {title="The Standard ML Basis Library", protocol="https",
     address="//smlfamily.github.io/Basis/overview.html"}
val {protocol=port, address=addr, title=name} = url

val x as (fst, snd) = (2, true);

第一个val绑定了四个变量mnrs;第二个val绑定了一个变量url;第三个val绑定了三个变量portaddrname,第四个叫分层模式,绑定了三个变量xfstsnd

模式匹配可以在语法上嵌入到函数定义中,比如:

datatype shape
  = Circle of loc * real    (* 中心和弧度 *)
  | Square of loc * real    (* 左上角和边长,坐标轴对齐 *)
  | Triangle of loc * loc * loc     (* 角点 *)

fun area (Circle (_, r)) = 3.14 * r * r
  | area (Square (_, s)) = s * s
  | area (Triangle (a, b, c)) = heron (a, b, c)

次序在模式匹配中是紧要的:模式按文本次序来依次进行匹配。在特定计算中,使用下划线_,来省略不需要它的值的子成员,这也叫做通配符(wildcard)模式。所谓的“子句形式”风格的函数定义,这里的模式紧随在函数名字之后出现,只是如下形式的一种语法糖

fun area shape = case shape
    of  Circle (_, r) => 3.14 * r * r
     |  Square (_, s) => s * s
     |  Triangle (a, b, c) => heron (a, b, c)

模式穷尽性检查将确保数据类型的每个情况都已经顾及到。[a] 如果有遗漏,则产生警告。[b] 如果模式存在冗余,也会导致一个编译时间警告。[c]

高阶函数编辑

函数可以接受函数作为实际参数,比如:

fun applyToBoth f x y = (f x, f y)

函数可以产生函数作为返回值,比如:

fun constantFn k = (fn anything => k)

函数可以同时接受和产生函数,比如复合函数英语Function composition (computer science)

fun compose (f, g) = (fn x => f (g x))

基本库的函数List.map,是在Standard ML中最常用的Curry化高阶函数,它在概念上可定义为:

fun map _ [] = []
  | map f (x :: xs) = f x :: map f xs

在基本库中将函数复合定义为中缀算符(f o g)mapfold高阶函数有较高效率的实现。[d]

异常编辑

异常可以使用raise关键字发起,并通过模式匹配handle构造来处理:

exception Undefined;

fun max [x] = x
  | max (x :: xs) = let
    val m = max xs
    in
        if x > m then x else m 
    end
  | max [] =
    raise Undefined

fun main xs = let
    val msg = (Int.toString (max xs))
    handle Undefined => "empty list...there is no max!"
    in
        print (msg ^ "\n")
    end

这里的^是字符串串接算符。可以利用异常系统来实现非局部退出,例如这个函数所采用技术:

exception Zero;

fun listProd ns = let
    fun p [] = 1
      | p (0 :: _) = raise Zero
      | p (h :: t) = h * p t
    in
        (p ns)
        handle Zero => 0
    end

异常Zero0情况下发起,控制从函数p中一起出离。

引用编辑

初始化基础库还以引用的形式提供了可变的存储。引用ref可以在某种意义上被认为是如下这样定义的:

datatype 'a ref = ref of 'a

还定义了内建的:=函数来修改引用的内容,和!函数来检索引用的内容。阶乘函数可以使用引用定义为指令式风格:

fun factImper n = let
    val i = ref n and acc = ref 1
    in
        while !i > 0 do
           (acc := !acc * !i;
            i := !i - 1);
        !acc
    end

这里使用圆括号对以;分隔的表达式进行了顺序复合。

可变类型'a ref是等式类型,即使它的成员类型不是。两个引用被称为是相等的,如果它们标识相同的“ref单元”,就是说相同的对ref构造子调用生成的同一个指针。因此(ref 1) = (ref 1)(ref 1.0) = (ref 1.0)都是有效的,并且都求值为false,因为即使两个引用碰巧指向了相同的值,引用自身是分立的,每个都可以独立于其他而改变。

模块编辑

模块是ML用于构造大型项目和库的系统。一个模块构成自一个签名(signature)文件和一个或多个结构文件。签名文件指定要实现的API(就像C语言头文件或Java接口文件)。结构实现这个签名(就像C语言源文件或Java文件)。解释器通过use命令导入它们。ML的标准库被实现为这种方式的模块。

例如,下列定义一个算术签名和它的使用有理数的实现:

signature ARITH =
sig
    type t;
    val zero : t;
    val one : t;
    val fromInt: int -> t;  
    val fromIntPair : int * int -> t;
    val fromReal : real -> t;
    val succ : t -> t;
    val pred : t -> t;
    val ~ : t -> t;
    val + : t * t -> t;
    val - : t * t -> t;
    val * : t * t -> t;
    val / : t * t -> t;
    val == : t * t -> bool;
    val <> : t * t -> bool;
    val > : t * t -> bool;
    val >= : t * t -> bool;
    val < : t * t -> bool;
    val <= : t * t -> bool;
end;

structure Rational : ARITH =
struct
    datatype t = Rat of int * int;
    val zero = Rat (0, 1);
    val one = Rat (1, 1);
    fun fromInt n = Rat (n, 1);
    fun ineg (a, b) = (~a, b);
    fun fromIntPair (num, den) = let
        fun reduced_fraction (numerator, denominator) = let
            fun gcd (n, 0) = n
              | gcd (n, d) = gcd (d, n mod d)
            val d = gcd (numerator, denominator)
            in 
                if d > 1 then (numerator div d, denominator div d) 
                else (numerator, denominator)
            end
        in  
            if num < 0 andalso den < 0
            then Rat (reduced_fraction (~num, ~den))
            else if num < 0 
            then Rat (ineg (reduced_fraction (~num, den)))
            else if den < 0
            then Rat (ineg (reduced_fraction (num, ~den)))
            else Rat (reduced_fraction (num, den))
        end
    val SOME maxInt = Int.maxInt;
    val minPos = 1.0 / (real maxInt);
    fun fromReal r = let
        fun convergent (i, f, h_1, k_1, h_2, k_2) = 
            if i <> 0 andalso ((h_1 > (maxInt - h_2) div i)
                orelse (k_1 > (maxInt - k_2) div i))
            then (h_1, k_1)
            else if f < minPos 
            then (i * h_1 + h_2, i * k_1 + k_2)
            else convergent (trunc (1.0 / f), Real.realMod (1.0 / f),
                             i * h_1 + h_2, i * k_1 + k_2, h_1, k_1)
        in 
            if r < 0.0
            then Rat (ineg (convergent (trunc (~ r), 
                      Real.realMod (~ r), 1, 0, 0, 1))) 
            else Rat (convergent (trunc r, Real.realMod r, 1, 0, 0, 1))
        end
    fun succ (Rat (a, b)) = fromIntPair (a + b, b);
    fun pred (Rat (a, b)) = fromIntPair (a - b, b);
    fun add (Rat (a, b), Rat (c, d)) = 
        if b = d then fromIntPair(a + c, b) 
        else fromIntPair (a * d + c * b, b * d);
    fun sub (Rat (a, b), Rat (c, d)) = 
        if b = d then fromIntPair(a - c, b) 
        else fromIntPair (a * d - c * b, b * d);
    fun mul (Rat (a, b), Rat (c, d)) = fromIntPair (a * c, b * d);
    fun div_ (Rat (a, b), Rat (c, d)) = fromIntPair (a * d, b * c);
    fun gt (Rat (a, b), Rat (c, d)) =
        if b = d then (a > c) else (a * d) > (b * c);
    fun lt (Rat (a, b), Rat (c, d)) =
        if b = d then (a < c) else (a * d) < (b * c);
    fun neg (Rat (a, b)) = Rat (~a, b);
    fun eq (Rat (a, b), Rat (c, d)) = ((b = d) andalso (a = c));
    fun ~ a = neg a;
    fun a + b = add (a, b);
    fun a - b = sub (a, b);
    fun a * b = mul (a, b);
    fun a / b = div_ (a, b);
    fun op == (a, b) = eq (a, b);
    fun a <> b = not (eq (a, b));
    fun a > b = gt (a, b);
    fun a >= b = (gt (a, b) orelse eq (a, b)); 
    fun a < b = lt (a, b);
    fun a <= b = (lt (a, b) orelse eq (a, b));
end;

和这个结构的简单用例:

infix ==;
local open Rational
in  
    val c = let 
    val a = fromIntPair(2, 3)
    val b = fromIntPair(4, 6)
    in
        a + b
    end
end;
structure R = Rational;
R.fromReal(3.245);

Standard ML只允许通过签名函数同实现进行交互,例如不可以直接通过这个代码中的Rat来建立数据对象。结构块对外部隐藏所有实现细节。这里的:叫做透明归属(ascription),可以通过所绑定的变量见到此结构的数据内容,与之相对的是:>,它叫做不透明归属,此结构的数据内容对外完全不可见。

要用有理数进行实际上的数值计算,需要处理分数形式中分母快速增大导致溢出整数类型大小范围等问题。[e]

函子编辑

函子接受指定签名的一个结构作为参数,并返回一个结构作为结果,下面示例的函子能在ARITH签名的结构上计算移动平均

functor MovingList (S : ARITH) = 
struct
    type t = S.t list * int * S.t; 
    fun size (lx : t) = #2 lx;
    fun average (lx : t) = #3 lx;
    fun fromList (l : S.t list) = let
        val n = length l;
        val m = foldl S.+ S.zero l;
        in
            if (null l) then raise Empty
            else (l, n, S./ (m, (S.fromInt n))) 
        end
    fun move ((l, n, m) : t, new : S.t) = let
        val old = List.nth (l, n - 1);  
        local open S in val xm = m + (new - old) / (fromInt n) end;     
        in
            (new :: l, n, xm)
        end     
    fun expand ((l, n, m) : t, new : S.t) = let
        val xn = n + 1; 
        local open S in val xm = m + (new - m) / (fromInt xn) end;
        in
            (new :: l, xn, xm)
        end
    fun shrink ((l, n, m) : t) = let
        val old = List.nth (l, n - 1); 
        val xn = if (n > 2) then n - 1 else 1; 
        local open S in val xm = m + (m - old) / (fromInt xn) end;
        in
           (l, xn, xm)
        end
    fun trunc ((l, n, m) : t) = (List.take (l, n), n, m)
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;

例子编辑

下列例子使用了Standard ML的语法。其他ML方言比如OCamlF#在细微方面有所不同。SML的代码片段很容易通过将其录入到“顶层”来研习,它也叫作读取﹣求值﹣输出循环或REPL。这是打印结果或定义的表达式的推论类型的交互式会话。很多SML实现提供交互式REPL,包括SML/NJ英语Standard ML of New Jersey

$ sml
Standard ML of New Jersey v110.79 [built: Sat Oct 26 12:27:04 2019]
-

可以在提示符-后键入代码。例如计算1 + 2 * 3:

- 1 + 2 * 3;
val it = 7 : int

顶层推论这个表达式的类型为int并给出结果7。如果输入不完全则打印第二提示符=,这时经常可以用;终结输入。it是给未指定变量的表达式的标准变量。输入control-C可返回解释器顶层,输入control-D可退出解释器。

Hello world编辑

下面是hello, world!的程序代码在SML/NJ解释器下执行的结果:

- val _ = print "Hello, world!\n";
Hello, world!

和使用MLton英语MLton编译器进行编译执行的例子:

$ echo 'print "Hello, world!\n";' > hello-world.sml
$ mlton hello-world.sml
$ ./hello-world
Hello, world!

素数编辑

下面是求素数试除法实现:

fun prime n = let
    fun findDivisor ([], _) = NONE 
      | findDivisor (x :: xs, i) = 
        if (i mod x) = 0 then SOME x
        else if (x * x) > i then NONE 
        else findDivisor (xs, i)
    fun checkAppend (l, i) = let
        val is_prime = case findDivisor (l, i)
            of  SOME _ => false 
             |  NONE => true
        in
            if is_prime then l @ [i] else l
        end
    fun iterator (l, i) =
        if i > n then l
        else iterator (checkAppend (l, i), i + 2)
    in 
        if n < 2 then []
        else iterator ([2], 3)
    end

埃拉托斯特尼筛法实现:

fun prime n = let
    fun generate i = let
        fun gen (l, i) = 
            if i <= 2 then 2 :: l
            else gen (i :: l, i - 2)
        in
            if (i mod 2) <> 0 
            then gen ([], i)
            else gen ([], i - 1)
        end
    fun dropComposite ([], d, _, _) = rev d
      | dropComposite (l, d, j, i) = let
        val (k :: xs) = l
        in
            if j > n then List.revAppend (d, l) 
            else if j > k  
            then dropComposite (xs, k :: d, j, i)
            else if j < k
            then dropComposite (l, d, j + i, i)
            else dropComposite (xs, d, j + i, i)
        end
    fun iterator (l, d) = let
        val (i :: xs) = l
        in  
            if i * i > n then List.revAppend (d, l)
            else if i = 2 then iterator (xs, i :: d)       
            else iterator (dropComposite 
                           (xs, [], i * i, i), i :: d)
        end
    in 
        if n < 2 then [] 
        else iterator (generate n, [])
    end

筛法还有基于数组的直观实现。[f] 下面是其解释器下命令行运行实例:

- 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

汉明数编辑

计算升序的正规数的算法经由戴克斯特拉得以流行[6],有关问题叫做“汉明问题”[7]。Dijkstra计算这些数的想法如下:

  • 汉明数的序列开始于数1
  • 要加入序列中的数有下述形式:2h,3h,5h,这里的h是序列已有的任意的汉明数。
  • 因此,可以生成最初只有一个1的序列H,并接着归并英语Merge algorithm序列2H,3H,5H,并以此类推。
fun Hamming_number n = let
    fun merge (l, p, q) = let
        fun revMerge (l, p, q) =
            if not (null p) andalso not (null q) then
                if hd p < hd q
                then revMerge ((hd p) :: l, tl p, q)
                else if hd p > hd q
                then revMerge ((hd q) :: l, p, tl q)
                else revMerge ((hd p) :: l, tl p, tl q)
            else if null p 
            then List.revAppend (q, l)
            else List.revAppend (p, l)
        in
            rev (revMerge (l, p, q))
        end
    fun timesLE m x =
        if ((x * m) <= n) then SOME (x * m) else NONE             
    fun generate l = let
        fun listMul m = List.mapPartial (timesLE m) l
        fun mergeMul (m, l) = merge ([], (listMul m), l)
        in
            foldl mergeMul (listMul 2) [3, 5]
        end
    fun iterator (l, d, i) =
        if i >= n then merge ([], l, d)
        else iterator (generate l, merge ([], l, d), i * 2)
    in
        if n > 0 then iterator ([1], [], 2) else []
    end

下面是它的解释器下命令行运行实例:

- 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

示例汉明数程序代码一般用来展示函数式编程语言特性[8][g]

排序算法编辑

下面是简单的插入排序算法的实现:

fun insertSort l = let
    fun insert (i, d, r) =
        if (null r) orelse i < (hd r)
        then List.revAppend (d, (i :: r))
        else insert (i, (hd r) :: d, tl r)
    fun iterator (l, r) =
        if (null l) then r
        else iterator (tl l, insert (hd l, [], r))
    in
        iterator (l, [])
    end

下面是快速排序算法的自顶向下实现:

fun quickSort [] = []
  | quickSort [x] = [x]
  | quickSort [x, y] =
    if x <= y then [x, y] else [y, x]
  | quickSort [x, y, z] = let
    val (y, z) = if y <= z then (y, z) else (z, y)
    val (x, y) = if x <= y then (x, y) else (y, x)
    val (y, z) = if y <= z then (y, z) else (z, y)
    in
        [x, y, z]
    end
  | quickSort (pivot :: xs) = let
    fun partition f l = let
        fun divide ([], p, q) = (p, q)
          | divide (h :: t, p, q) =
            if (f h) 
            then divide (t, h :: p, q)
            else divide (t, p, h :: q)
        in
            divide (l, [], [])
        end
    fun compare n x = (x <= n)
    val (le, gt) = partition (compare pivot) xs
    in  
        (quickSort le) @ (pivot :: (quickSort gt))
    end

基本库partition函数实现对快速排序而言有不必要的反转。[h] 下面是快速排序的自底向上实现:

fun quickSort l = let 
    fun divideAppend (l, lol) = let
        val (pivot :: xs) = l
        fun partition f l = let
            fun divide ([], p, q) = (p, q)
              | divide (h :: t, p, q) =
                if (f h) 
                then divide (t, h :: p, q)
                else divide (t, p, h :: q)
            in
                divide (l, [], [])
            end
        fun compare n x = (x <= n)
        val (le, gt) = partition (compare pivot) xs
        in
           (gt :: [pivot] :: le :: lol)
        end
    fun iterator (l, []) = l
      | iterator (l, [] :: xs) = iterator (l, xs)
      | iterator (l, [x] :: xs) = iterator (x :: l, xs)
      | iterator (l, [x, y] :: xs) = let
        val (x, y) = if x <= y then (x, y) else (y, x) 
        in
            iterator (x :: y :: l, xs)
        end
      | iterator (l, [x, y, z] :: xs) = let
        val (y, z) = if y <= z then (y, z) else (z, y)
        val (x, y) = if x <= y then (x, y) else (y, x)
        val (y, z) = if y <= z then (y, z) else (z, y)
        in
            iterator (x :: y :: z :: l, xs)
        end
      | iterator (l, x :: xs) =
            iterator (l, divideAppend (x, xs))        
    in
        iterator ([], [l])
    end

下面是归并排序算法的自底向上法实现:

fun mergeSort l = let
    fun sortAppend ([], lol) = lol
      | sortAppend ([x], lol) = [x] :: lol
      | sortAppend ([x, y], lol) =
        if x <= y then [x, y] :: lol else [y, x] :: lol
      | sortAppend (x :: y :: z :: xs, lol) = let
        val (x, y) = 
            if x <= y then (x, y) else (y, x)
        val (x, y, z) =
            if y <= z then (x, y, z)
            else if x <= z then (x, z, y)
            else (z, x, y)
        in
            sortAppend (xs, [x, y, z] :: lol)
        end
    fun mergeWith _ (l, [], []) = l
      | mergeWith _ (l, p, []) = List.revAppend (p, l)  
      | mergeWith _ (l, [], q) = List.revAppend (q, l)
      | mergeWith cmp (l, p :: ps, q :: qs) =
        if cmp (p, q)
        then mergeWith cmp (p :: l, ps, q :: qs)
        else mergeWith cmp (q :: l, p :: ps, qs)
    val mergeRev = mergeWith (fn (x, y) => (x >= y))
    val revMerge = mergeWith (fn (x, y) => (x < y))
    fun mergeIter _ (newlol, []) = newlol
      | mergeIter _ (newlol, [x]) = (rev x) :: newlol 
      | mergeIter merge (newlol, x :: y :: xs) = 
            mergeIter merge (merge ([], x, y) :: newlol, xs)
    fun iterator ([], _) = []
      | iterator ([x], isRev) =
        if isRev then rev x else x
      | iterator (lol, isRev) = let
        val merge = if isRev then mergeRev else revMerge
        in
            iterator (mergeIter merge ([], lol), not isRev)
        end
    in
        iterator (sortAppend (l, []), false)
    end

初始分解的子列表采用了插入排序,还可进一步增加其大小。[i] 归并排序也有自顶向下实现。[j] 下面是堆排序的基于数组的实现:

fun heapSort l = let
    val h = Array.fromList l;
    val len = Array.length h;
    val temp = ref 0;
    fun get a i = Array.sub (a, i);
    fun set a i v = Array.update (a, i, v);
    val get_heap = get h and set_heap = set h;
    fun siftup (i, v, n) = let
        fun siftupIter i = let
            val lh = i * 2 + 1;
            val rh = lh + 1;
            val next =
                if (lh >= n) then i 
                else if (rh < n) 
                    andalso (get_heap rh) > (get_heap lh)
                then rh else lh
            in
                if next = i orelse (get_heap next) <= v
                then set_heap i v
                else (set_heap i (get_heap next);
                      siftupIter next)
            end
        in
             siftupIter i    
        end
    fun heapify () = let
        fun heapifyIter i =
            if i < 0 then ()
            else (siftup (i, get_heap i, len);
                  heapifyIter (i - 1))
        in
            heapifyIter (len div 2 - 1)
        end
    fun iterator (l, i) =
        if i < 0 then l
        else (temp := (get_heap 0);
              siftup (0, get_heap i, i); 
              iterator (!temp :: l, i - 1))
    in
        heapify (); 
        iterator ([], len - 1)
    end

排序算法关注计算复杂度,特别是时间复杂度,基本库函数的实现细节也要考虑在内,除非必需的情况避免使用遍历整个列表的length函数。[k] 编写排序算法还可能需要伪随机数列表用于测试。[l]

语言解释器编辑

定义和处理一个小型表达式语言是相对容易的:

exception Err;
 
datatype ty
  = IntTy
  | BoolTy;
 
datatype exp
  = True
  | False
  | Int of int
  | Not of exp
  | Add of exp * exp
  | If of exp * exp * exp;
 
fun typeOf (True) = BoolTy
  | typeOf (False) = BoolTy
  | typeOf (Int _) = IntTy
  | typeOf (Not e) = 
    if typeOf e = BoolTy
    then BoolTy
    else raise Err
  | typeOf (Add (e1, e2)) = 
    if (typeOf e1 = IntTy) andalso (typeOf e2 = IntTy)
    then IntTy
    else raise Err
  | typeOf (If (e1, e2, e3)) = 
    if typeOf e1 <> BoolTy
    then raise Err
    else if typeOf e2 <> typeOf e3 then raise Err
    else typeOf e2

fun eval (True) = True
  | eval (False) = False
  | eval (Int n) = Int n
  | eval (Not e) = (case eval e
    of  True => False
     |  False => True
     |  _ => raise Fail "type-checking is broken")
  | eval (Add (e1, e2)) = let
    val (Int n1) = eval e1
    val (Int n2) = eval e2
    in
        Int (n1 + n2)
    end
  | eval (If (e1, e2, e3)) = 
    if eval e1 = True
    then eval e2
    else eval e3
 
fun exp_repr e = let
    val msg = case e
        of  True  => "True"
         |  False => "False"
         |  Int n => Int.toString n
         |  _ => ""     
    in
        msg ^ "\n"
    end
    
(* 忽略TypeOf的返回值,它在类型错误时发起Err *) 
fun evalPrint e = (ignore (typeOf e); print (exp_repr (eval e)));

将这段代码录入文件比如expr-lang.sml,并在命令行下执行sml expr-lang.sml,可以用如下在正确类型的和不正确类型上运行的例子,测试这个新语言:

- 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
  raised at: expr-lang.sml:25.20-25.23

其他示例编辑

  1. ^ 子句集合是穷尽和不冗余的函数示例:
    fun hasCorners (Circle _) = false
      | hasCorners _ = true
    

    如果控制通过了第一个模式Circle,则这个值必定是要么Square要么Triangle。在任何这些情况下,这个形状都有角点,所以返回true而不用区分具体是那种情况。

  2. ^ 不详尽的模式示例:
    fun center (Circle (c, _)) = c
      | center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)
    

    这里在center函数中没有给Triangle的模式。 编译器发起模式不详尽的一个警告,并且如果在运行时间,Triangle被传递给这个函数,则发起异常Match

  3. ^ 存在模式冗余的(无意义)函数示例:
    fun f (Circle ((x, y), r)) = x+y
      | f (Circle _) = 1.0
      | f _ = 0.0
    

    匹配第二个子句的模式的任何值都也匹配第一个子句的模式,所以第二个子句是不可到达的。因此这个定义整体上是冗余的。

  4. ^ 映射函数的实际实现:
    fun map f = let
        fun m [] = []
    	  | m [a] = [f a]
    	  | m [a, b] = [f a, f b]
    	  | m [a, b, c] = [f a, f b, f c]
    	  | m (a :: b :: c :: d :: r) = f a :: f b :: f c :: f d :: m r
        in
    	    m
        end
    

    折叠函数的实际实现:

    fun foldl f b l = let
        fun f2 ([], b) = b
    	  | f2 (a :: r, b) = f2 (r, f (a, b))
        in
    	    f2 (l, b)
        end
    
    fun foldr f b l = foldl f b (rev l)
    

    过滤器函数的实际实现:

    fun filter pred [] = []
      | filter pred (a :: rest) =
        if pred a
    	then a :: (filter pred rest)
    	else (filter pred rest)
    
  5. ^ 对分数采取修约的有理数实现:
    signature ARITH =
    sig
        type t;
        val zero : t;
        val one : t;
        val fromInt: int -> t;  
        val fromIntPair : int * int -> t;
        val repr : t -> unit;
        val succ : t -> t;
        val pred : t -> t;
        val ~ : t -> t;
        val + : t * t -> t;
        val - : t * t -> t;
        val * : t * t -> t;
        val / : t * t -> t;
    end;
    
    structure Rational : ARITH =
    struct
        type t = int * int;
        val zero = (0, 1);
        val one = (1, 1);
        val maxInt = (let val SOME a = Int.maxInt in Int.toLarge a end);
        fun fromInt n = (n, 1);
        fun neg (a, b) = (~a, b);
        fun fromLargePair (a, b) = (Int.fromLarge a, Int.fromLarge b); 
        fun fromIntPair (num, den) = let
            fun reduced_fraction (numerator, denominator) = let
                fun gcd (n, 0) = n
                  | gcd (n, d) = gcd (d, n mod d)
                val d = gcd (numerator, denominator)
                in 
                    if d > 1 then (numerator div d, denominator div d) 
                    else (numerator, denominator)
                end
            in
                if num < 0 andalso den < 0
                then reduced_fraction (~num, ~den)
                else if num < 0 
                then neg (reduced_fraction (~num, den))
                else if den < 0
                then neg (reduced_fraction (num, ~den))
                else reduced_fraction (num, den)
            end
        fun repr (a, b) = let
            val m = if (b = 0) then 0 else if (a >= 0) then a div b else ~a div b;
            val n = if (b = 0) then 1 else if (a >= 0) then a mod b else ~a mod b;
            val ms = Int.toString m and ns = Int.toString n and bs = Int.toString b;
            in 
                if n <> 0 andalso m <> 0 andalso a < 0
                then print ("~" ^ ms ^ " - " ^ ns ^ "/" ^ bs ^ "\n")
                else if n <> 0 andalso m <> 0  
                then print (ms ^ " + " ^ ns ^ "/" ^ bs ^ "\n")
                else if n <> 0 andalso m = 0 andalso a < 0
                then print ("~" ^ ns ^ "/" ^ bs ^ "\n")
                else if n <> 0 andalso m = 0 
                then print (ns ^ "/" ^ bs ^ "\n")
                else if a < 0 
                then print ("~" ^ ms ^ "\n")
                else print (ms ^ "\n")
            end
        fun convergent (i, n, d, h_1, k_1, h_2, k_2) = 
            if i <> 0 andalso ((h_1 > (maxInt - h_2) div i)
                orelse (k_1 > (maxInt - k_2) div i))
            then (h_1, k_1)  
            else if n = 0
            then (i * h_1 + h_2, i * k_1 + k_2) 
            else convergent (d div n, d mod n, n,
                             i * h_1 + h_2, i * k_1 + k_2, h_1, k_1) 
        fun add ((a, b), (c, d)) = let
            val la = Int.toLarge a and lb = Int.toLarge b;
            val lc = Int.toLarge c and ld = Int.toLarge d; 
            val m = la * ld + lb * lc and n = lb * ld; 
            in 
                if b = d 
                then fromIntPair (a + c, b)
                else fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
            end 
        fun sub ((a, b), (c, d)) = let
            val la = Int.toLarge a and lb = Int.toLarge b;
            val lc = Int.toLarge c and ld = Int.toLarge d;   
            val m = la * ld - lb * lc and n = lb * ld;
            in  
                if b = d
                then fromIntPair (a - c, b)
                else if m < 0 
                then neg (fromLargePair (convergent (~m div n, ~m mod n, n, 1, 0, 0, 1)))
                else if m > 0
                then fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
                else (0, 1)
            end
        fun mul ((a, b), (c, d)) = let
            val la = Int.toLarge a and lb = Int.toLarge b;
            val lc = Int.toLarge c and ld = Int.toLarge d; 
            val m = la * lc and n = lb * ld; 
            in  
                fromLargePair (convergent (m div n, m mod n, n, 1, 0, 0, 1))
            end
        fun op + ((a, b), (c, d)) = 
            if a < 0 andalso c < 0 
            then neg (add ((~a, b), (~c, d)))
            else if a < 0
            then sub ((c, d), (~a, b))
            else if c < 0
            then sub ((a, b), (~c, d))
            else add ((a, b), (c, d))
        fun op - ((a, b), (c, d)) = 
            if a < 0 andalso c < 0 
            then sub ((~c, d), (~a, b))
            else if a < 0
            then neg (add ((~a, b), (c, d)))
            else if c < 0
            then add ((a, b), (~c, d))
            else sub ((a, b), (c, d))
        fun op * ((a, b), (c, d)) = 
            if a < 0 andalso c < 0  
            then mul ((~a, b), (~c, d))
            else if a < 0
            then neg (mul ((~a, b), (c, d)))
            else if c < 0
            then neg (mul ((a, b), (~c, d)))
            else mul ((a, b), (c, d))
        fun op / ((a, b), (c, d)) =
            if a < 0 andalso c < 0  
            then mul ((~a, b), (d, ~c))
            else if a < 0
            then neg (mul ((~a, b), (d, c)))
            else if c < 0
            then neg (mul ((a, b), (d, ~c)))
            else mul ((a, b), (d, c))
        fun succ a = add (a, one)
        fun pred a = sub (a, one)
        fun ~ a = neg a
    end;
    
  6. ^ 筛法基于数组的实现:
    fun prime n = let
        val sieve = Array.array (n + 1, true);
        fun markComposite (j, i) =
            if j > n then () 
            else (Array.update (sieve, j, false); 
                  markComposite (j + i, i))
        fun checkPrime i = 
            if Array.sub (sieve, i) 
            then markComposite (i * i, i) 
            else () 
        fun iterator i =
            if i * i > n then ()
            else (checkPrime i; 
                  iterator (i + 1))
        fun generate (l, i) = 
            if i < 2 then l
            else if Array.sub (sieve, i) 
            then generate (i :: l, i - 1)
            else generate (l, i - 1) 
        in 
            if n < 2 then [] 
            else (iterator 2;
                 generate ([], n))
        end
    
  7. ^ 汉明数进一步性质演示代码:
    fun printIntList (l: int list) =
        print ((String.concatWith " " (map Int.toString l)) ^ "\n");
    
    fun diff (l, p, q) = let
            fun revDiff (l, p, q) =
                if not (null p) andalso not (null q) then
                    if hd p < hd q
                    then revDiff ((hd p) :: l, tl p, q)
                    else if hd p > hd q
                    then revDiff (l, p, tl q)
                    else revDiff (l, tl p, tl q)
                else if null q 
                then List.revAppend (p, l)
                else l
            in
                rev (revDiff (l, p, q))
            end
    
    fun Hamming_number n = let
        fun merge (l, p, q) = let
            fun revMerge (l, p, q) =
                if not (null p) andalso not (null q) then
                    if hd p < hd q
                    then revMerge ((hd p) :: l, tl p, q)
                    else if hd p > hd q
                    then revMerge ((hd q) :: l, p, tl q)
                    else revMerge ((hd p) :: l, tl p, tl q)
                else if null p 
                then List.revAppend (q, l)
                else List.revAppend (p, l)
            in
                rev (revMerge (l, p, q))
            end
        fun times m x = (x * m)             
        fun generate l = let
            fun listMul m = map (times m) l
            fun mergeMul (m, l) = merge ([], (listMul m), l)
            in
                printIntList (listMul 2);
                printIntList (diff ([], listMul 3, listMul 2));
                printIntList (diff ([], listMul 5, 
                              merge ([], listMul 2, listMul 3)));  
                foldl mergeMul (listMul 2) [3, 5]
            end
        fun iterator (l, d, i) =
            if i >= n then merge ([], l, d)
            else iterator (generate l, merge ([], l, d), i * 2)
        in
            if n > 0 then iterator ([1], [], 2) else []
        end
    
    - val _ = Hamming_number 250;
    2
    3
    5
    4 6 10
    9 15
    25
    8 12 18 20 30 50
    27 45 75
    125
    16 24 36 40 54 60 90 100 150 250
    81 135 225 375
    625
    32 48 72 80 108 120 162 180 200 270 300 450 500 750 1250
    243 405 675 1125 1875
    3125
    64 96 144 160 216 240 324 360 400 486 540 600 810 900 1000 1350 1500 2250 2500 3750 6250
    729 1215 2025 3375 5625 9375
    15625
    128 192 288 320 432 480 648 720 800 972 1080 1200 1458 1620 1800 2000 2430 2700 3000 4050 4500 5000 6750 7500 11250 12500 18750 31250
    2187 3645 6075 10125 16875 28125 46875
    78125
    
  8. ^ 划分函数的实际实现:
    fun partition pred l = let
        fun loop ([], trueList, falseList) =
                (rev trueList, rev falseList)
          | loop (h :: t, trueList, falseList) =
            if pred h then loop (t, h :: trueList, falseList)
            else loop (t, trueList, h :: falseList)
        in
    	    loop (l, [], [])
        end
    
  9. ^ 分解成4元素子列表的函数:
        fun sortAppend ([], lol) = lol
          | sortAppend ([x], lol) = [x] :: lol
          | sortAppend ([x, y], lol) =
            if x <= y then [x, y] :: lol else [y, x] :: lol
          | sortAppend ([x, y, z], lol) = let
            val (x, y, z) =
                if x <= y then
                    if y <= z then (x, y, z)
                    else if x <= z then (x, z, y)
                    else (z, x, y)
                else 
                    if x <= z then (y, x, z)
                    else if y <= z then (y, z, x)
                    else (z, y, x)
            in
                [x, y, z] :: lol
            end
          | sortAppend (w :: x :: y :: z :: xs, lol) = let
            val (w, x) = 
                if w <= x then (w, x) else (x, w)
            val (w, x, y) =
                if x <= y then (w, x, y)
                else if w <= y then (w, y, x)
                else (y, w, x)
            val (w, x, y, z) =
                if y <= z then (w, x, y, z)
                else if x <= z then (w, x, z, y)
                else if w <= z then (w, z, x, y)
                else (z, w, x, y)
            in
                sortAppend (xs, [w, x, y, z] :: lol)
            end
    
  10. ^ 归并排序算法的自顶向下实现:
    fun mergeSort [] = []
      | mergeSort [x] = [x]
      | mergeSort [x, y] =
        if x <= y then [x, y] else [y, x]
      | mergeSort [x, y, z] =
        if x <= y then
            if y <= z then [x, y, z]
            else if x <= z then [x, z, y] 
            else [z, x, y]
        else 
            if x <= z then [y, x, z]
            else if y <= z then [y, z, x]
            else [z, y, x] 
      | mergeSort l = let
        val len = length l
        fun split (l, p, q, i) = 
            if (i = 0) then (rev p, l)
            else split (tl l, (hd l) :: p, q, i - 1)
        fun merge (l, p, q) = let
            fun revMerge (l, p, q) =
                if not (null p) andalso not (null q) then
                    if (hd p) <= (hd q)
                    then revMerge ((hd p) :: l, tl p, q)
                    else revMerge ((hd q) :: l, p, tl q)
                else if null p 
                then List.revAppend (q, l)
                else List.revAppend (p, l)
            in
                rev (revMerge (l, p, q))
            end
        val (ls, rs) = split (l, [], [], len div 2)
        in
            merge ([], mergeSort ls, mergeSort rs)
        end
    
  11. ^ 列表长度函数的实际实现:
    fun length l = let
        (* fast add that avoids the overflow test *)
        val op + = Int.fast_add
        fun loop (n, []) = n
    	  | loop (n, [_]) = n + 1
    	  | loop (n, _ :: _ :: l) = loop (n + 2, l)
        in
    	    loop (0, l)
        end
    
  12. ^ 线性同余伪随机数列表生成函数:
    fun randList (n, seed) = let
        val randx = ref seed;
        fun lcg () = (randx := (!randx * 1366 + 150889) mod 714025; !randx);
        fun iterator (l, i) =
            if i = 0 then l
            else iterator (lcg () :: l, i - 1)
        in
            iterator ([], n)
        end
    

参见编辑

引用编辑

  1. ^ Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17(3):348–375, 1978.
  2. ^ Gordon, Michael J. C. From LCF to HOL: a short history. 1996 [2007-10-11]. 
  3. ^ David MacQueen. Modules for Standard ML, LFP '84 Proceedings of the 1984 ACM Symposium on LISP and functional programming: 198–207. August 1984. 
  4. ^ Programming language for "special forces" of developers., Russian Software Development Network: Nemerle Project Team, [January 24, 2021] 
  5. ^ Tate, Bruce A.; Daoud, Fred; Dees, Ian; Moffitt, Jack. 3. Elm. Seven More Languages in Seven Weeks Book version: P1.0-November 2014. The Pragmatic Programmers, LLC. 2014: 97, 101. ISBN 978-1-941222-15-7. On page 101, Elm creator Evan Czaplicki says: 'I tend to say "Elm is an ML-family language" to get at the shared heritage of all these languages.' ["these languages" is referring to Haskell, OCaml, SML, and F#.] 
  6. ^ Dijkstra, Edsger W., 17. An exercise attributed to R. W. Hamming, A Discipline of Programming, Prentice-Hall: 129–134, 1976, ISBN 978-0132158718 
    Dijkstra, Edsger W., Hamming's exercise in SASL (PDF), 1981, Report EWD792. Originally a privately circulated handwritten note .
  7. ^ Hamming Problem. Cunningham & Cunningham, Inc. [September 2, 2014]. 
  8. ^ Hemmendinger, David, The "Hamming problem" in Prolog, ACM SIGPLAN Notices, 1988, 23 (4): 81–86, doi:10.1145/44326.44335 .
    Yuen, C. K., Hamming numbers, lazy evaluation, and eager disposal, ACM SIGPLAN Notices, 1992, 27 (8): 71–75, doi:10.1145/142137.142151 .
  9. ^ "OCaml is an industrial strength programming language supporting functional, imperative and object-oriented styles". Retrieved on January 2, 2018.

延伸阅读编辑

  • The Definition of Standard ML (PDF).  Robin Milner, Mads Tofte, Robert Harper, MIT Press 1990; (revised edition adds author David MacQueen), MIT Press 1997, ISBN 0-262-63181-4.
  • Commentary on Standard ML, Robin Milner, Mads Tofte, MIT Press 1997, ISBN 0-262-63137-7.
  • ML for the Working Programmer, Lawrence Paulson, Cambridge University Press 1991, 1996, ISBN 0-521-57050-6.
  • Harper, Robert. Programming in Standard ML (PDF). Carnegie Mellon University. 2011. 
  • Elements of ML Programming, Jeffrey D. Ullman, Prentice-Hall 1994, 1998, ISBN 0-13-790387-1.

外部链接编辑