-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path2.html
More file actions
executable file
·816 lines (723 loc) · 39.1 KB
/
Copy path2.html
File metadata and controls
executable file
·816 lines (723 loc) · 39.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="zh-CN" xml:lang="zh-CN">
<head>
<!-- 2018-12-05 Wed 13:01 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>programming-languages学习笔记–第2部分</title>
<meta name="generator" content="Org mode" />
<meta name="author" content="ntestoc" />
<meta name="description" content="测试通过Org-mode提交到cnblogs,本节学习创建自己的类型:定义新类型，构造新类型的值及使用这些值。 思考"复合类型(compound types)"。 使用模式匹配访问复合类型的值。 最后还有尾递归。"
/>
<meta name="keywords" content="programming, sml" />
<style type="text/css">
<!--/*--><![CDATA[/*><!--*/
.title { text-align: center;
margin-bottom: .2em; }
.subtitle { text-align: center;
font-size: medium;
font-weight: bold;
margin-top:0; }
.todo { font-family: monospace; color: red; }
.done { font-family: monospace; color: green; }
.priority { font-family: monospace; color: orange; }
.tag { background-color: #eee; font-family: monospace;
padding: 2px; font-size: 80%; font-weight: normal; }
.timestamp { color: #bebebe; }
.timestamp-kwd { color: #5f9ea0; }
.org-right { margin-left: auto; margin-right: 0px; text-align: right; }
.org-left { margin-left: 0px; margin-right: auto; text-align: left; }
.org-center { margin-left: auto; margin-right: auto; text-align: center; }
.underline { text-decoration: underline; }
#postamble p, #preamble p { font-size: 90%; margin: .2em; }
p.verse { margin-left: 3%; }
pre {
border: 1px solid #ccc;
box-shadow: 3px 3px 3px #eee;
padding: 8pt;
font-family: monospace;
overflow: auto;
margin: 1.2em;
}
pre.src {
position: relative;
overflow: visible;
padding-top: 1.2em;
}
pre.src:before {
display: none;
position: absolute;
background-color: white;
top: -10px;
right: 10px;
padding: 3px;
border: 1px solid black;
}
pre.src:hover:before { display: inline;}
/* Languages per Org manual */
pre.src-asymptote:before { content: 'Asymptote'; }
pre.src-awk:before { content: 'Awk'; }
pre.src-C:before { content: 'C'; }
/* pre.src-C++ doesn't work in CSS */
pre.src-clojure:before { content: 'Clojure'; }
pre.src-css:before { content: 'CSS'; }
pre.src-D:before { content: 'D'; }
pre.src-ditaa:before { content: 'ditaa'; }
pre.src-dot:before { content: 'Graphviz'; }
pre.src-calc:before { content: 'Emacs Calc'; }
pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
pre.src-fortran:before { content: 'Fortran'; }
pre.src-gnuplot:before { content: 'gnuplot'; }
pre.src-haskell:before { content: 'Haskell'; }
pre.src-hledger:before { content: 'hledger'; }
pre.src-java:before { content: 'Java'; }
pre.src-js:before { content: 'Javascript'; }
pre.src-latex:before { content: 'LaTeX'; }
pre.src-ledger:before { content: 'Ledger'; }
pre.src-lisp:before { content: 'Lisp'; }
pre.src-lilypond:before { content: 'Lilypond'; }
pre.src-lua:before { content: 'Lua'; }
pre.src-matlab:before { content: 'MATLAB'; }
pre.src-mscgen:before { content: 'Mscgen'; }
pre.src-ocaml:before { content: 'Objective Caml'; }
pre.src-octave:before { content: 'Octave'; }
pre.src-org:before { content: 'Org mode'; }
pre.src-oz:before { content: 'OZ'; }
pre.src-plantuml:before { content: 'Plantuml'; }
pre.src-processing:before { content: 'Processing.js'; }
pre.src-python:before { content: 'Python'; }
pre.src-R:before { content: 'R'; }
pre.src-ruby:before { content: 'Ruby'; }
pre.src-sass:before { content: 'Sass'; }
pre.src-scheme:before { content: 'Scheme'; }
pre.src-screen:before { content: 'Gnu Screen'; }
pre.src-sed:before { content: 'Sed'; }
pre.src-sh:before { content: 'shell'; }
pre.src-sql:before { content: 'SQL'; }
pre.src-sqlite:before { content: 'SQLite'; }
/* additional languages in org.el's org-babel-load-languages alist */
pre.src-forth:before { content: 'Forth'; }
pre.src-io:before { content: 'IO'; }
pre.src-J:before { content: 'J'; }
pre.src-makefile:before { content: 'Makefile'; }
pre.src-maxima:before { content: 'Maxima'; }
pre.src-perl:before { content: 'Perl'; }
pre.src-picolisp:before { content: 'Pico Lisp'; }
pre.src-scala:before { content: 'Scala'; }
pre.src-shell:before { content: 'Shell Script'; }
pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
/* additional language identifiers per "defun org-babel-execute"
in ob-*.el */
pre.src-cpp:before { content: 'C++'; }
pre.src-abc:before { content: 'ABC'; }
pre.src-coq:before { content: 'Coq'; }
pre.src-groovy:before { content: 'Groovy'; }
/* additional language identifiers from org-babel-shell-names in
ob-shell.el: ob-shell is the only babel language using a lambda to put
the execution function name together. */
pre.src-bash:before { content: 'bash'; }
pre.src-csh:before { content: 'csh'; }
pre.src-ash:before { content: 'ash'; }
pre.src-dash:before { content: 'dash'; }
pre.src-ksh:before { content: 'ksh'; }
pre.src-mksh:before { content: 'mksh'; }
pre.src-posh:before { content: 'posh'; }
/* Additional Emacs modes also supported by the LaTeX listings package */
pre.src-ada:before { content: 'Ada'; }
pre.src-asm:before { content: 'Assembler'; }
pre.src-caml:before { content: 'Caml'; }
pre.src-delphi:before { content: 'Delphi'; }
pre.src-html:before { content: 'HTML'; }
pre.src-idl:before { content: 'IDL'; }
pre.src-mercury:before { content: 'Mercury'; }
pre.src-metapost:before { content: 'MetaPost'; }
pre.src-modula-2:before { content: 'Modula-2'; }
pre.src-pascal:before { content: 'Pascal'; }
pre.src-ps:before { content: 'PostScript'; }
pre.src-prolog:before { content: 'Prolog'; }
pre.src-simula:before { content: 'Simula'; }
pre.src-tcl:before { content: 'tcl'; }
pre.src-tex:before { content: 'TeX'; }
pre.src-plain-tex:before { content: 'Plain TeX'; }
pre.src-verilog:before { content: 'Verilog'; }
pre.src-vhdl:before { content: 'VHDL'; }
pre.src-xml:before { content: 'XML'; }
pre.src-nxml:before { content: 'XML'; }
/* add a generic configuration mode; LaTeX export needs an additional
(add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
pre.src-conf:before { content: 'Configuration File'; }
table { border-collapse:collapse; }
caption.t-above { caption-side: top; }
caption.t-bottom { caption-side: bottom; }
td, th { vertical-align:top; }
th.org-right { text-align: center; }
th.org-left { text-align: center; }
th.org-center { text-align: center; }
td.org-right { text-align: right; }
td.org-left { text-align: left; }
td.org-center { text-align: center; }
dt { font-weight: bold; }
.footpara { display: inline; }
.footdef { margin-bottom: 1em; }
.figure { padding: 1em; }
.figure p { text-align: center; }
.inlinetask {
padding: 10px;
border: 2px solid gray;
margin: 10px;
background: #ffffcc;
}
#org-div-home-and-up
{ text-align: right; font-size: 70%; white-space: nowrap; }
textarea { overflow-x: auto; }
.linenr { font-size: smaller }
.code-highlighted { background-color: #ffff00; }
.org-info-js_info-navigation { border-style: none; }
#org-info-js_console-label
{ font-size: 10px; font-weight: bold; white-space: nowrap; }
.org-info-js_search-highlight
{ background-color: #ffff00; color: #000000; font-weight: bold; }
.org-svg { width: 90%; }
/*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart The following is the entire license notice for the
JavaScript code in this tag.
Copyright (C) 2012-2018 Free Software Foundation, Inc.
The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version. The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU GPL for more details.
As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.
@licend The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
function CodeHighlightOn(elem, id)
{
var target = document.getElementById(id);
if(null != target) {
elem.cacheClassElem = elem.className;
elem.cacheClassTarget = target.className;
target.className = "code-highlighted";
elem.className = "code-highlighted";
}
}
function CodeHighlightOff(elem, id)
{
var target = document.getElementById(id);
if(elem.cacheClassElem)
elem.className = elem.cacheClassElem;
if(elem.cacheClassTarget)
target.className = elem.cacheClassTarget;
}
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<h1 class="title">programming-languages学习笔记–第2部分</h1>
<div id="table-of-contents">
<h2>目录</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#org67ea651">1. 自定义类型</a></li>
<li><a href="#orgaf3dd37">2. Records</a></li>
<li><a href="#org01c7244">3. tuples as syntactic sugar</a></li>
<li><a href="#orga02e7db">4. datatype bindings</a></li>
<li><a href="#orgb8cf071">5. case 表达式</a></li>
<li><a href="#orgb216fdd">6. 类型同义词</a></li>
<li><a href="#orgfc7e20b">7. Lists和Options也是datatype</a></li>
<li><a href="#org0f768ea">8. 多态数据类型</a></li>
<li><a href="#org46eda57">9. Each-of类型的模式匹配:val绑定的真相</a></li>
<li><a href="#orgc626028">10. 类型推断,多态类型与相等类型</a></li>
<li><a href="#org3190ed9">11. 嵌套模式</a></li>
<li><a href="#org9c5f5b6">12. 异常</a></li>
<li><a href="#org2839301">13. 尾递归和累加器</a></li>
</ul>
</div>
</div>
<div id="outline-container-org67ea651" class="outline-2">
<h2 id="org67ea651"><span class="section-number-2">1</span> 自定义类型</h2>
<div class="outline-text-2" id="text-1">
<ul class="org-ul">
<li>基本类型 (int bool unit char)</li>
<li>复合类型 (tuples, lists, options)</li>
</ul>
<p>
构造复合类型:
</p>
<ul class="org-ul">
<li>each of: 组合所有 例如:tuples, (int * bool) 包含一个int和一个bool, 与java中带的字段类相似</li>
<li>one of: 选择一个 例如:option, int option可以包含一个int或者空，java中可以通过子类化实现。</li>
<li>self reference: 自引用类型，用于构造递归数据类型，例如列表和树</li>
</ul>
<p>
list使用了全部3种构造
</p>
</div>
</div>
<div id="outline-container-orgaf3dd37" class="outline-2">
<h2 id="orgaf3dd37"><span class="section-number-2">2</span> Records</h2>
<div class="outline-text-2" id="text-2">
<p>
属于"each-of"类型：
</p>
<ul class="org-ul">
<li>record的值用字段来保存</li>
<li>record的类型也用字段保存</li>
<li>字段的顺序无关紧要</li>
</ul>
<p>
与tuple相比更容易记忆(有字段名)，
</p>
<p>
注意代码中-开始的行是repl的输入，下面是输出。
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">x</span> = {bar = (1+2, true <span style="color: #c397d8;">andalso</span> true), foo = 3+4, baz = (false,9)};
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">x</span> = {bar=(3,true),baz=(false,9),foo=7}
: {bar:int * bool, baz:bool * int, foo:int}
- #bar x;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = (3,true) : int * bool
- #foo x;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = 7 : int
</pre>
</div>
<p>
ML中不需要定义record类型，直接写record表达式，类型检查器会给出正确的类型。
</p>
</div>
</div>
<div id="outline-container-org01c7244" class="outline-2">
<h2 id="org01c7244"><span class="section-number-2">3</span> tuples as syntactic sugar</h2>
<div class="outline-text-2" id="text-3">
<p>
records和tuples很相似。都是"each-of"构造。唯一的不同是records通过名称访问，tuples通过位置访问。
java的方法调用组合了这两种方式:方法内使用变量名访问不同的参数，但调用者通过位置传递参数。
</p>
<p>
可以通过构造records来定义tuples:
</p>
<div class="org-src-container">
<pre class="src src-sml">- - <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">a_pair</span> = (3+1, 4+2);
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">a_pair</span> = (4,6) : int * int
- - <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">a_record</span> = {second=4+2, first=3+1};
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">a_record</span> = {first=4,second=6} : {first:int, second:int}
- - <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">another_pair</span> = {2=5, 1=6};
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">another_pair</span> = (6,5) : int * int
- - #1 a_pair + #2 another_pair;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = 9 : int
- - <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">x</span> = {3=<span style="color: #b9ca4a;">"hi"</span>, 1=true};
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">x</span> = {1=true,3=<span style="color: #b9ca4a;">"hi"</span>} : {1:bool, 3:string}
- - <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">y</span> = {3=<span style="color: #b9ca4a;">"hi"</span>, 1=true, 2=3+2};
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">y</span> = (true,5,<span style="color: #b9ca4a;">"hi"</span>) : bool * int * string
</pre>
</div>
<p>
实际上，tuple就是record, tuple是record的语法糖
</p>
<p>
方便设计实现(语言核心足够简单)，方便理解
</p>
</div>
</div>
<div id="outline-container-orga02e7db" class="outline-2">
<h2 id="orga02e7db"><span class="section-number-2">4</span> datatype bindings</h2>
<div class="outline-text-2" id="text-4">
<div class="org-src-container">
<pre class="src src-sml">datatypee mytype = TwoInts <span style="color: #c397d8;">of</span> int * int
| Str <span style="color: #c397d8;">of</span> string
| Pizza
</pre>
</div>
<p>
每个mytype的值都从一个构造器产生,
每个值包括:构造的tag, 对应的数据
</p>
<p>
上面的示例创建一个新类型 <b>mytype</b> 和3个构造器 <b>TwoInts</b>, <b>Str</b>, <b>Pizza</b>
</p>
<p>
构造器两种表示，它可以是创建新类型值的函数(如果有 <b>of t</b> )，或者是新类型的值。
上面的示例中， <b>TwoInts</b> 是一个函数，类型为 <b>int\*int -> mytype</b>, <b>Str</b> 是一个类型为 <b>string->mytype</b> 的函数， <b>Pizza</b> 是类型为 <b>mytype</b> 的值。
</p>
<p>
要访问datatype的值，需要:
</p>
<ol class="org-ol">
<li>检查是哪个构造器构造的</li>
<li>提取数据</li>
</ol>
<p>
例如: null 和 isSome检查;
ht,tl 和 valOf 提取数据
</p>
<div class="org-src-container">
<pre class="src src-sml">- - <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">exp</span> = Constant <span style="color: #c397d8;">of</span> int
| Negate <span style="color: #c397d8;">of</span> exp
| Add <span style="color: #c397d8;">of</span> exp * exp
| Multiply <span style="color: #c397d8;">of</span> exp * exp ;
<span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">exp</span>
= Add <span style="color: #c397d8;">of</span> exp * exp | Constant <span style="color: #c397d8;">of</span> int | Multiply <span style="color: #c397d8;">of</span> exp * exp | Negate <span style="color: #c397d8;">of</span> exp
- - <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">r</span> = Add (Constant (10 + 9), Negate (Constant 4));
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">r</span> = Add (Constant 19,Negate (Constant 4)) : exp
- - <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">eval</span> e =
<span style="color: #c397d8;">case</span> e <span style="color: #c397d8;">of</span>
Constant i => i
| Negate e2 => ~ (eval e2)
| Add(e1, e2) => (eval e1) + (eval e2)
| Multiply(e1,e2) => (eval e1) * (eval e2)
;
= <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">eval</span> = <span style="color: #c397d8;">fn</span> : exp -> int
- - eval r;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = 15 : int
</pre>
</div>
</div>
</div>
<div id="outline-container-orgb8cf071" class="outline-2">
<h2 id="orgb8cf071"><span class="section-number-2">5</span> case 表达式</h2>
<div class="outline-text-2" id="text-5">
<p>
ML使用case表达式和模式匹配访问"one-of"值
</p>
<div class="org-src-container">
<pre class="src src-sml">- - <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">mytype</span> = TwoInts <span style="color: #c397d8;">of</span> int * int
| Str <span style="color: #c397d8;">of</span> string
| Pizza
;
= <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">mytype</span> = Pizza | Str <span style="color: #c397d8;">of</span> string | TwoInts <span style="color: #c397d8;">of</span> int * int
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">f</span> (x : mytype) =
<span style="color: #c397d8;">case</span> x <span style="color: #c397d8;">of</span>
Pizza => 3
| Str s => 8
| TwoInts(i1, i2) => i1 + i2
;
= <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">f</span> = <span style="color: #c397d8;">fn</span> : mytype -> int
- - f Pizza;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = 3 : int
- - f (TwoInts (7, 9));
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = 16 : int
</pre>
</div>
<p>
在某种意义上，case表达式就像一个更强大的if-then-else表达式。它首先求值 <b>case</b> 和 <b>of</b> 中间的表达式，然后求值第一个匹配的分支的表达式。和条件表达式一样，每个分支表达式必须有相同的类型，作为case表达式的值。
</p>
<p>
对于每个分支 <b>p => e</b> p是一个模式，e是一个表达式；使用|分割多个分支。模式看起来像表达式，但不要把它们想做表达式。它们用来匹配case的第一个表达式( <b>case</b> 后面的部分)的值。这就是为什么case表达式叫做模式匹配。
</p>
</div>
</div>
<div id="outline-container-orgb216fdd" class="outline-2">
<h2 id="orgb216fdd"><span class="section-number-2">6</span> 类型同义词</h2>
<div class="outline-text-2" id="text-6">
<p>
type aname = t
</p>
<p>
两个名字可以互换使用
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">suit</span> = Club | Diamond | Heart | Spade ;
<span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">suit</span> = Club | Diamond | Heart | Spade
- <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">rank</span> = Jack | Queen | King | Ace | Num <span style="color: #c397d8;">of</span> int;
<span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">rank</span> = Ace | Jack | King | Num <span style="color: #c397d8;">of</span> int | Queen
- <span style="color: #c397d8;">type</span> <span style="font-weight: bold;">card</span> = suit * rank;
<span style="color: #c397d8;">type</span> <span style="font-weight: bold;">card</span> = suit * rank
- <span style="color: #c397d8;">type</span> <span style="font-weight: bold;">name_record</span> = { student_num : int option,
first : string,
middle : string option,
last : string };
<span style="color: #c397d8;">type</span> <span style="font-weight: bold;">name_record</span> =
{first:string, last:string, middle:string option, student_num:int option}
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">is_Queen_of_Spades</span> (c : card) =
#1 c = Spade <span style="color: #c397d8;">andalso</span> #2 c = Queen;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">is_Queen_of_Spades</span> = <span style="color: #c397d8;">fn</span> : card -> bool
- <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">c1</span> : card = (Diamond, Ace);
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">c1</span> = (Diamond,Ace) : card
- <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">c2</span> : suit * rank = (Heart, Ace);
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">c2</span> = (Heart,Ace) : suit * rank
- <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">c3</span> = (Spade, Ace);
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">c3</span> = (Spade,Ace) : suit * rank
- is_Queen_of_Spades c1;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = false : bool
- is_Queen_of_Spades c2;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = false : bool
- is_Queen_of_Spades c3;
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = false : bool
</pre>
</div>
</div>
</div>
<div id="outline-container-orgfc7e20b" class="outline-2">
<h2 id="orgfc7e20b"><span class="section-number-2">7</span> Lists和Options也是datatype</h2>
<div class="outline-text-2" id="text-7">
<p>
因为datatype可以递归定义，我们可以用来定义自己的lists类型:
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">my_int_list</span> = Empty
| Cons <span style="color: #c397d8;">of</span> int * my_int_list ;
= <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">my_int_list</span> = Cons <span style="color: #c397d8;">of</span> int * my_int_list | Empty
- <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">one_two_three</span> = Cons(1, Cons(2, Cons(3, Empty)));
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">one_two_three</span> = Cons (1,Cons (2,Cons #)) : my_int_list
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">append_mylist</span> (xs, ys) =
<span style="color: #c397d8;">case</span> xs <span style="color: #c397d8;">of</span>
Empty => ys
| Cons(x, xs') => Cons(x, append_mylist(xs', ys));
= <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">append_mylist</span> = <span style="color: #c397d8;">fn</span> : my_int_list * my_int_list -> my_int_list
</pre>
</div>
<p>
对于options, <b>SOME</b> 和 <b>NONE</b> 是构造器。
对于lists来说 <b>[]</b> 和 <b>::</b> 都是构造器。::有点特殊，因为它是中缀操作符(在两个操作数中间)。
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">inc_or_zero</span> intoption =
<span style="color: #c397d8;">case</span> intoption <span style="color: #c397d8;">of</span>
NONE => 0
| SOME i => i + 1 ;
= <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">inc_or_zero</span> = <span style="color: #c397d8;">fn</span> : int option -> int
- <span style="color: #c397d8;">fun</span> append(xs, ys) =
<span style="color: #c397d8;">case</span> xs <span style="color: #c397d8;">of</span>
[] => ys
| x::xs' => x :: append(xs', ys) ;
= <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">append</span> = <span style="color: #c397d8;">fn</span> : 'a list * 'a list -> 'a list
</pre>
</div>
<p>
模式匹配的优点: 不会有例外情况。不能应用错误的函数。
</p>
</div>
</div>
<div id="outline-container-org0f768ea" class="outline-2">
<h2 id="org0f768ea"><span class="section-number-2">8</span> 多态数据类型</h2>
<div class="outline-text-2" id="text-8">
<p>
好的语言设计：定义自己的多态类型
</p>
<div class="org-src-container">
<pre class="src src-sml"><span style="color: #c397d8;">datatype</span> 'a <span style="font-weight: bold;">option</span> = NONE | SOME <span style="color: #c397d8;">of</span> 'a
<span style="color: #c397d8;">datatype</span> 'a <span style="font-weight: bold;">mylist</span> = Empty | Cons <span style="color: #c397d8;">of</span> 'a * 'a mylist
<span style="color: #c397d8;">datatype</span> ('a, 'b) <span style="font-weight: bold;">tree</span> =
Node <span style="color: #c397d8;">of</span> 'a * ('a, 'b) tree * ('a, 'b) tree
| Leaf <span style="color: #c397d8;">of</span> 'b
</pre>
</div>
</div>
</div>
<div id="outline-container-org46eda57" class="outline-2">
<h2 id="org46eda57"><span class="section-number-2">9</span> Each-of类型的模式匹配:val绑定的真相</h2>
<div class="outline-text-2" id="text-9">
<p>
val绑定模式，val绑定可以使用模式， val p = e, 例如:
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">val</span> (x,y) = (1,2);
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">x</span> = 1 : int
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">y</span> = 2 : int
- <span style="color: #c397d8;">val</span> {f1=a, f2=b} = {f2 =5, f1=3};
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">a</span> = 3 : int
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">b</span> = 5 : int
</pre>
</div>
<p>
当知道一个模式肯定会被匹配时，使用模式匹配就是为了提取值。
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">full_name</span> (r : {first:string, middle:string, last:string}) =
<span style="color: #c397d8;">let</span> <span style="color: #c397d8;">val</span> {first=x, middle=y, last=z} = r
<span style="color: #c397d8;">in</span>
x ^ <span style="color: #b9ca4a;">" "</span> ^ y ^ <span style="color: #b9ca4a;">" "</span> ^ z
<span style="color: #c397d8;">end</span>
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">full_name</span> = <span style="color: #c397d8;">fn</span> : {first:string, last:string, middle:string} -> string
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">sum_triple</span> (triple : int*int*int) =
<span style="color: #c397d8;">let</span> <span style="color: #c397d8;">val</span> (x,y,z) = triple
<span style="color: #c397d8;">in</span>
x + y + z
<span style="color: #c397d8;">end</span>
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">sum_triple</span> = <span style="color: #c397d8;">fn</span> : int * int * int -> int
<span style="color: #969896; font-style: italic;">(* </span><span style="color: #969896; font-style: italic;">在定义函数绑定中使用模式 </span><span style="color: #969896; font-style: italic;">*)</span>
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">full_name</span> {first=x, middle=y, last=z} = x ^ <span style="color: #b9ca4a;">" "</span> ^ y ^ <span style="color: #b9ca4a;">" "</span> ^ z
= <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">full_name</span> = <span style="color: #c397d8;">fn</span> : {first:string, last:string, middle:string} -> string
- full_name {first=<span style="color: #b9ca4a;">"a"</span>, middle=<span style="color: #b9ca4a;">"b"</span>, last=<span style="color: #b9ca4a;">"c"</span>};
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">it</span> = <span style="color: #b9ca4a;">"a b c"</span> : string
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">sum_triple</span> (x,y,z) = x + y + z
= <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">sum_triple</span> = <span style="color: #c397d8;">fn</span> : int * int * int -> int
</pre>
</div>
<p>
ML中的所有函数都是一个参数，按照模式匹配展开，可以是tuple:(a,b,c);也可以是record:{a,b,c}或者其它。
这种灵活性很有用，可以把函数的返回值直接传递给其它有多个参数的函数。没有无参数的函数，hello()也是一个参数(空的tuple， <b>unit</b> 类型)。因为存在预定义的类型 , <b>datatype unit = ()</b>
</p>
</div>
</div>
<div id="outline-container-orgc626028" class="outline-2">
<h2 id="orgc626028"><span class="section-number-2">10</span> 类型推断,多态类型与相等类型</h2>
<div class="outline-text-2" id="text-10">
<p>
在ML中，所有的变量和函数都有一个类型，类型推断只是表示不需要把类型写下来。
</p>
<p>
类型推断有时会让你的函数更通用。
</p>
<p>
多态表示更通用的类型，例如append的类型 <b>'a list * 'a list -> 'a list</b> ,可以统一地把'a替换为 <b>string</b>,就像append具有 <b>string list * string list -> string list</b> 类型一样使用。可以用任何类型替换'a。
</p>
<p>
<b>''a</b> 表示相等类型：
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">fun</span> same_thing(x,y) = <span style="color: #c397d8;">if</span> x=y <span style="color: #c397d8;">then</span> <span style="color: #b9ca4a;">"yes"</span> <span style="color: #c397d8;">else</span> <span style="color: #b9ca4a;">"no"</span>;
stdIn:1.28 Warning: calling polyEqual
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">same_thing</span> = <span style="color: #c397d8;">fn</span> : ''a * ''a -> string
</pre>
</div>
</div>
</div>
<div id="outline-container-org3190ed9" class="outline-2">
<h2 id="org3190ed9"><span class="section-number-2">11</span> 嵌套模式</h2>
<div class="outline-text-2" id="text-11">
<p>
模式是递归的。通常模式匹配就是取一个值和一个模式，然后确定模式是否与值匹配，如果匹配，变量绑定到值的正确部分。模式匹配的递归定义的关键点:
</p>
<ul class="org-ul">
<li>一个变量模式(x)匹配任意值v并引入一个绑定</li>
<li>模式 <b>C</b> 匹配值 <b>C</b> ，如果 <b>C</b> 是一个没有任何数据的构造器</li>
<li>模式 <b>C p</b> (构造器 <b>C</b> 和 模式 <b>p</b> )匹配一个值 <b>C v</b> (注意构造器相同),如果 <b>p</b> 匹配 <b>v</b> (嵌套模式匹配携带的值)。它引入了 <b>p</b> 匹配 <b>v</b> 的绑定。</li>
<li>模式(p1,p2,…,pn)匹配tuple值(v1,v2,…,vn),如果p1匹配v1,p2匹配v2,…,pn匹配vn.它引入所有递归匹配引入的绑定。</li>
<li>record模式与tuple类似 {f1=p1,…,fn=pn}</li>
</ul>
<p>
模式匹配中使用通配符 <b>_</b> 匹配所有值，但不会引入新绑定。
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">exception</span> BadTriple
<span style="color: #c397d8;">exception</span> BadTriple
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">zip</span> list_triple =
<span style="color: #c397d8;">case</span> list_triple <span style="color: #c397d8;">of</span>
([],[],[]) => []
| (hd1::tl1, hd2::tl2, hd3::tl3) => (hd1,hd2,hd3)::zip(tl1,tl2,tl3)
| _ => <span style="color: #c397d8;">raise</span> BadTriple
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">zip</span> = <span style="color: #c397d8;">fn</span> : 'a list * 'b list * 'c list -> ('a * 'b * 'c) list
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">unzip3</span> lst =
<span style="color: #c397d8;">case</span> lst <span style="color: #c397d8;">of</span>
[] => ([],[],[])
| (a,b,c)::tl => <span style="color: #c397d8;">let</span> <span style="color: #c397d8;">val</span> (l1,l2,l3) = unzip3 tl
<span style="color: #c397d8;">in</span>
(a::l1, b::l2, c::l3)
<span style="color: #c397d8;">end</span>
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">unzip3</span> = <span style="color: #c397d8;">fn</span> : ('a * 'b * 'c) list -> 'a list * 'b list * 'c list
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">nondecreasing</span> intlist =
<span style="color: #c397d8;">case</span> intlist <span style="color: #c397d8;">of</span>
[] => true
| _::[] => true
| head::(neck::rest) => (head <= neck <span style="color: #c397d8;">andalso</span> nondecreasing (neck::rest))
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">nondecreasing</span> = <span style="color: #c397d8;">fn</span> : int list -> bool
- <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">sgn</span> = P | N | Z
= <span style="color: #c397d8;">datatype</span> <span style="font-weight: bold;">sgn</span> = N | P | Z
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">multsign</span> (x1,x2) =
<span style="color: #c397d8;">let</span> <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">sign</span> x = <span style="color: #c397d8;">if</span> x=0 <span style="color: #c397d8;">then</span> Z <span style="color: #c397d8;">else</span> <span style="color: #c397d8;">if</span> x>0 <span style="color: #c397d8;">then</span> P <span style="color: #c397d8;">else</span> N
<span style="color: #c397d8;">in</span>
<span style="color: #c397d8;">case</span> (sign x1,sign x2) <span style="color: #c397d8;">of</span>
(Z, _) => Z
| (_, Z) => Z
| (P, P) => P
| (N, N) => N
| _ => N
<span style="color: #c397d8;">end</span>
= <span style="color: #c397d8;">val</span> <span style="color: #e78c45;">multsign</span> = <span style="color: #c397d8;">fn</span> : int * int -> sgn
</pre>
</div>
</div>
</div>
<div id="outline-container-org9c5f5b6" class="outline-2">
<h2 id="org9c5f5b6"><span class="section-number-2">12</span> 异常</h2>
<div class="outline-text-2" id="text-12">
<p>
ML有内置的异常概念。使用 <b>raise</b> 抛出一个异常。使用异常绑定创建自己的异常。
异常构造器可以创建 <b>exn</b> 类型的值。
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">exception</span> MyUndesirableCondition
- <span style="color: #c397d8;">exception</span> MyOtherException <span style="color: #c397d8;">of</span> int * int
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">maxlist</span> (xs, ex) =
<span style="color: #c397d8;">case</span> xs <span style="color: #c397d8;">of</span>
[] => <span style="color: #c397d8;">raise</span> ex
| x::[] => x
| x::xs' => Int.max(x,maxlist(xs',ex));
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">maxlist</span> = <span style="color: #c397d8;">fn</span> : int list * exn -> int
</pre>
</div>
<p>
处理异常使用handle表达式: <b>e1 handle p => e2</b> , e1和e2是表达式，p是用来匹配异常的模式。
</p>
</div>
</div>
<div id="outline-container-org2839301" class="outline-2">
<h2 id="org2839301"><span class="section-number-2">13</span> 尾递归和累加器</h2>
<div class="outline-text-2" id="text-13">
<p>
新的编程模型:尾递归，编写有效率的递归函数。使用累加器把一些函数变为尾递归。
</p>
<div class="org-src-container">
<pre class="src src-sml">- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">sum1</span> xs =
<span style="color: #c397d8;">case</span> xs <span style="color: #c397d8;">of</span>
[] => 0
| i::xs' => i + sum1 xs'
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">sum1</span> = <span style="color: #c397d8;">fn</span> : int list -> int
- <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">sum2</span> xs =
<span style="color: #c397d8;">let</span> <span style="color: #c397d8;">fun</span> <span style="color: #7aa6da;">f</span> (xs,acc) =
<span style="color: #c397d8;">case</span> xs <span style="color: #c397d8;">of</span>
[] => acc
| i::xs' => f(xs',i+acc)
<span style="color: #c397d8;">in</span>
f(xs,0)
<span style="color: #c397d8;">end</span>
<span style="color: #c397d8;">val</span> <span style="color: #e78c45;">sum2</span> = <span style="color: #c397d8;">fn</span> : int list -> int
</pre>
</div>
<p>
函数调用的实现依靠调用栈(call stack)，调用栈的内容是每个函数为一个元素，这个函数是已启动但还没有完毕的调用。
每个元素保存局部变量和函数还未求值的部分。当一个函数体内调用了另一个函数，一个新的元素push到调用栈，当被调用的函数完成后弹出。
</p>
<p>
对于 <b>sum1</b> ,每个 <b>sum1</b> 递归调用都会产生一个调用栈元素，栈会和列表一样大。因为在弹出每个栈帧后，调用者要加 <b>i</b> 到每个递归结果并返回。
</p>
<p>
对于 <b>sum2</b> ,在被调用函数返回后，调用函数不需要做任何事，只需返回被调用函数的结果。这种情况叫做尾递归，函数式语言通常会对这种情况优化:当调用一个尾递归调用，调用者的栈帧在调用之前弹出，被调用者的栈帧替换调用者的。这很简单：调用者只是返回被调用者的结果。因此，调用 <b>sum2</b> 只需要1个栈帧。
</p>
<p>
使用累加器是把递归函数转换为尾递归函数的常用方法。通常转换一个非尾递归函数到尾递归函数需要满足结合律。
</p>
<p>
如果一个调用在尾部位置，它就是尾递归调用。尾部位置定义如下：
</p>
<ul class="org-ul">
<li>在 <b>fun f(x) = e</b> 中, <b>e</b> 在尾部位置</li>
<li>如果一个表达式不在尾部位置，那么它的子表达式都不在尾部位置</li>
<li>如果 <b>if e1 then e2 else e3</b> 在尾部位置，则 <b>e2</b> 和 <b>e3</b> 在尾部位置( <b>e1</b> 不在),case表达式类似。</li>
<li>如果 <b>let b1 … bn in e end</b> 在尾部位置， 则 <b>e</b> 在尾部位置(但绑定中的表达式不在)。</li>
<li>函数调用参数不在尾部位置。</li>
</ul>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="author">作者: ntestoc</p>
<p class="date">Created: 2018-12-05 Wed 13:01</p>
<p class="validation"></p>
</div>
</body>
</html>