ELEMENTS OF ML PROGRAMMING
		      Second Edition
			Using ML97

		     Jeffrey D. Ullman

		     TABLE OF CONTENTS

1 A Perspective on ML and SML/NJ 
	1.1 Why ML? 
	1.2 Standard ML of New Jersey 
	1.3 Prerequisites for the Reader 
	1.4 References and Web Resources 
	1.5 Features of ML97 

2 Getting Started in ML 
	2.1 Expressions 
		2.1.1 Constants 
		2.1.2 Arithmetic Operators 
		2.1.3 String Operators 
		2.1.4 Comparison Operators 
		2.1.5 Combining Logical Values 
		2.1.6 If-Then-Else Expressions 
		2.1.7 Exercises for Section 2.1 
	2.2 Type Consistency 
		2.2.1 Type Errors 
		2.2.2 Coercion Between Integers and Reals 
		2.2.3 Coercions Between Characters and Integers 
		2.2.4 Coercions Between Strings and Characters 
		2.2.5 Exercises for Section 2.2 
	2.3 Variables and Environments 
		2.3.1 Identifiers 
		2.3.2 The Top-Level Environment 
		2.3.3 An Assignment-Like Statement 
		2.3.4 A View of ML Programming 
		2.3.5 Exercises for Section 2.3 
	2.4 Tuples and Lists 
		2.4.1 Tuples 
		2.4.2 Accessing Components of Tuples 
		2.4.3 Lists 
		2.4.4 List Notation and Operators 
		2.4.5 Converting Between Character Strings and Lists 
		2.4.6 Introduction to the ML Type System 
		2.4.7 Exercises for Section 2.4 

3 Defining Functions 
	3.1 It's Easy; It's fun 
		3.1.1 Function Types 
		3.1.2 Declaring Function Types 
		3.1.3 Function Application 
		3.1.4 Functions With More Than One Parameter 
		3.1.5 Functions that Reference External Variables 
		3.1.6 Exercises for Section 3.1 
	3.2 Recursive Functions 
		3.2.1 Function Execution 
		3.2.2 Nonlinear Recursion 
		3.2.3 Mutual Recursion 
		3.2.4 How ML Deduces Types 
		3.2.5 Exercises for Section 3.2 
	3.3 Patterns in Function Definitions 
		3.3.1 Patterns as Function Parameters 
		3.3.2 ``As'' You Like it: Having it Both Ways 
		3.3.3 Anonymous Variables 
		3.3.4 What Is and What Isn't a Pattern? 
		3.3.5 How ML Matches Patterns 
		3.3.6 A Subtle Pattern Bug 
		3.3.7 Exercises for Section 3.3 
	3.4 Local Environments Using let 
		3.4.1 Defining Common Subexpressions 
		3.4.2 Effect on Environments of let 
		3.4.3 Splitting Apart the Value Returned by a Function 
		3.4.4 Mergesort: An Efficient, Recursive Sorter 
		3.4.5 Exercises for Section 3.4 
	3.5 Case Study: Linear-Time Reverse 
		3.5.1 Analysis of Simple Reverse 
		3.5.2 ML's Representation of Lists 
		3.5.3 A Reversal Function Using Difference Lists 
		3.5.4 Analysis of Fast Reverse 
		3.5.5 Exercises for Section 3.5 
	3.6 Case Study: Polynomial Multiplication 
		3.6.1 Representing Polynomials by Lists 
		3.6.2 A Simple Polynomial-Multiplication Algorithm 
		3.6.3 Analysis of Simple Multiplication 
		3.6.4 Auxiliary Functions for a Faster Multiplication 
		3.6.5 The Karatsuba-Ofman Algorithm 
		3.6.6 Analysis of the Karatsuba-Ofman Algorithm 
		3.6.7 Exercises for Section 3.6 

4 Input and Output 
	4.1 Simple Output 
		4.1.1 The Print Function 
		4.1.2 Printing Nonstring Values 
		4.1.3 ``Statement'' Lists 
		4.1.4 Statement Lists Versus Let-Expressions 
		4.1.5 Exercises for Section 4.1 
	4.2 Reading Input From a File 
		4.2.1 Instreams 
		4.2.2 Reading Characters From a File 
		4.2.3 Reading Lines of a File 
		4.2.4 Reading Complete Files 
		4.2.5 Reading a Single Character 
		4.2.6 Lookahead on the Input 
		4.2.7 Closing Instreams 
		4.2.8 Exercises for Section 4.2 
	4.3 Output to Files 
		4.3.1 Outstreams 
		4.3.2 Closing Outstreams 
		4.3.3 The output Command 
		4.3.4 Exercises for Section 4.3 
	4.4 Case Study: Summing Integers 
		4.4.1 The Function startInt 
		4.4.2 The Function finishInt 
		4.4.3 The Function getInt 
		4.4.4 The Function sumInts 
		4.4.5 Eager Evaluation 
		4.4.6 Exercises for Section 4.4 

5 More About Functions 
	5.1 Matches and Patterns 
		5.1.1 Matches 
		5.1.2 Using Matches to Define Functions 
		5.1.3 Anonymous Functions 
		5.1.4 Case Expressions 
		5.1.5 If-Then-Else Expressions Revisited 
		5.1.6 Exercises for Section 5.1 
	5.2 Exceptions 
		5.2.1 User-Defined Exceptions 
		5.2.2 Expressions With Parameters 
		5.2.3 Handling Exceptions 
		5.2.4 Exceptions as Elements of an Environment 
		5.2.5 Local Exceptions 
		5.2.6 Exercises for Section 5.2 
	5.3 Polymorphic Functions 
		5.3.1 A Limitation on the Use of Polymorphic Functions 
		5.3.2 Operators that Restrict Polymorphism 
		5.3.3 Operators that Allow Polymorphism 
		5.3.4 The Equality Operators 
		5.3.5 Exercises for Section 5.3 
	5.4 Higher-Order Functions 
		5.4.1 Some Common Higher-Order Functions 
		5.4.2 A Simple Map Function 
		5.4.3 The Function reduce 
		5.4.4 Converting Infix Operators to Function Names 
		5.4.5 The Function Filter 
		5.4.6 Exercises for Section 5.4 
	5.5 Curried Functions 
		5.5.1 Partially Instantiated Functions 
		5.5.2 The ML Style of Function Application 
		5.5.3 Exercises for Section 5.5 
	5.6 Built-In Higher-Order Functions 
		5.6.1 Composition of Functions 
		5.6.2 The ML Operator o For Composition 
		5.6.3 The ``Real'' Version of Map 
		5.6.4 Folding Lists 
		5.6.5 Exercises for Section 5.6 
	5.7 Case Study: Parsing Expressions 
		5.7.1 The Grammatical Structure of Arithmetic Expressions 
		5.7.2 Structure of the Parsing Program 
		5.7.3 Detailed Explanation of the Parser Code 
		5.7.4 Exercises for Section 5.7 

6 Defining Your Own Types 
	6.1 Defining New Types 
		6.1.1 Review of the ML Type System 
		6.1.2 New Names for Old Types 
		6.1.3 Parametrized Type Definitions 
		6.1.4 Exercises for Section 6.1 
	6.2 Datatypes 
		6.2.1 A Simple Form of Datatype Declaration 
		6.2.2 Using Constructor Expressions in Datatype Definitions 
		6.2.3 Recursively Defined Datatypes 
		6.2.4 Mutually Recursive Datatypes 
		6.2.5 Exercises for Section 6.2 
	6.3 Case Study: Binary Trees 
		6.3.1 Binary Search Trees 
		6.3.2 Lookup in Binary Search Trees 
		6.3.3 Insertion into Binary Search Trees 
		6.3.4 Deletion from Binary Search Trees 
		6.3.5 Some Comments About Running Time 
		6.3.6 Visiting All the Nodes of a Binary Tree 
		6.3.7 Preorder Traversals 
		6.3.8 Exercises for Section 6.3 
	6.4 Case Study: General Rooted Trees 
		6.4.1 A Datatype for Trees 
		6.4.2 Summing the Labels of a General Tree 
		6.4.3 Computing Sums Using Higher-Order Functions 
		6.4.4 Exercises for Section 6.4 

7 More About ML Data Structures 
	7.1 Record Structures 
		7.1.1 Records and Their Types 
		7.1.2 Extracting Field Values 
		7.1.3 Tuples as a Special Case of Record Structures 
		7.1.4 Patterns That Match Records 
		7.1.5 Shorthands in Record Patterns 
		7.1.6 Exercises for Section 7.1 
	7.2 Arrays 
		7.2.1 Why Do We Need Arrays? 
		7.2.2 Array Operations 
		7.2.3 Exercises for Section 7.2 
	7.3 References 
		7.3.1 The ref Type Constructor 
		7.3.2 Obtaining the Value of a Ref-Variable 
		7.3.3 Modifying Ref-Variables 
		7.3.4 The While-Do Statement 
		7.3.5 Exercises for Section 7.3 
	7.4 Case Study: Hash Tables 
		7.4.1 The Dictionary Operations 
		7.4.2 How a Hash Table Works 
		7.4.3 An Example of Hash Table Implementation 
		7.4.4 Exercises for Section 7.4 
	7.5 Case Study: Triangularization of a Matrix 
		7.5.1 Creating and Initializing the Matrix 
		7.5.2 Triangularization by Row Operations 
		7.5.3 Exercises for Section 7.5 

8 Encapsulation and the ML Module System 
	8.1 Why Modules? 
		8.1.1 Information Hiding 
		8.1.2 Clustering Connected Elements 
	8.2 Structures 
		8.2.1 Signatures 
		8.2.2 Restricting Structures Through Their Signatures 
		8.2.3 Accessing Names Defined Within Structures 
		8.2.4 Opening Structures 
		8.2.5 Exercises for Section 8.2 
	8.3 Functors 
		8.3.1 Motivation for Functors 
		8.3.2 Using Functors to Import Information 
		8.3.3 More General Forms for Functor Parameters and Arguments 
		8.3.4 Exercises for Section 8.3 
	8.4 Sharings 
		8.4.1 Sharing Specifications 
		8.4.2 Substructures 
		8.4.3 Sharing of Types 
		8.4.4 Sharing of Substructures 
		8.4.5 Exercises for Section 8.4 
	8.5 ML Techniques for Hiding Information 
		8.5.1 An Information-Hiding Problem 
		8.5.2 Using Signatures to Hide Information 
		8.5.3 Abstract Types 
		8.5.4 Local Definitions 
		8.5.5 Opaque Signatures 
		8.5.6 Exercises for Section 8.5 
	8.6 Case Study: Feedback Shift Registers 
		8.6.1 Operation of a Feedback Shift Register 
		8.6.2 A Functor to Create Random Number Generators 
		8.6.3 Generating a Feedback Shift Register 
		8.6.4 Exercises for Section 8.6 

9 Summary of the ML Standard Basis 
	9.1 The Infix Operators 
		9.1.1 Precedence 
		9.1.2 Precedence Levels in ML 
		9.1.3 Associativity of Operators 
		9.1.4 Creating New Infix Operators 
		9.1.5 Infix Data Constructors 
		9.1.6 Exercises for Section 9.1 
	9.2 Functions in the Top-Level Environment 
		9.2.1 Functions on Integers 
		9.2.2 Functions on Reals 
		9.2.3 Functions on Booleans 
		9.2.4 Functions on Characters 
		9.2.5 Functions on Strings 
		9.2.6 Functions on Options 
		9.2.7 Functions on References 
		9.2.8 Functions on Lists 
		9.2.9 Functions on Exceptions 
		9.2.10 Functions Affecting Return Values 
		9.2.11 Exercises for Section 9.2 
	9.3 Top-Level Types and Exceptions 
		9.3.1 Primitive Types 
		9.3.2 Primitive Type Constructors 
		9.3.3 Primitive Datatypes 
		9.3.4 Top-Level Exceptions 
		9.3.5 Exercises for Section 9.3 
	9.4 Structures of the Standard Basis 
		9.4.1 The Structure Int 
		9.4.2 The Structure Word 
		9.4.3 The Structures Real and Math 
		9.4.4 The Structure Char 
		9.4.5 The Structure String 
		9.4.6 The Structure Substring 
		9.4.7 The Structure List 
		9.4.8 The Structure Array 
		9.4.9 The Structure Vector 
		9.4.10 The Structure OS 
		9.4.11 The Structures Time and Timer 
		9.4.12 What If I Lose a Name? 
		9.4.13 Exercises for Section 9.4 
	9.5 Additional Features of SML/NJ 
		9.5.1 Exporting Functions 
		9.5.2 Exporting the ML Environment 
		9.5.3 Exercises for Section 9.5 
	9.6 Summary of ML Syntax 
		9.6.1 Lexical Categories 
		9.6.2 Some Simplifications to the Grammatical Structure 
		9.6.3 Expressions 
		9.6.4 Matches and Patterns 
		9.6.5 Types 
		9.6.6 Declarations 
		9.6.7 Signatures 
		9.6.8 Structures 
		9.6.9 Functors 
		9.6.10 Programs