ML語言
編程範型 | 多范型:函數式,指令式 |
---|---|
設計者 | 羅賓·米爾納及愛丁堡大學其他人 |
面市時間 | 1973年 |
型態系統 | 類型推論,靜態類型,強類型 |
衍生副語言 | |
Standard ML, OCaml | |
啟發語言 | |
ISWIM[1],PAL[2],POP-2[1],GEDANKEN[1] | |
影響語言 | |
Clojure、Coq、Cyclone、C++、Elm[3]、Futhark[4]、F#、F*、Haskell、Idris、Lazy ML[5]、Miranda、Nemerle[6]、OCaml、Opa、Rust、Scala、Standard ML、Ur[7] | |
ML(Meta Language:元語言),是一個函數式、指令式的通用的程式語言,它著稱於使用了多態的Hindley–Milner類型推論[8]。ML能自動的指定多數表達式的類型,不要求顯式的類型標註,而且能夠確保類型安全,已經正式證明了有良好類型的ML程序不會導致運行時間類型錯誤[8]。
ML提供了對函數實際參數的模式匹配、垃圾回收、指令式編程、傳值調用和柯里化。它被大量的用於程式語言研究之中,並且是全面規定了的和使用形式語義驗證了的少數語言之一。它的類型和模式匹配使得它非常適合併且經常用於在其他形式語言上進行操作,比如在編譯器構造、自動化定理證明和形式驗證中。
歷史
在1970年代早期,ML由愛丁堡大學的羅賓·米爾納及他人研製出來[1],用於在LCF定理證明器中開發證明策略[9]。LCF的語言是「PPλ」,它是一階邏輯演算與有類型的多態λ演算的結合,以ML作為元語言。ML的語法從ISWIM及其擴展實現PAL得到了啟發[2],LCF ML運行在DEC-10/TOPS-10主機的Stanford LISP 1.6下[10]。
在1980年,Luca Cardelli於愛丁堡大學的VAX/VMS系統上開發了ML編譯器,它被稱為「VAX ML」[11],以區別於LCF版本的「DEC-10 ML」[12]。VAX ML的編譯器和運行時間系統二者,都是用Pascal書寫而建立在「函數抽象機器」(FAM)之上[13]。在1982年,愛丁堡大學的Kevin Mitchell,用VAX ML重寫了VAX ML編譯器,隨即John Scott和Alan Mycroft加入了開發,在又進行一系列重寫改進之後,新的編譯器被稱為「Edinburgh ML」[14]。
在1981年,INRIA的Gérard Huet,將最初的LCF ML適配到Multics系統的Maclisp下,並且增加了編譯器[15]。這個實現被描述於INRIA內部文檔「ML手冊」之中[16],它被開發者自稱為「Le_ML」[17]。劍橋大學的Lawrence Paulson用它開發了基於Franz Lisp的Cambridge LCF[18],進而劍橋大學的Michael J. C. Gordon又用它開發了基於Common Lisp的第一版的HOL[19]。
在1983年,Robin Milner由兩個動機驅使開始重新設計ML[20]。其一是愛丁堡大學的Rod Burstall及其小組在規定上的工作,具體化為規定語言CLEAR[21],和表達可執行規定的函數式語言HOPE[22]。這項工作與ML有關的是兩方面成果:首先,HOPE擁有優雅的編程特徵,特別是模式匹配[23],和子句式函數定義[24];其次,是使用在接口中的簽名,進行規定的模塊化構造的想法。其二是Luca Cardelli在VAX ML上的工作,通過增加命名記錄和可變類型,擴展了ML中數據類型的品目[25]。
在1984年,貝爾實驗室的David MacQueen提出了對Standard ML的模塊系統的設計[26]。在Standard ML的持續設計期間[27],Edinburgh ML被漸進的修改,充當了Standard ML的近似原型實現[28]。在1986年,普林斯頓大學的Andrew Appel和貝爾實驗室的David MacQueen,以Edinburgh Standard ML作為起步開發環境[29],開始了專注於生成高質量機器代碼的Standard ML of New Jersey的活躍開發[30]。
在1990年,Robin Milner、Mads Tofte和Robert Harper制定的Standard ML的正式規定《The Definition of Standard ML》最終完成[31];在1997年,這個標準規定增補了David MacQueen為作者並進行了修訂[32]。在1989年,Mads Tofte、Nick Rothwell和David N. Turner於愛丁堡大學開始開發ML Kit編譯器,為了強調清晰性而非高效,將標準定義直接轉譯成一組Standard ML模塊;在1992年和1993年期間,主要通過愛丁堡大學的Nick Rothwell和哥本哈根大學計算機科學系(DIKU)的Lars Birkedal的工作[33],ML Kit第一版完成並開源發行[34]。
在1987年,INRIA的Ascánder Suárez,基於巴黎第七大學的Guy Cousineau的「範疇抽象機器」(CAM)[35],利用Le Lisp的運行時間系統重新實現了Le_ML,並正式命名為Caml[15]。在1990年和1991年,INRIA的Xavier Leroy基於用C實現的字節碼解釋器[36],利用Damien Doligez提供的內存管理系統重新實現了Caml,並稱其為Caml Light[37]。在1995年,Xavier Leroy又增加了機器代碼編譯器和高層模塊系統[38],這個版本也稱為「Caml Special Light」。在1996年,INRIA的Didier Rémy和Jérôme Vouillon,向Caml Special Light增加了物件導向特徵[39],從而形成了OCaml[40]。
今天ML家族的兩個主要的方言是Standard ML和OCaml。ML的實力大多被用於語言設計和操作,比如建構編譯器、分析器、定理證明器,但是它作為通用語言也被用於生物信息和財務系統等領域。ML確立了靜態類型函數式編程范型,從而在程式語言歷史上占有顯要地位,它的思想在影響了眾多的語言,例如Haskell、Nemerle[6]、ATS和Elm[3]。
解釋與編譯
ML代碼片段很容易通過將其錄入到「頂層」來研習,它也叫作讀取﹣求值﹣輸出循環或REPL。這是列印結果或定義的表達式的推論類型的交互式會話。很多SML實現提供交互式REPL,比如SML/NJ:
$ sml
Standard ML of New Jersey v110.79 [built: Sun Nov 6 06:43:07 2022]
-
可以在提示符-
後鍵入代碼。例如計算1 + 2 * 3
:
- 1 + 2 * 3;
val it = 7 : int
頂層推論這個表達式的類型為int
並給出結果7
。如果輸入不完全則列印第二提示符=
,這時經常可以用;
終結輸入。it
是給未指定變量的表達式的標準變量。輸入control-C可返回解釋器頂層,輸入control-D可退出解釋器。可以使用第三方工具rlwrap
運行SML/NJ解釋器,它處理用戶輸入並提供readline
的行編輯、持久歷史和補全功能。
下面是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書寫的程序構成自要被求值的表達式,而非語句或命令,儘管一些表達式返回一個平凡的unit
值並且只為其副作用而求值。以下章節介紹採用Standard ML的語法和語義。
函數
就像所有的函數式語言一樣,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 fac n = let
fun loop (0, acc) = acc
| loop (n, acc) = loop (n - 1, n * acc)
in
loop (n, 1)
end
let
表達式的值是在in
和end
之間表達式的值。這個遞歸函數的實現不保證能夠終止,因為負數實際參數會導致遞歸調用的無窮降鏈條件。更健壯的實現會在遞歸前檢查實際參數為非負數,並在有問題的情況,即n
是負數的時候,啟用例外處理:
fun fac n = let
fun loop (0, acc) = acc
| loop (n, acc) = loop (n - 1, n * acc)
in
if (n < 0)
then raise Fail "negative argument"
else loop (n, 1)
end
類型
有一些基本類型可以當作是「內建」的,因為它們是在Standard ML標準基本庫中預先定義的,並且語言為它們提供文字表示法,比如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
和短路求值的中綴算符andalso
、orelse
。
包括上述基本類型的各種類型可以用多種方式組合。一種方式是元組,它是值的有序集合,比如表達式(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) * int
和int * (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
的函數sum
和average
。第二段創建中綴算子averaged_with
,接著定義它為類型int * int -> int
的函數。最後的int_pair
函數的類型是int -> int * int
。
下列函數是多態類型的一個例子:
fun pair x = (x, x)
編譯器無法推論出的pair
的特殊化了的類型,它可以是int -> int * int
、real -> real * real
甚至是(int * real -> string) -> (int * real -> string) * (int * real -> string)
。在Standard ML中,它可以簡單指定為多態類型'a -> 'a * 'a
,這裡的'a
(讀作「alpha」)是一個類型變量,指示任何可能的類型。在上述定義下,pair 3
和pair "x"
都是有良好定義的,分別產生(3, 3)
和("x", "x")
。
SML標準基本庫包括了重載標識符:+
、-
、*
、div
、mod
、/
、~
、abs
、<
、>
、<=
、>=
。標準基本庫提供了多態函數:!
、:=
、o
、before
、ignore
。中綴運算符可以有從預設最低0
到最高9
的任何運算符優先級。標準基本庫提供了如下內建中綴規定:
infix 7 * / div mod
infix 6 + - ^
infixr 5 :: @
infix 4 = <> > >= < <=
infix 3 := o
infix 0 before
等式類型
算符=
和<>
分別被定義為多態的等式和不等式。=
它確定兩個值是否相等,有著類型''a * ''a -> bool
。這意味著它的兩個運算數必須有相同的類型,這個類型必須是等式類型(eqtype
)。上述基本類型中除了real
之外,int
、real
、string
、char
和bool
都是等式類型。
例如:3 = 3
、"3" = "3"
、#"3" = #"3"
和true = true
,都是有效的表達式並求值為true
;而3 = 4
是有效表達式並求值為false
,3.0 = 3.0
是無效表達式而被編譯器拒絕。這是因為IEEE浮點數等式打破了ML中對等式的一些要求。特別是nan
不等於自身,所以關係不是自反的。
元組和記錄類型是等式類型,當時且僅當它的每個成員類型是等式類型;例如int * string
、{b : bool, c : char}
和unit
是等式類型,而int * real
和{x : real}
不是。函數類型永遠不是等式類型,因為一般情況下不可能確定兩個函數是否等價。
類型聲明
類型聲明或同義詞(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提供了對代數數據類型(ADT)的強力支持。一個ML數據類型可以被當作是元組的不交並(積之和)。數據類型使用datatype
關鍵字來定義,比如:
datatype int_or_string
= INT of int
| STRING of string
| NEITHER
這個數據類型聲明建立一個全新的數據類型int_or_string
,還有一起的新構造子(一種特殊函數或值)INT
、STRING
和NEITHER
;每個這種類型的值都是要麼INT
具有一個整數,要麼STRING
具有一個字符串,要麼NEITHER
。寫為如下這樣:
val i = INT 3
val s = STRING "qq"
val n = NEITHER
val INT j = i
這裡最後的一個聲明通過模式匹配,將變量j
綁定到變量i
所綁定的整數3
。val 模式 = 表达式
是綁定的一般形式,它是良好定義的,若且唯若模式和表達式有相同的類型。
數據類型可以是多態的:
datatype 'a pair
= PAIR of 'a * 'a
這個數據類型聲明建立一個新的類型'a pair
家族,比如int pair
,string 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)
模式匹配
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
綁定了四個變量m
、n
、r
和s
;第二個val
綁定了一個變量url
;第三個val
綁定了三個變量port
、addr
和name
,第四個叫分層模式,綁定了三個變量x
、fst
和snd
。
模式匹配可以在語法上嵌入到函數定義中,比如:
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)
函數可以同時接受和產生函數,比如複合函數:
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)
,map
和fold
高階函數有較高效率的實現。[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
Zero
在0
情況下發起,控制從函數p
中一起出離。
引用
初始化基礎庫還以引用的形式提供了可變的存儲。引用ref
可以在某種意義上被認為是如下這樣定義的:
datatype 'a ref = ref of 'a
還定義了內建的:=
函數來修改引用的內容,和!
函數來檢索引用的內容。階乘函數可以使用引用定義為指令式風格:
fun factImperative 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
eqtype 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),可以通過所綁定的變量見到此結構的數據內容,與之相對的是:>
,它叫做不透明歸屬,此結構的數據內容對外完全不可見。比如上面用例有結果:val c = Rat (4,3) : Rational.t
,如果改為不透明歸屬則有結果:val c = - : Rational.t
。
要用有理數進行實際上的數值計算,需要處理分數形式中分母快速增大導致溢出整數類型大小範圍等問題。[e]
函子
函子接受指定簽名的一個結構作為參數,並返回一個結構作為結果,下面示例的函子能在ARITH
簽名的結構上計算移動平均:
signature MOVINGLIST =
sig
type t
structure Arith : sig
type t end
val size : t -> int
val average : t -> Arith.t
val fromList : Arith.t list -> t
val move : t * Arith.t -> t
val expand : t * Arith.t -> t
val shrink : t -> t
val trunc : t -> t
end
functor MovingList (S: ARITH) : MOVINGLIST =
struct
type t = S.t list * int * S.t
structure Arith = S
fun size (ml : t) = #2 ml
fun average (ml : t) = #3 ml
fun fromList (l : S.t list) = let
val n = length l
val sum = foldl S.+ S.zero l
local open S in
val m = sum / (fromInt n) end
in
if (null l) then raise Empty
else (l, n, m)
end
fun move ((l, n, m) : t, new : S.t) = let
val old = List.nth (l, n - 1)
local open S in
val m' = m + (new - old) / (fromInt n) end
in
(new :: l, n, m')
end
fun expand ((l, n, m) : t, new : S.t) = let
val n' = n + 1;
local open S in
val m' = m + (new - m) / (fromInt n') end
in
(new :: l, n', m')
end
fun shrink ((l, n, m) : t) = let
val old = List.nth (l, n - 1)
val n' = if (n > 2) then n - 1 else 1
local open S in
val m' = m + (m - old) / (fromInt n') end
in
(l, n', m')
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
這個用例承上節示例,Rational
結構採用了透明歸屬,有結果如:val d = ([Rat (4,5),Rat (2,3)],2,Rat (11,15)) : MLR.t
。如果它改為不透明歸屬,則對應結果為:val d = ([-,-],2,-) : MLR.t
。
示例代碼
下列例子使用了Standard ML的語法和語義。
素數
fun prime n = let
fun isPrime (l, i) = let
fun existsDivisor [] = false
| existsDivisor (x :: xs) =
if (i mod x) = 0 then true
else if (x * x) > i then false
else existsDivisor xs
in
not (existsDivisor l)
end
fun iterate (acc, i) =
if i > n then acc
else if isPrime (acc, i)
then iterate (acc @ [i], i + 2)
else iterate (acc, i + 2)
in
if n < 2 then []
else iterate ([2], 3)
end
基本庫find
和exists
函數在不存在符合條件元素的時候會遍歷整個列表,[f]
這裡採用了特殊化了的existsDivisor
,用以在後續元素都不滿足條件時立即結束運算。
fun prime n = let
fun dropComposite (acc, [], _, _) = rev acc
| dropComposite (acc, l as x :: xs, j, i) =
if j > n then List.revAppend (acc, l)
else if x < j
then dropComposite (x :: acc, xs, j, i)
else if x > j
then dropComposite (acc, l, j + i, i)
else dropComposite (acc, xs, j + i, i)
fun init i = let
fun loop (l, i) =
if i <= 2 then l
else loop (i :: l, i - 2)
in
loop ([], i - (i + 1) mod 2)
end
fun iterate (acc, []) = rev acc
| iterate (acc, l as x :: xs) =
if x * x > n
then 2 :: List.revAppend (acc, l)
else iterate (x :: acc,
dropComposite ([], xs, x * x, x * 2))
in
if n < 2 then []
else iterate ([], init n)
end
這裡基於列表的篩法實現符合埃拉托斯特尼的原初算法[41]。篩法還有基於數組的直觀實現。[g] 下面是其解釋器下命令行運行實例:
- 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
漢明數
正規數是形如的整數,對於非負整數、和,它是可以整除的數。計算升序的正規數的算法經由戴克斯特拉得以流行[42],理察·漢明最初提出了這個問題,故而這個問題被稱為「漢明問題」,這個數列也因而被稱為漢明數。Dijkstra計算這些數的想法如下:
- 漢明數的序列開始於數
1
。 - 要加入序列中的數有下述形式:
2h, 3h, 5h
,這裡的h
是序列已有的任意的漢明數。 - 因此,可以生成最初只有一個
1
的序列H
,並接著歸併序列2H, 3H, 5H
,並以此類推。
示例漢明數程序代碼,一般用來展示,確使計算只在需要時進行的純函數式編程方式[43]。
fun Hamming_number n = let
fun merge (p, q) = let
fun revMerge (acc, p, q) =
if not (null p) andalso not (null q) then
if hd p < hd q
then revMerge ((hd p) :: acc, tl p, q)
else if hd p > hd q
then revMerge ((hd q) :: acc, p, tl q)
else revMerge ((hd p) :: acc, tl p, tl q)
else if null p
then List.revAppend (q, acc)
else List.revAppend (p, acc)
in
if (null p) then q
else if (null q) then p
else rev (revMerge ([], p, q))
end
fun mul m x =
if x <= (n div m) then SOME (x * m) else NONE
fun mapPrefix pred l = let
fun mapp ([], acc) = rev acc
| mapp (x :: xs, acc) =
(case (pred x)
of SOME a => mapp (xs, a :: acc)
| NONE => rev acc)
in
mapp (l, [])
end
fun mergeWith f (m, i) = merge (f m, i)
fun generate l = let
fun listMul m = mapPrefix (mul m) l
in
foldl (mergeWith listMul) [] [2, 3, 5]
end
fun iterate (acc, l) =
if (hd l) > (n div 2) then merge (l, acc)
else iterate (merge (l, acc), generate l)
in
if n > 0 then iterate ([], [1]) else []
end
產生指定範圍內的漢明數需要多輪運算,後面每輪中的三個列表元素乘積運算中都可能產生超出這個範圍的結果,它們不需要出現在後續的運算之中。[h]
基本庫mapPartial
函數與它所映射的函數,通過基於Option
結構的SOME
和NONE
構造子的協定,可以將所映射函數認為不符合條件的元素或者結果排除掉,它會遍歷整個列表。[i]
由於這個算法採用升序列表,故而這裡將它改寫為mapPrefix
函數,用來在特定條件不滿足條件就立即結束。下面是漢明數程序在解釋器下命令行運行實例:
- 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)[44]的高階函數foldr和map的實現,和達成一個整數列表的合計函數的簡單用例:
fun foldr' f b l = let
fun f2 ([], k) = k b
| f2 (a :: r, k) =
f2 (r, fn x => k (f (a, x)))
in
f2 (l, fn x => x)
end
fun map' f l =
foldr' (fn (x, y) => (f x) :: y) [] l
fun sum l =
foldr' (fn (x, y) => (x + y)) 0 l
對於輸入[e1, e2, ..., en]
,sum
函數等價於函數複合(fn x => x) o (fn x => e1 + x) o (fn x => e2 + x) o ... o (fn x => en + x)
,它應用於0
上得到(e1 + (e2 + (... + (en + 0)...)))
。[45]
SML/NJ支持頭等對象的續體[46]。頭等續體對一門語言而言是能完全控制指令執行次序的能力。它們可以用來跳轉到產生對當前函數調用的那個函數,或者跳轉到此前已經退出了的函數。頭等續體保存了程序執行狀態,它不保存程序數據,只保存執行上下文。
排序算法
排序算法關注計算複雜度,特別是時間複雜度,基本庫函數的實現細節也要考慮在內,比如串接函數@
,它被實現為fun l1 @ l2 = revAppend(rev l1, l2)
,除非必需的情況避免使用遍歷整個列表的rev
和length
函數。[j]
通過比較於這些排序算法的周知過程式編程語言比如C語言的實現,可以體察到ML在控制流程和列表資料結構上的相關限制,和與之相適應的採用尾遞歸的特色函數式編程風格。
插入排序
尾遞歸 | 普通遞歸 |
---|---|
fun insertSort l = let
fun insert pred (ins, l) = let
fun loop (acc, []) =
List.revAppend (acc, [ins])
| loop (acc, l as x :: xs) =
if pred (ins, x)
then List.revAppend (acc, ins :: l)
else loop (x :: acc, xs)
in loop ([], l) end
val rec ge = fn (x, y) => (x >= y)
in
rev (foldl (insert ge) [] l)
end
|
fun insertSort l = let
fun insert pred (ins, []) =
[ins]
| insert pred (ins, l as x :: xs) =
if pred (ins, x)
then ins :: l
else x :: (insert pred (ins, xs))
val rec ge = fn (x, y) => (x >= y)
in
rev (foldl (insert ge) [] l)
end
|
x 保存在形式參數acc 對應的分配堆中 |
x 保存在調用棧棧幀中
|
插入排序算法是穩定的自適應排序,它在輸入列表趨於正序的時候性能最佳,在輸入列表趨於反序的時候性能最差,因此在算法實現中,需要insert
函數所插入列表保持為反序,在插入都完成後經rev
函數再反轉回正序。在預期輸入數據趨於隨機化或者預知它經過了反轉的情況下,可以採用保持要插入列表為正序的變體插入排序算法實現,它在輸入列表趨於反序的時候性能最佳,在輸入列表趨於正序的時候性能最差,它比自適應實現少作一次全列表反轉。[k]
採用foldr
函數可以相應的保持要插入列表為正序,由於fun foldr f b l = foldl f b (rev l)
,它等同於對反轉過的列表應用變體插入排序。
希爾排序
希爾排序算法是對插入排序的改進,保持了自適應性,放棄了穩定性。[l] 下面是希爾排序的實現:
fun shellSort l = let
fun insert pred (ins, l) = let
fun loop (acc, []) =
List.revAppend (acc, [ins])
| loop (acc, l as x :: xs) =
if pred (ins, x)
then List.revAppend (acc, ins :: l)
else loop (x :: acc, xs)
in
loop ([], l)
end
val rec lt = fn (x, y) => (x < y)
fun insertSort [] = []
| insertSort [x] = [x]
| insertSort [x, y] =
if (y < x) then [y, x] else [x, y]
| insertSort (x :: y :: z :: xs) = let
val (x, y, z) =
if (y < x) then
if z < y then (z, y, x)
else if z < x then (y, z, x)
else (y, x, z)
else
if z < x then (z, x, y)
else if z < y then (x, z, y)
else (x, y, z)
in
foldl (insert lt) [x, y, z] xs
end
fun group (lol, n) = let
fun dup n = let
fun loop (acc, i) =
if i <= 0 then acc
else loop ([] :: acc, i - 1)
in
loop ([], n)
end
fun loop ([], [], accj, lol') =
List.revAppend (accj, lol')
| loop (acci, [], accj, []) =
loop ([], rev acci, [], rev accj)
| loop (acci, [], accj, lol') =
loop ([], rev acci, accj, lol')
| loop (acci, lol, accj, []) =
loop (acci, lol, [], rev accj)
| loop (acci, [] :: ls, accj, lol') =
loop (acci, ls, accj, lol')
| loop (acci, (x :: xs) :: ls, accj, l' :: ls') =
loop (xs :: acci, ls, (x :: l') :: accj, ls')
in
loop ([], lol, [], dup n)
end
val (lol, len) = foldl
(fn (x, (l, n)) => ([x] :: l, n + 1)) ([], 0) (rev l)
val incs = [1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660,
5985, 13467, 30301, 68178, 153401, 345152,
776591, 1747331, 3931496, 8845866, 19903198,
44782196, 100759940, 226709866, 510097200]
val gap = let
val v = len * 3 div 4
val thold = if (v = 0) then 1 else v
fun loop (acc, h) =
if (hd h) > thold then acc
else loop ((hd h) :: acc, tl h)
in
loop ([], incs)
end
fun sort (h, lol) = map insertSort (group (lol, h))
in
hd (foldl sort lol gap)
end
這裡採用的間隔序列是OEIS A108870,即,它是徳田尚之在1992年提出的[47]。這個序列用遞推公式表示為:hk = ⌈h'k⌉
,這裡的h'k = 2.25·h'k-1 + 1
而h'1 = 1
。假定一個列表的長度s
位於序列兩個元素之間,即hk-1 < hk ≤ s < hk+1
,如果hk ≤ ·s
,這裡的n ≤ m
,則選擇初始間隔為hk
,否則為hk-1
。在這個閾值下,對於不同長度s
的列表和對應的初始間隔h
,每個列表的這些初始子列表的平均長度,約在
≤ < ·
範圍之內。間隔序列還可以採用OEIS A102549,它是Marcin Ciura在2001年通過實驗得到的[48]。[m]
快速排序
下面是快速排序算法的自頂向下實現:
fun quickSort [] = []
| quickSort [x] = [x]
| quickSort [x, y] =
if x <= y then [x, y] else [y, x]
| quickSort [x, y, z] = let
val (x, y) = if x <= y then (x, y) else (y, x)
val (y, z) = if y <= z then (y, z) else (z, y)
val (x, y) = if x <= y then (x, y) else (y, x)
in
[x, y, z]
end
| quickSort (pivot :: xs) = let
fun partition pred l = let
fun loop ([], p, q) = (p, q)
| loop (h :: t, p, q) =
if (pred h)
then loop (t, h :: p, q)
else loop (t, p, h :: q)
in
loop (l, [], [])
end
val (le, gt) = partition (fn x => (x <= pivot)) xs
in
(quickSort le) @ (pivot :: (quickSort gt))
end
基本庫partition
函數實現對快速排序而言有不必要的反轉,[n]
這裡採用了它的簡化改寫。在ML中快速排序應採用自底向上實現:
fun quickSort l = let
fun partition pred l = let
fun loop ([], p, q) = (p, q)
| loop (h :: t, p, q) =
if (pred h)
then loop (t, h :: p, q)
else loop (t, p, h :: q)
in
loop (l, [], [])
end
fun iterate (acc, []) = acc
| iterate (acc, [] :: xs) = iterate (acc, xs)
| iterate (acc, [x] :: xs) = iterate (x :: acc, xs)
| iterate (acc, [x, y] :: xs) = let
val (x, y) = if x <= y then (x, y) else (y, x)
in
iterate (x :: y :: acc, xs)
end
| iterate (acc, [x, y, z] :: xs) = 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
iterate (x :: y :: z :: acc, xs)
end
| iterate (acc, (pivot :: d) :: xs) = let
val (le, gt) = partition (fn x => (x <= pivot)) d
in
iterate (acc, gt :: [pivot] :: le :: xs)
end
in
iterate ([], [l])
end
歸併排序
下面是歸併排序算法的自底向上法實現:
fun mergeSort l = let
fun init (acc, []) = acc
| init (acc, [x]) = [x] :: acc
| init (acc, [x, y]) =
if x <= y then [x, y] :: acc else [y, x] :: acc
| init (acc, x :: y :: z :: xs) = 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
init ([x, y, z] :: acc, xs)
end
fun mergeWith _ (acc, [], []) = acc
| mergeWith _ (acc, p, []) = List.revAppend (p, acc)
| mergeWith _ (acc, [], q) = List.revAppend (q, acc)
| mergeWith cmp (acc, p :: ps, q :: qs) =
if cmp (p, q)
then mergeWith cmp (p :: acc, ps, q :: qs)
else mergeWith cmp (q :: acc, p :: ps, qs)
val mergeRev = mergeWith (fn (x, y) => (x > y))
val revMerge = mergeWith (fn (x, y) => (x < y))
fun iterate ([], _) = []
| iterate ([x], isRev) =
if isRev then rev x else x
| iterate (acc, isRev) = let
val merge = if isRev then mergeRev else revMerge
fun loop (acci, []) = acci
| loop (acci, [x]) = (rev x) :: acci
| loop (acci, x :: y :: xs) =
loop (merge ([], x, y) :: acci, xs)
in
iterate (loop ([], acc), not isRev)
end
in
iterate (init ([], l), false)
end
考慮輸入列表[x1, ..., xi, a0, ..., a9, xj, ..., xn]
,這裡在xi
和xj
之間的10
個a
,具有相同的值並且需要保持其下標表示的次序,這裡的xi > a
並且xj < a
,並且在這個區段前後的元素總數都能被3
整除,則它被分解成子列表的列表[Xm, ..., [xj, a8, a9], [a5, a6, a7], [a2, a3, a4], [a0, a1, xi], ..., X1]
,這裡有m = n div 3
;假定這4
個含有a
的子列表兩兩歸併,在歸併正序子列表的歸併條件x < y
下,能得到[X1, ..., [xi, a4, ..., a0], [a9, ..., a5, xj], ..., Xk]
;繼續推演下去,在歸併反序子列表的歸併條件x > y
下,能得到[Xh, ..., [xj, a0, ..., a9, xi], ..., X1]
。可以看出這種歸併操作能夠保證排序算法的穩定性,即具有相同值的元素之間的相對次序保持不變。
分解初始的子列表採用了插入排序,還可進一步增加其大小。歸併排序也有自頂向下實現。[o]
堆排序
fun heapSort l = let
val h = Array.fromList l
val len = Array.length h
fun get i = Array.sub (h, i)
fun set i v = Array.update (h, i, v)
fun siftdown (i, ins, n) = let
fun sift k = let
val l = k * 2 + 1
val r = l + 1
in
if (r < n) andalso
(get r) > (get l) then r
else if (l < n) then l
else k
end
fun loop i = let
val j = sift i
in
if j = i orelse (get j) <= ins
then set i ins
else (set i (get j); loop j)
end
in
loop i
end
fun heapify () = let
fun loop i =
if i < 0 then ()
else (siftdown (i, get i, len);
loop (i - 1))
in
loop (len div 2 - 1)
end
fun generate () = let
fun loop (acc, i) = let
val t = get 0
in
if i <= 0 then t :: acc
else (siftdown (0, get i, i);
loop (t :: acc, i - 1))
end
in
if len = 0 then []
else loop ([], len - 1)
end
in
heapify ();
generate ()
end
在數組實現中,siftdown
函數融合了插入和篩選功能,它首先在暫時位於堆頂的要插入的元素,和從堆頂節點左右子堆的兩個堆頂元素中篩選出的那個元素,二者中選擇出哪個適合作堆頂元素;如果要插入元素適合,則以它為新堆頂元素而結束整個過程,否則以篩選出元素為新堆頂元素,並自頂向下逐級處理提供了新堆頂元素的子堆,將要插入元素暫時作為其堆頂元素並對它繼續進行siftdown
;siftdown
只要到達了某個堆底,就插入要插入的元素而結束整個過程。
在提取堆頂元素生成結果列表時,先提取走堆頂元素的內容,再摘掉最後的堆底元素將它的內容暫時放置在堆頂,這時堆的大小也相應的減一,隨後的siftdown
函數,篩選出新的堆頂元素,並把原最後堆底元素插入回堆中。
在heapify
函數建造堆的時候,首先自列表中間將元素分為前後兩組,後組中的元素被視為只有一個元素的堆,然後從後往前處理前組中的元素,這時它的左右子節點已經是已有的堆或者為空,在其上進行siftdown
,從而合成一個新堆。建造堆也可以採用siftup
函數來實現,它自第二個元素開始從前往後逐個處理列表元素,其前面是已有的堆,將這個新元素自堆底向上插入到這個堆中。[p]
fun heapSort l = let
datatype 'a heap
= Nil
| Leaf of 'a
| Node of 'a * int * 'a heap * 'a heap
fun key Nil =
let val SOME a = Int.minInt in a end
| key (Leaf k) = k
| key (Node (k, _, _, _)) = k
fun count Nil = 0
| count (Leaf _) = 1
| count (Node (_, c, _, _)) = c
fun left Nil = Nil
| left (Leaf _) = Nil
| left (Node (_, _, l, _)) = l
fun insert (Nil, x) = Leaf x
| insert (Leaf k, l) =
if l >= k
then Node (l, 2, Leaf k, Nil)
else Node (k, 2, Leaf l, Nil)
| insert (Node (k, _, Leaf l, Nil), r) =
if r >= k
then Node (r, 3, Leaf k, Leaf l)
else if r >= l
then Node (k, 3, Leaf r, Leaf l)
else Node (k, 3, Leaf l, Leaf r)
| insert (Node (k, c, l, r), x) = let
val (k, x) =
if k >= x then (k, x) else (x, k)
in
if (count l) <= (count r)
then Node (k, c + 1, insert (l, x), r)
else if x >= (key l)
then Node (k, c + 1, insert (r, x), l)
else Node (k, c + 1, l, insert (r, x))
end
fun extract Nil = Nil
| extract (Leaf _) = Nil
| extract (Node (_, _, l, Nil)) = l
| extract (Node (_, c, l, r)) = let
val k = key l
val n = left l
in
if n = Nil
then Node (k, c - 1, r, Nil)
else if (key n) >= (key r)
then Node (k, c - 1, extract l, r)
else Node (k, c - 1, r, extract l)
end
fun heapify () = let
fun loop (acc, []) = acc
| loop (acc, x :: xs) =
loop (insert (acc, x), xs)
in
loop (Nil, l)
end
fun generate h = let
fun loop (acc, Nil) = acc
| loop (acc, h) =
loop ((key h) :: acc, extract h)
in
loop ([], h)
end
in
generate (heapify ())
end
二元樹實現不能直接訪問堆底元素,從而不適宜通過摘掉它使堆的大小減一。這裡的insert
函數,在原堆頂元素和要插入元素中選擇適合者作為新的堆頂元素,將落選的另一個元素作為新的要插入元素,插入到利於保持這個堆平衡的那個子樹之中。這裡的extract
函數隻篩選不插入,它將堆的大小減一。
這裡的insert
和extract
函數也可以直接轉寫為等價的尾遞歸形式,與列表情況不同,只要樹結構能保持良好的平衡,採用尾遞歸形式就沒有太大的必要性。[q]
在二元樹實現下,也可以採用siftdown
函數來初始建造堆,而不需要在節點中保存關於樹狀態的統計信息。[r]
基數排序
fun radixSort l = let
fun distribute (l, d) = let
val t0 = ([], [], [], [], [], [], [], [])
fun loop (t, []) = let
fun join (acc, i) = let
val f = case i
of 1 => (#1 t) | 2 => (#2 t) | 3 => (#3 t)
| 4 => (#4 t) | 5 => (#5 t) | 6 => (#6 t)
| 7 => (#7 t) | 8 => (#8 t) | _ => []
in
if i <= 0 then acc
else join (List.revAppend (f, acc), i - 1)
end
in
join ([], 8)
end
| loop (t, x :: xs) = let
val (f0, f1, f2, f3, f4, f5, f6, f7) = t
val t = case ((x div d) mod 8)
of 0 => (x :: f0, f1, f2, f3, f4, f5, f6, f7)
| 1 => (f0, x :: f1, f2, f3, f4, f5, f6, f7)
| 2 => (f0, f1, x :: f2, f3, f4, f5, f6, f7)
| 3 => (f0, f1, f2, x :: f3, f4, f5, f6, f7)
| 4 => (f0, f1, f2, f3, x :: f4, f5, f6, f7)
| 5 => (f0, f1, f2, f3, f4, x :: f5, f6, f7)
| 6 => (f0, f1, f2, f3, f4, f5, x :: f6, f7)
| 7 => (f0, f1, f2, f3, f4, f5, f6, x :: f7)
| _ => t0
in
loop (t, xs)
end
in
loop (t0, l)
end
val SOME maxInt = Int.maxInt
val max = foldl (fn (x, y) => if x > y then x else y) 0 l
fun iterate (l, d) = let
val l' = distribute (l, d)
in
if d >= (maxInt div 8 + 1) orelse
((max div d) div 8) = 0 then l'
else iterate (l', d * 8)
end
in
iterate (l, 1)
end
這裡採用的基數是2
的3
次冪8
,代碼所使用的列表元組大小與基數大小成正比,運算量與列表中元素的總數與最大數的位數的乘積成正比。
隨機數生成
編寫排序算法進行測試除了使用簡單的數列,[s] 測試用列表還可以使用線性同餘偽隨機數函數來生成[49]:
fun randList (n, seed) = let
val randx = ref seed
fun lcg () = (randx := (!randx * 421 + 1663) mod 7875; !randx)
(* fun lcg () = (randx := (!randx * 1366 + 150889) mod 714025; !randx) *)
fun iterate (acc, i) =
if i <= 0 then acc
else iterate (lcg () :: acc, i - 1)
in
iterate ([], n)
end
語言解釋器
定義和處理一個小型表達式語言是相對容易的:
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
注釋和附錄代碼
- ^
子句集合是窮盡和不冗餘的函數示例:
fun hasCorners (Circle _) = false | hasCorners _ = true
如果控制通過了第一個模式
Circle
,則這個值必定是要麼Square
要麼Triangle
。在任何這些情況下,這個形狀都有角點,所以返回true
而不用區分具體是那種情況。 - ^
不詳盡的模式示例:
fun center (Circle (c, _)) = c | center (Square ((x, y), s)) = (x + s / 2.0, y + s / 2.0)
這裡在
center
函數中沒有給Triangle
的模式。 編譯器發起模式不詳盡的一個警告,並且如果在運行時間,Triangle
被傳遞給這個函數,則發起例外Match
。 - ^
存在模式冗餘的(無意義)函數示例:
fun f (Circle ((x, y), r)) = x+y | f (Circle _) = 1.0 | f _ = 0.0
匹配第二個子句的模式的任何值都也匹配第一個子句的模式,所以第二個子句是不可到達的。因此這個定義整體上是冗餘的。
- ^
映射函數的實際實現:
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)
- ^
對分數採取修約的有理數實現:
signature ARITH = sig eqtype 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
- ^ 找出函數的實際實現:
fun find pred [] = NONE | find pred (a :: rest) = if pred a then SOME a else (find pred rest)
存在謂詞函數的實際實現:
fun exists pred = let fun f [] = false | f (h :: t) = pred h orelse f t in f end
- ^
篩法基於數組的實現:
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 iterate i = if i * i > n then () else if Array.sub (sieve, i) then (markComposite (i * i, i); iterate (i + 1)) else iterate (i + 1) fun generate (acc, i) = if i < 2 then acc else if Array.sub (sieve, i) then generate (i :: acc, i - 1) else generate (acc, i - 1) in if n < 2 then [] else (iterate 2; generate ([], n)) end
- ^ 漢明數進一步性質演示代碼:
fun printIntList (l: int list) = print ((String.concatWith " " (map Int.toString l)) ^ "\n"); fun diff (p, q) = let fun revDiff (acc, p, q) = if not (null p) andalso not (null q) then if hd p < hd q then revDiff ((hd p) :: acc, tl p, q) else if hd p > hd q then revDiff (acc, p, tl q) else revDiff (acc, tl p, tl q) else if null q then List.revAppend (p, acc) else acc in if (null p) then [] else if (null q) then p else rev (revDiff ([], p, q)) end; fun Hamming_number n = let fun merge (p, q) = let fun revMerge (acc, p, q) = if not (null p) andalso not (null q) then if hd p < hd q then revMerge ((hd p) :: acc, tl p, q) else if hd p > hd q then revMerge ((hd q) :: acc, p, tl q) else revMerge ((hd p) :: acc, tl p, tl q) else if null p then List.revAppend (q, acc) else List.revAppend (p, acc) in if (null p) then q else if (null q) then p else rev (revMerge ([], p, q)) end fun mergeWith f (m, i) = merge (f m, i) fun mul m x = (x * m) fun generate l = let fun listMul m = map (mul m) l in printIntList (listMul 2); printIntList (diff (listMul 3, listMul 2)); printIntList (diff (listMul 5, merge (listMul 2, listMul 3))); foldl (mergeWith listMul) [] [2, 3, 5] end val count = ref 1; fun iterate (acc, l) = if (hd l) > (n div 2) then merge (l, acc) else (print ("round " ^ (Int.toString (!count)) ^ " for " ^ (Int.toString(length l)) ^ " number(s)\n"); count := !count + 1; iterate (merge (l, acc), generate l)) in if n > 0 then iterate ([], [1]) else [] end;
val l = Hamming_number 400; val h = List.filter (fn x => (x <= 400)) l; val _ = print ((Int.toString (length h)) ^ " numbers from " ^ (Int.toString (length l)) ^ " numbers\n");
- ^ 部份映射函數的實際實現:
fun mapPartial pred l = let fun mapp ([], l) = rev l | mapp (x :: r, l) = (case (pred x) of SOME y => mapp (r, y :: l) | NONE => mapp (r, l) (* end case *)) in mapp (l, []) end
- ^
列表長度函數的實際實現:
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
- ^ 變體的插入排序算法實現:
fun insertSort l = let fun insert pred (ins, l) = let fun loop (acc, []) = List.revAppend (acc, [ins]) | loop (acc, l as x :: xs) = if pred (ins, x) then List.revAppend (acc, ins :: l) else loop (x :: acc, xs) in loop ([], l) end val rec lt = fn (x, y) => (x < y) in foldl (insert lt) [] l end
- ^ 下面是希爾排序算法的原型實現,當輸入列表趨於正序的時候,
scatter
函數將其分解為一組趨於反序的子列表,經過在輸入趨於反序情況下性能最佳的變體插入排序後,gather
函數再將它們合成為一個列表:fun shellSort l = let fun insert pred (ins, l) = let fun loop (acc, []) = List.revAppend (acc, [ins]) | loop (acc, l as x :: xs) = if pred (ins, x) then List.revAppend (acc, ins :: l) else loop (x :: acc, xs) in loop ([], l) end val rec lt = fn (x, y) => (x < y) fun insertSort l = foldl (insert lt) [] l fun scatter (l, n) = let fun dup n = let fun loop (acc, i) = if i <= 0 then acc else loop ([] :: acc, i - 1) in loop ([], n) end fun loop ([], acc, lol) = List.revAppend (acc, lol) | loop (l, acc, []) = loop (l, [], rev acc) | loop (x :: xs, acc, l :: ls) = loop (xs, (x :: l) :: acc, ls) in loop (l, [], dup n) end fun gather lol = let fun loop ([], [], l) = rev l | loop (acc, [], l) = loop ([], rev acc, l) | loop (acc, [] :: ls, l) = loop (acc, ls, l) | loop (acc, (x :: xs) :: ls, l) = loop (xs :: acc, ls, x :: l) in loop ([], lol, []) end val gap = let fun loop (acc, i) = let val h = (i * 5 - 1) div 11 in if i < 5 then rev (1 :: acc) else loop (h :: acc, h) end in loop ([], length l) end fun sort (h, l) = gather (map insertSort (scatter (l, h))) in foldl sort l gap end
- ^ 希爾排序還可以採用Ciura提出的間隔序列:
val incs = [1750, 701, 301, 132, 57, 23, 10, 4, 1] val gap = let fun loop (acc, i) = let val h = (i * 4 - 1) div 9 fun iter incs = if i >= (hd incs) * 4 div 3 then incs else iter (tl incs) in if i <= ((hd incs) * 3) then List.revAppend (acc, iter incs) else loop (h :: acc, h) end in if len = 0 then [1] else loop ([], len) end
- ^
劃分函數的實際實現:
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
- ^
歸併排序算法的自頂向下實現:
fun mergeSort l = let fun sort ([], _) = [] | sort ([x], _) = [x] | sort ([x, y], _) = if x <= y then [x, y] else [y, x] | sort ([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] | sort (l, n) = let val m = n div 2 fun split (l, acc, i) = if i = 0 then (rev acc, l) else split (tl l, (hd l) :: acc, i - 1) fun merge (p, q) = let fun revMerge (acc, p, q) = if not (null p) andalso not (null q) then if (hd p) <= (hd q) then revMerge ((hd p) :: acc, tl p, q) else revMerge ((hd q) :: acc, p, tl q) else if null p then List.revAppend (q, acc) else List.revAppend (p, acc) in rev (revMerge ([], p, q)) end val (ls, rs) = split (l, [], m) in merge (sort (ls, m), sort (rs, n - m)) end in sort (l, length l) end
- ^ 堆排序算法的數組實現中,堆建造函數
heapify
也可以使用siftup
函數的數組來完成,它將新節點自堆底向上插入到合適的位置,而不對途徑節點左右子樹頂點進行比較:fun siftup i = let val ins = get i fun loop i = let val j = (i - 1) div 2 in if i <= 0 orelse (get j) >= ins then set i ins else (set i (get j); loop j) end in loop i end fun heapify () = let fun loop i = if i > (len - 1) then () else (siftup i; loop (i + 1)) in loop 1 end
- ^ 在堆排序算法的二元樹實現中,樹插入和提取函數也可以寫為等價的尾遞歸形式代碼:
exception Err; fun revLink ([], t) = t | revLink (Nil :: xs, t) = revLink (xs, t) | revLink ((Leaf k) :: xs, t) = revLink (xs, Node (k, (count t) + 1, t, Nil)) | revLink (Node (k, c, Nil, r) :: xs, t) = revLink (xs, Node (k, c, t, r)) | revLink (Node (k, c, l, Nil) :: xs, t) = revLink (xs, Node (k, c, l, t)) | revLink (_ :: xs, t) = raise Err fun insert (t, x) = let fun loop (acc, Nil, x) = revLink (acc, Leaf x) | loop (acc, Leaf k, l) = if l >= k then revLink (acc, Node (l, 2, Leaf k, Nil)) else revLink (acc, Node (k, 2, Leaf l, Nil)) | loop (acc, Node (k, _, Leaf l, Nil), r) = if r >= k then revLink (acc, Node (r, 3, Leaf k, Leaf l)) else if r >= l then revLink (acc, Node (k, 3, Leaf r, Leaf l)) else revLink (acc, Node (k, 3, Leaf l, Leaf r)) | loop (acc, Node (k, c, l, r), x) = let val (k, x) = if k >= x then (k, x) else (x, k) in if (count l) <= (count r) then loop (Node (k, c + 1, Nil, r) :: acc, l, x) else if x >= (key l) then loop (Node (k, c + 1, Nil, l) :: acc, r, x) else loop (Node (k, c + 1, l, Nil) :: acc, r, x) end in loop ([], t, x) end fun extract t = let fun loop (acc, Nil) = revLink (acc, Nil) | loop (acc, Leaf _) = revLink (acc, Nil) | loop (acc, Node (_, _, l, Nil)) = revLink (acc, l) | loop (acc, Node (_, c, l, r)) = let val k = key l val n = left l in if n = Nil then revLink (acc, Node (k, c - 1, r, Nil)) else if (key n) >= (key r) then loop (Node (k, c - 1, Nil, r) :: acc, l) else loop (Node (k, c - 1, r, Nil) :: acc, l) end in loop ([], t) end
- ^ 堆排序算法的二元樹實現中,堆建造函數也可以主要採用
siftdown
函數來完成,這裡不需要在節點中保存關於樹狀態的統計信息:fun heapSort l = let datatype 'a heap = Nil | Node of 'a * 'a heap * 'a heap fun key Nil = let val SOME a = Int.minInt in a end | key (Node (k, _, _)) = k fun left Nil = Nil | left (Node (_, l, _)) = l fun right Nil = Nil | right (Node (_, _, r)) = r fun leaf k = Node (k, Nil, Nil) fun sift (l, r) = if l <> Nil andalso r <> Nil then if (key l) >= (key r) then l else r else if l <> Nil then l else if r <> Nil then r else Nil fun siftdown (x, l, r) = let val superior = sift (l, r) in if superior = Nil then Node (x, Nil, Nil) else if x >= (key superior) then Node (x, l, r) else if superior = l then Node (key l, siftdown (x, left l, right l), r) else Node (key r, l, siftdown (x, left r, right r)) end fun insert (Nil, x) = Node (x, Nil, Nil) | insert (Node (k, l, r), x) = let val superior = sift (l, r) in if x >= k andalso superior = l then Node (x, l, insert (r, k)) else if x >= k then Node (x, insert (l, k), r) else if superior = l then Node (k, l, insert (r, x)) else Node (k, insert (l, x), r) end fun extract Nil = Nil | extract (Node (_, l, r)) = let val superior = sift (l, r) in if superior = Nil then Nil else if superior = l then Node (key l, extract l, r) else Node (key r, l, extract r) end fun join (l, r) = extract (Node (key Nil, l, r)) fun heapify () = let fun init (hs, ls, [], _) = (hs, ls) | init (hs, ls, x :: xs, flag) = if flag then init ((leaf x) :: hs, ls, xs, false) else init (hs, x :: ls, xs, true) val (hs, ls) = init ([], [], l, true) fun loop ([], [], []) = Nil | loop ([], [h], []) = h | loop ([], [], x :: xs) = loop ([], [leaf x], xs) | loop ([], [h], x :: xs) = loop ([], [insert (h, x)], xs) | loop (acc, [], l) = loop ([], acc, l) | loop (acc, [h], l) = loop ([], h :: acc, l) | loop (acc, l :: r :: hs, []) = loop (join (l, r) :: acc, hs, []) | loop (acc, l :: r :: hs, x :: xs) = loop (siftdown (x, l, r) :: acc, hs, xs) in loop ([], hs, ls) end fun generate h = let fun loop (acc, Nil) = acc | loop (acc, h) = loop ((key h) :: acc, extract h) in loop ([], h) end in generate (heapify ()) end
稍加處理,堆建造函數也可以只用
siftdown
函數來完成:fun heapify () = let exception Err; fun split () = let val (rs, ts) = let fun loop (acci, accj, [], i, n) = if i = n then (List.revAppend (accj, acci), []) else (acci, accj) | loop (acci, accj, x :: xs, i, n) = if i = n then loop (List.revAppend (accj, acci), [x], xs, i + 1, n * 2 + 1) else loop (acci, x :: accj, xs, i + 1, n) in loop ([], [], l, 0, 1) end fun loop (hs, ls, [], _) = (hs, ls, ts) | loop (hs, ls, x :: xs, flag) = if flag then loop (x :: hs, ls, xs, false) else loop (hs, x :: ls, xs, true) in loop ([], [], rs, true) end fun init () = let val (hs, ls, ts) = split () fun loop (acc, [], []) = (acc, ls) | loop (acc, [], ts) = (acc, List.revAppend (ts, ls)) | loop (acc, k :: hs, []) = loop ((leaf k) :: acc, hs, []) | loop (acc, k :: hs, [x]) = let val (k, x) = if k >= x then (k, x) else (x, k) in loop (Node (k, leaf x, Nil) :: acc, hs, []) end | loop (acc, k :: hs, l :: r :: rs) = let val (k, l, r) = if k >= l then if l >= r then (k, l, r) else if k >= r then (k, r, l) else (r, k, l) else if k >= r then (l, k, r) else if l >= r then (l, r, k) else (r, l, k) in loop (Node (k, leaf l, leaf r) :: acc, hs, rs) end in loop ([], hs, ts) end val (hs, ls) = init () fun loop ([], [], []) = Nil | loop ([], [h], []) = h | loop ([], [], _) = raise Err | loop ([], [h], _) = raise Err | loop (acc, [], l) = loop ([], acc, l) | loop (acc, [h], l) = loop ([], h :: acc, l) | loop (acc, l :: r :: hs, []) = raise Err | loop (acc, l :: r :: hs, x :: xs) = loop (siftdown (x, l, r) :: acc, hs, xs) in loop ([], hs, ls) end
- ^ 排序算法的簡單測試代碼:
fun printIntList (l: int list) = print ((String.concatWith " " (map Int.toString l)) ^ "\n") fun shuffle (l, n) = let fun split (l, acc, i) = if i = 0 then (acc, l) else split (tl l, (hd l) :: acc, i - 1) fun zip (acc, p, q, flag) = if null p then List.revAppend (q, acc) else if null q then List.revAppend (p, acc) else if flag then zip ((hd p) :: acc, tl p, q, false) else zip ((hd q) :: acc, p, tl q, true) val (p, q) = split (l, [], n div 2) in if (null l) then tl [0] else zip ([], p, q, true) end fun testsort f n = let fun loop (acc, i) = if (i <= 0) then acc else loop (i :: acc, i - 1) val sl = shuffle (loop ([], n), n) val ssl = shuffle (sl, n) in print ("source list is: "); printIntList ssl; print ("result list is: "); printIntList (f ssl) end
參見
- Standard ML和它的實現:
- SML/NJ,由普林斯頓大學和貝爾實驗室聯合開發的實現,它具有並發編程擴展Concurrent ML。
- MLton,嚴格遵循標準定義的強力的全程序優化編譯器[50]。
- HaMLet[51],由馬克斯·普朗克軟體系統研究所(MPI-SWS)的Andreas Rossberg編寫,是一個SML解釋器,意圖成為精確且合宜接近的標準定義參考實現。
- OCaml,由法國國家信息與自動化研究所(INRIA)維護,是一個「工業強度」的ML方言[52],演化自最初用來實現Coq定理證明器的Caml[17]。
- Alice,由薩爾蘭大學設計的Alice ML,是基於Standard ML的函數式程式語言,擴展了對並發、分布式和約束式編程的豐富支持[53]。
- ATS,由波士頓大學的Hongwei Xi和卡內基·梅隆大學的Frank Pfenning提出的Dependent ML發展而來,它向ML擴展了依賴類型。
- F#,由微軟研究院(MSR)開發,是一個基於OCaml的一個以.NET為目標的程式語言。
- F*,由MSR和INRIA主導開發,是一個基於ML的依賴類型函數式程式語言。
- Futhark,由哥本哈根大學計算機科學系(DIKU)開發,是屬於ML家族的一個函數式、數據並行、陣列程式語言[4]。
- Ur,由麻省理工學院的Adam Chlipala開發,是語法基於Standard ML的專門用於web開發的一個函數式程式語言[7]。
- CM-Lex和CM-Yacc,由卡內基·梅隆大學的Karl Crary開發,是用於Standard ML、OCaml和Haskell的詞法分析器和語法解析器[54]。
- Amulet,是一個類ML的函數式程式語言,其編譯器輸出Lua文件[55]。
- Alpaca,是一個受ML啟發的運行在Erlang虛擬機上的函數式程式語言[56]。
延伸閱讀
- Robin Milner, Mads Tofte, Robert Harper. The Definition of Standard ML (PDF). MIT Press. 1990 [2021-03-01]. (原始內容 (PDF)存檔於2021-01-14).
- Robin Milner, Mads Tofte, Robert Harper, David MacQueen. The Definition of Standard ML, Revised (PDF). MIT Press. 1997 [2021-03-01]. ISBN 0-262-63181-4. (原始內容 (PDF)存檔於2022-03-09).
- Robin Milner, Mads Tofte. Commentary on Standard ML. MIT Press. 1991 [2021-08-31]. ISBN 978-0-262-63137-2. (原始內容存檔於2021-08-31).
- Emden R. Gansner, John H. Reppy. The Standard ML Basis Library (PDF). Cambridge University Press. 2004 [2021-09-17]. (原始內容 (PDF)存檔於2022-01-29).
- Mads Tofte. Four Lectures on Standard ML (PDF). University of Edinburgh. 1989 [2021-09-04]. (原始內容 (PDF)存檔於2022-01-28). Code examples in lectures. [2021-09-11]. 原始內容存檔於2016-04-02.
- Mads Tofte. Essentials of Standard ML Modules. DIKU. 1996 [2021-09-04]. (原始內容存檔於2021-09-04). The SML code (uuencoded compressed tar). [2021-09-18]. 原始內容存檔於2005-03-07.
- Mads Tofte. Tips for Computer Scientists on Standard ML (Revised) (PDF). ITU. 2009 [2021-09-04]. (原始內容 (PDF)存檔於2021-11-27). Examples. [2022-01-03]. 原始內容存檔於2017-09-15.
- Robert Harper. Programming in Standard ML (PDF). Carnegie Mellon University. 2011 [2021-02-27]. (原始內容 (PDF)存檔於2020-02-15). Examples. [2021-09-12]. (原始內容存檔於2021-09-12).
- Michael J. C. Gordon. Introduction to Functional Programming. Cambridge University. 1996 [2021-09-11]. (原始內容存檔於2021-04-11). Lecture notes. [2021-09-11]. (原始內容存檔於2006-06-23).
- Lawrence Paulson. ML for the Working Programmer, 2nd Edition. Cambridge University Press. 1996 [2021-08-31]. ISBN 0-521-56543-X. (原始內容存檔於2022-02-24). Sample programs. [2021-09-12]. (原始內容存檔於2022-01-19).
- David MacQueen. Should ML be Object-Oriented? (PDF). 2002 [2021-09-10]. (原始內容 (PDF)存檔於2021-10-29).
- David MacQueen, Robert Harper, John Reppy. The History of Standard ML. 2020 [2021-08-31]. (原始內容存檔於2021-12-01).
- Andrew W. Appel. Compiling with Continuations. Cambridge University Press. 1992 [2022-01-03]. (原始內容存檔於2022-01-03).
- Andrew W. Appel. Modern Compiler Implementation in ML. Cambridge University Press. 1998 [2022-01-12]. (原始內容存檔於2022-01-12). Tiger compiler modules for programming exercises. [2021-09-12]. (原始內容存檔於2022-05-06).
- Jeffrey D. Ullman. Elements of ML Programming, ML97 Edition. Prentice-Hall. 1998 [2021-12-30]. ISBN 0-13-790387-1. (原始內容存檔於2022-03-12). Programs from the text. [2022-01-01]. (原始內容存檔於2022-02-14).
- Anthony L. Shipman. Unix System Programming with Standard ML (PDF). 2001 [2021-09-01]. (原始內容 (PDF)存檔於2021-01-21).
引用
- ^ 1.0 1.1 1.2 1.3 Michael J. Gordon, Arthur J. Milner, Christopher P. Wadsworth. Edinburgh LCF: A Mechanised Logic of Computation. Lecture Notes in Computer Science, Vol. 78. Springer-Verlag, New York, NY, USA. 1979 [2021-12-28]. (原始內容存檔於2021-12-28).
ML is a general purpose programming language. It is derived in different aspects from ISWIM, POP2 and GEDANKEN, and contains perhaps two new features. First, it has an escape and escape trapping mechanism, well-adapted to programming strategies which may be (in fact usually are) inapplicable to certain goals. Second, it has a polymorphic type discipline which combines the flexibility of programming in a typeless language with the security of compile-time type checking (as in other languages, you may also define your own types, which may be abstract and/or recursive); this is what ensures that a well-typed program cannot perform faulty proofs.
Michael J. C. Gordon. From LCF to HOL: a short history. 1996 [2021-02-27]. (原始內容存檔於2016-09-05).Around 1973 Milner moved to Edinburgh University and established a project to build a successor to Stanford LCF, which was subsequently dubbed Edinburgh LCF. He initially hired Lockwood Morris and Malcolm Newey (both recent PhD graduates from Stanford) as research assistants. …… Milner, ably assisted by Morris and Newey, designed the programming language ML (an abbreviation for 「Meta Language」). …… In 1975, Morris and Newey took up faculty positions at Syracuse University and the Australian National University, respectively, and were replaced by Chris Wadsworth and myself. The design and implementation of ML and Edinburgh LCF was finalised and the book 「Edinburgh LCF」 was written and published. In 1978, the first LCF project finished, Chris Wadsworth went off trekking in the Andes (returning to a permanent position at the Rutherford Appleton Laboratory) and I remained at Edinburgh supported by a postdoctoral fellowship and with a new research interest: hardware verification.
- ^ 2.0 2.1 M. Gordon, R. Milner, L. Morris, M. Newey, C. Wadsworth. A Metalanguage for Interactive Proof in LCF (PDF). 1978 [2021-08-31]. (原始內容 (PDF)存檔於2021-05-06).
ML is a higher-order functional programming language in the tradition of ISWIM, PAL, POP2 and GEDANKEN, but differs principally in its handling of failure and, more so, of types.
- ^ 3.0 3.1 Bruce A. Tate, Fred Daoud, Ian Dees, Jack Moffitt. 3. Elm. Seven More Languages in Seven Weeks (PDF) Book version: P1.0-November 2014. The Pragmatic Programmers, LLC. 2014: 97, 101 [2021-09-04]. ISBN 978-1-941222-15-7. (原始內容 (PDF)存檔於2021-03-15).
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#.]
- ^ 4.0 4.1 Troels Henriksen, Niels G. W. Serup, Martin Elsman, Fritz Henglein, Cosmin Oancea. Futhark: Purely Functional GPU-Programming with Nested Parallelism and In-Place Array Updates (PDF). Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI 2017. ACM. 2017 [2021-09-04]. (原始內容 (PDF)存檔於2020-09-20).
- ^ Lennart Augustsson, Thomas Johnsson. The Chalmers Lazy-ML Compiler. 1989 [2021-09-17]. (原始內容存檔於2021-09-17).
- ^ 6.0 6.1 Programming language for "special forces" of developers., Russian Software Development Network: Nemerle Project Team, [January 24, 2021], (原始內容存檔於2021-05-04)
- ^ 7.0 7.1 Adam Chlipala. Ur/Web: A Simple Model for Programming the Web (PDF). MIT / Association for Computing Machinery (ACM). January 2015 [2021-09-04]. (原始內容 (PDF)存檔於2022-01-16).
- ^ 8.0 8.1 Robin Milner. A theory of type polymorphism in programming. (PDF). 1978 [2021-09-01]. (原始內容 (PDF)存檔於2020-11-01). Journal of Computer and System Sciences, 17(3):348–375.
- ^ Robin Milner. How ML Evolved (PDF). Polymorphism—The ML/LCF/Hope Newsletter,Vol. 1, No. 1. 1982 [2021-09-09]. (原始內容 (PDF)存檔於2022-01-28).
- ^ The original Edinburgh LCF. 1977 [2021-10-10]. (原始內容存檔於2021-10-10).
- ^ Luca Cardelli. ML under VMS (PDF). 1982 [2021-09-04]. (原始內容 (PDF)存檔於2021-11-06).
- ^ Luca Cardelli. Differences between VAX and DEC-10 ML (PDF). 1982 [2021-09-04]. (原始內容 (PDF)存檔於2021-11-06).
- ^ Luca Cardelli. The Functional Abstract Machine. 1983 [2021-09-04]. (原始內容存檔於2021-09-04). Bell Labs Technical Report TR-107.
Luca Cardelli. Compiling a functional language. 1984 [2021-09-03]. (原始內容存檔於2021-09-03). In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming, pages 208–217, New York, NY, USA. ACM. - ^ Kevin Mitchell, Alan Mycroft. The Edinburgh Standard ML Compiler (PDF). 1985 [2021-09-10]. (原始內容 (PDF)存檔於2022-01-29).
- ^ 15.0 15.1 Guy Cousineau, Gérard Huet. The CAML primer Version 2.6.1. 1990 [2021-09-02]. (原始內容存檔於2022-05-04). RT-0122, INRIA. pp.78.
Pierre Weis, Maria Virginia Aponte, Alain Laville, Michel Mauny, Ascander Suarez. The CAML reference manual Version 2.6.1. 1990 [2021-09-02]. (原始內容存檔於2022-04-06). [Research Report] RT-0121, INRIA. pp.491. - ^ G. Cousineau, M. Gordon, G. Huet, R. Milner, L. C. Paulson, C. Wadsworth. The ML Handbook, Version 6.2. Internal document. Project Formel, INRIA. July 1985.
Christoph Kreitz, Vincent Rahli. Introduction to Classic ML (PDF). 2011 [2021-09-09]. (原始內容 (PDF)存檔於2022-01-29).This handbook is a revised edition of Section 2 of 『Edinburgh LCF』, by M. Gordon, R. Milner, and C. Wadsworth, published in 1979 as Springer Verlag Lecture Notes in Computer Science no 78. ……The language is somewhere in between the original ML from LCF and standard ML, since Guy Cousineau added the constructors and call by patterns. This is a LISP based implementation, compatible for Maclisp on Multics, Franzlisp on VAX under Unix, Zetalisp on Symbolics 3600, and Le Lisp on 68000, VAX, Multics, Perkin-Elmer, etc... Video interfaces have been implemented by Philippe Le Chenadec on Multics, and by Maurice Migeon on Symbolics 3600. The ML system is maintained and distributed jointly by INRIA and the University of Cambridge.
- ^ 17.0 17.1 A History of Caml. [2021-08-31]. (原始內容存檔於2022-04-13).
The Formel team became interested in the ML language in 1980-81. ……Gérard Huet decided to make the ML implementation compatible with various Lisp compilers (MacLisp, FranzLisp, LeLisp, ZetaLisp). This work involved Guy Cousineau and Larry Paulson. ……Guy Cousineau also added algebraic data types and pattern-matching, following ideas from Robin Milner ……. At some point, this implementation was called Le_ML, a name that did not survive. It was used by Larry Paulson to develop Cambridge LCF and by Mike Gordon for the first version of HOL ……. ……
Our main reason for developing Caml was to use it for sofware development inside Formel. Indeed, it was used for developing the Coq system ……. We were reluctant to adopt a standard that could later prevent us from adapting the language to our programming needs. ……We did incorporate into Caml most of the improvements brought by Standard ML over Edinburgh ML. ……The first implementation of Caml appeared in 1987 and was further developed until 1992. It was created mainly by Ascander Suarez. ……
In 1990 and 1991, Xavier Leroy designed a completely new implementation of Caml, based on a bytecode interpreter written in C. Damien Doligez provided an excellent memory management system. ……In 1995, Xavier Leroy released Caml Special Light, which improved over Caml Light in several ways. In 1995, Xavier Leroy released Caml Special Light, which improved over Caml Light in several ways. First, an optimizing native-code compiler was added to the bytecode compiler. ……Second, Caml Special Light offered a high-level module system, designed by Xavier Leroy and inspired by the module system of Standard ML. ……Didier Rémy, later joined by Jérôme Vouillon, designed an elegant and highly expressive type system for objects and classes. This design was integrated and implemented within Caml Special Light, leading to the Objective Caml language and implementation, first released in 1996 and renamed to OCaml in 2011. - ^ Lawrence C. Paulson. The theorem prover Cambridge LCF. coded in Franz Lisp. 1989 [2021-10-10]. (原始內容存檔於2021-10-10).
Michael J. C. Gordon. From LCF to HOL: a short history. 1996 [2021-02-27]. (原始內容存檔於2016-09-05).In 1981, I moved to a permanent position as Lecturer at the University of Cambridge Computer Laboratory. ……Larry Paulson, recently graduated with a PhD from Stanford, was hired at Cambridge ……. About this time, and in parallel, G ́erard Huet ported the Edinburgh LCF code to Lelisp and MacLisp. Paulson and Huet then established a collaboration and did a lot of joint development of LCF by sending each other magnetic tapes in the post. …… Edinburgh LCF ran interpretively, but during Paulson and Huet’s collaboration an ML compiler was implemented that provided a speedup by a factor of about twenty. …… The resulting new LCF system was named 「Cambridge LCF」 and completed around 1985. Paulson did little work on it after that. Mikael Hedlund (of the Rutherford Appleton Laboratory) then ported Cambridge LCF to Standard ML (using a new implementation of ML that he created). The resulting Standard ML based version of Cambridge LCF is documented …… in Paulson’s 1987 book Logic and Computation.
- ^ HOL88, source code.
Michael J. C. Gordon. From LCF to HOL: a short history. 1996 [2021-02-27]. (原始內容存檔於2016-09-05).Whilst Paulson was designing and implementing Cambridge LCF, I was mainly concerned with hardware verification. …… The first version of the HOL system was created by modifying the Cambridge LCF parser and pretty-printer to support higher order logic concrete syntax. …… The core HOL system became stable in about 1988. A new release that consolidated various changes and enhancements called HOL88 was issued then. We were fortunate to receive support from DSTO Australia to document HOL and from Hewlett Packard to port it from Franz Lisp to Common Lisp (a job very ably done by John Carroll). …… In the late 1980’s Graham Birtwistle of the University of Calgary started a project to reimplement HOL in Standard ML. The work was done by Konrad Slind, under Birtwistle’s direction and with the collaboration of the HOL group at Cambridge. The resulting system, called HOL90, was first released around 1990. …… Recently John Harrison and Konrad Slind have entirely reworked the design of HOL ……. …… This new version of HOL is called 「HOL Light」. It is implemented in Caml Light and runs on modest platforms (e.g. standard PCs). It is faster than the Lisp-based HOL88, but a bit slower than HOL90 running in modern implementations of Standard ML.
- ^ Robin Milner. A Proposal for Standard ML (PDF). 1983 [2021-09-02]. (原始內容 (PDF)存檔於2021-11-06).
- ^ R. M. Burstall, J. A. Goguen. The semantics of CLEAR, a specification language. 1977 [2021-09-03]. (原始內容存檔於2021-09-03).
Donald Sannella. Semantics, Implementation and Pragmatics of Clear, a Program Specification Language. 1982 [2021-09-06]. (原始內容存檔於2021-09-06). - ^ Rod Burstall, D.B. MacQueen, D.T. Sannella. Hope: An Experimental Applicative Language (PDF). 1980 [2021-09-03]. (原始內容 (PDF)存檔於2022-01-28). Conference Record of the 1980 LISP Conference, Stanford University, pp. 136-143.
- ^ R.M. Burstall. Proving properties of programs by structural induction (PDF). 1968 [2021-09-13]. (原始內容 (PDF)存檔於2022-01-28).
- ^ R.M. Burstall, J. Darlington. A transformation system for developing recursive programs. Journal of the Association for Computing Machinery: 24(1):44–67. 1977 [2021-09-13]. (原始內容存檔於2020-01-28).
- ^ Luca Cardelli. ML under Unix (PDF). 1983 [2021-09-10]. (原始內容 (PDF)存檔於2022-01-28).
Luca Cardelli. ML under Unix, Pose 4 (PDF). 1984 [2021-09-04]. (原始內容 (PDF)存檔於2022-01-28). - ^ David MacQueen. Modules for Standard ML. LFP '84 Proceedings of the 1984 ACM Symposium on LISP and functional programming. August 1984: 198–207 [2021-06-23]. (原始內容存檔於2021-05-02).
- ^ *Robin Milner. The Standard ML Core Language (PDF). July 1984 [2021-09-05]. (原始內容 (PDF)存檔於2021-11-06).
- Robin Milner. The Standard ML Core Language (PDF). October 1984 [2021-09-05]. (原始內容 (PDF)存檔於2021-11-06).
- Robin Milner. The Standard ML Core Language (Revised) (PDF). 1985 [2021-09-05]. (原始內容 (PDF)存檔於2021-11-06).
- Robert Harper, David B. MacQueen, Robin Milner. Standard ML. Technical Report ECS-LFCS-86-2 (PDF). 1986 [2021-09-04]. (原始內容 (PDF)存檔於2022-01-28). LFCS, Department of Computer Science, University of Edinburgh.
- Robin Milner. Changes to the Standard ML Core language. Technical Report ECS-LFCS-87-33 (PDF). 1987 [2021-09-04]. (原始內容 (PDF)存檔於2021-09-04). LFCS, Department of Computer Science, University of Edinburgh.
- Robert Harper, Robin Milner, Mads Tofte. The Semantics of Standard ML, Version 1. Technical Report ECS-LFCS-87-36 (PDF). 1987 [2021-09-04]. (原始內容 (PDF)存檔於2022-01-28). LFCS, Department of Computer Science, University of Edinburgh.
- Robert Harper, Robin Milner, Mads Tofte. The Definition of Standard ML, Version 2. Technical Report ECS-LFCS-88-62 (PDF). 1988 [2021-09-04]. (原始內容 (PDF)存檔於2022-01-28). LFCS, Department of Computer Science, University of Edinburgh.
- Robert Harper, Robin Milner, Mads Tofte. The Definition of Standard ML, Version 3. Technical Report ECS-LFCS-89-81 (PDF). 1989 [2021-09-04]. (原始內容 (PDF)存檔於2022-01-28). LFCS, Department of Computer Science, University of Edinburgh.
- ^ Edinburgh ML (Core Language) (SML '90), Version 4.1.02. 1991 [2021-09-13]. (原始內容存檔於2021-09-13).
The Edinburgh Standard ML Library (SML '90). 1993 [2021-09-13]. (原始內容存檔於2020-08-12). - ^ Andrew W. Appel, David MacQueen. A Standard ML compiler. 1987 [2021-09-03]. (原始內容存檔於2021-09-03).
David Macueen. An Implementation of Standard ML Modules. 1988 [2021-09-03]. (原始內容存檔於2021-09-03). - ^ Andrew W. Appel, David MacQueen. Standard ML of New Jersey. 1991 [2021-08-31]. (原始內容存檔於2021-08-31).
Standard ML of New Jersey, Version 0.93. 1993 [2021-09-14]. (原始內容存檔於2022-03-28). - ^ Robin Milner, Mads Tofte, Robert Harper. The Definition of Standard ML (PDF). The MIT Press, Cambridge, MA, USA. 1990 [2021-03-01]. (原始內容 (PDF)存檔於2021-01-14).
- ^ Robin Milner, Mads Tofte, Robert Harper, David MacQueen. The Definition of Standard ML (Revised) (PDF). The MIT Press, Cambridge, MA, USA. 1997 [2021-03-01]. (原始內容 (PDF)存檔於2022-03-09).
- ^ Lars Birkedal, Nick Rothwell, Mads Tofte, David N. Turner. The ML Kit, Version 1. 1993 [2021-09-13]. (原始內容存檔於2021-09-13).
- ^ The release of the ML Kit Version 1. 1993 [2021-09-13]. (原始內容存檔於2021-09-13).
- ^ G. Cousineau, P.-L. Curien, M. Mauny. The categorical abstract machine. 1985 [2021-09-04]. (原始內容存檔於2021-09-03). LNCS, 201, Functional programming languages computer architecture, pp.~50-64.
Michel Mauny, Ascánder Suárez. Implementing functional languages in the Categorical Abstract Machine (PDF). 1986 [2021-09-04]. (原始內容 (PDF)存檔於2022-01-28). LFP '86: Proceedings of the 1986 ACM conference on LISP and functional programming, Pages 266–278. - ^ Xavier Leroy. The ZINC experiment : an economical implementation of the ML language. 1990 [2021-09-06]. (原始內容存檔於2022-04-06). RT-0117, INRIA.
- ^ Xavier Leroy. The Caml Light system Release 0.74, documentation and user's guide. 1997 [2021-09-02]. (原始內容存檔於2022-03-08).
- ^ Xavier Leroy. Manifest types, modules, and separate compilation (PDF). Principles of Programming Languages. 1994 [2021-09-07]. (原始內容 (PDF)存檔於2021-10-22).
- ^ Didier Rémy. Type inference for records in a natural extension of ML. Research Report RR-1431, INRIA. 1991 [2021-09-10]. (原始內容存檔於2022-04-06).
Didier Rémy, Jérôme Vouillon. Objective ML: a simple object-oriented extension of ML (PDF). 1997 [2021-09-06]. (原始內容 (PDF)存檔於2022-01-21).
Didier Rémy, Jérôme Vouillon. Objective ML: An effective object-oriented extension to ML (PDF). 1998 [2021-09-06]. (原始內容 (PDF)存檔於2022-01-20). - ^ Xavier Leroy. The Objective Caml system release 1.07, Documentation and user's manual. 1997 [2021-09-02]. (原始內容存檔於2022-01-23).
- ^ Samuel Horsley F. R. S. Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers. Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347. 1772 [2021-09-13]. (原始內容存檔於2018-10-02).
- ^ Edsger W. Dijkstra, 17. An exercise attributed to R. W. Hamming, A Discipline of Programming, Prentice-Hall: 129–134, 1976, ISBN 978-0132158718
Edsger W. Dijkstra, Hamming's exercise in SASL (PDF), 1981 [2021-05-19], Report EWD792. Originally a privately circulated handwritten note, (原始內容 (PDF)存檔於2019-04-04). - ^ David Turner. Lazy evaluation and infinite lists. An Overview of Miranda. Computing Laboratory, University of Kent. 1986 [2021-09-16]. (原始內容存檔於2021-12-23).
CS3110. Streams and Laziness. Cornell University. 2018 [2021-09-16]. (原始內容存檔於2022-03-03). - ^ Gerald J. Sussman, Guy L. Steele Jr.
Scheme: An Interpreter for Extended Lambda Calculus. 維基文庫. 1975 (英文).
It is always possible, ……to perform any calculation in this way: rather than reducing to its value, it reduces to an application of a continuation to its value (cf. [Fischer]). That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function.
- ^ CS312. Continuations. Cornell University. 2006 [2021-10-11]. (原始內容存檔於2021-10-28).
CS3110. Continuations and CPS Conversion. Cornell University. 2014 [2021-10-11]. (原始內容存檔於2018-02-15). - ^ Bruce Duba, Robert Harper, David MacQueen. Typing first-class continuations in ML (PDF). 1991 [2021-10-14]. (原始內容 (PDF)存檔於2022-01-29).
- ^ Tokuda, Naoyuki. An Improved Shellsort. van Leeuven, Jan (編). Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture. Amsterdam: North-Holland Publishing Co. 1992: 449–457. ISBN 978-0-444-89747-3.
- ^ Ciura, Marcin. Best Increments for the Average Case of Shellsort (PDF). Freiwalds, Rusins (編). Proceedings of the 13th International Symposium on Fundamentals of Computation Theory. London: Springer-Verlag. 2001: 106–117 [2021-10-06]. ISBN 978-3-540-42487-1. (原始內容 (PDF)存檔於2011-08-30).
- ^ W.H. Press, B.P. Flannery, S.A. Teukolsky, W.T. Vetterling. Numerical Recipes in C: The Art of Scientific Computing (PDF). Cambridge University Press. 1988, 1992 [2021-10-05]. (原始內容 (PDF)存檔於2022-03-23).
- ^ Stephen Weeks. Whole-Program Compilation in MLton (PDF). Workshop on ML. 2006 [2021-09-17]. (原始內容 (PDF)存檔於2022-01-24).
- ^ HaMLet. [2021-09-04]. (原始內容存檔於2016-10-14).
- ^ "OCaml is an industrial strength programming language supporting functional, imperative and object-oriented styles" (頁面存檔備份,存於網際網路檔案館). Retrieved on January 2, 2018.
- ^ Alice. [2021-09-04]. (原始內容存檔於2022-03-23).
- ^ Karl Crary. CM-Lex and CM-Yacc. Carnegie Mellon University. 2017 [2021-09-17]. (原始內容存檔於2022-01-20).
- ^ Amulet. amulet.works. [2021-01-12]. (原始內容存檔於2021-07-25).
- ^ Alpaca programming language community. [2021-10-14]. (原始內容存檔於2021-12-10).
外部連結
- Andreas Rossberg. Standard ML and Objective Caml, Side by Side. 2011 [2021-08-31]. (原始內容存檔於2021-12-30).
- Adam Chlipala. Comparing Objective Caml and Standard ML. 2020 [2021-08-31]. (原始內容存檔於2021-12-16).
- SML Help (頁面存檔備份,存於網際網路檔案館)
- cmlib (頁面存檔備份,存於網際網路檔案館)
|