Lập trình hàm - Đại học Đà Nẵng

CHƯƠNG I. NGUYÊN LÝ LẬP TRÌNH HÀM

I.1 Mở đầu về ngôn ngữ lập trình.1

I.1.1. Vài nét về lịch sử.1

I.1.2. Định nghĩa một ngôn ngữ lập trình.2

I.1.3. Khái niệm về chương trình dịch.4

I.1.4. Phân loại các ngôn ngữ lập trình.5

I.1.5. Ngôn ngữ lập trình mệnh lệnh.7

I.2 Cơ sở của các ngôn ngữhàm.8

I.2.1. Tính khai báo của các ngôn ngữ hàm.8

I.2.2. Định nghĩa hàm.11

I.2.3. Danh sách.13

I.2.4. Phép so khớp.16

I.2.5. Phương pháp currying (tham đối hoá từng phần).17

I.2.6. Khái niệm về bậc của hàm.18

I.2.7. Kiểu và tính đa kiểu.20

I.2.8. Tính hàm theo kiểu khôn ngoan.22

I.2.9. Một số ví dụ.25

1. Loại bỏ những phần tử trùng nhau.25

2. Sắp xếp nhanh quicksort.25

3. Bài toán tám quân hậu.26

4. Bài toán hamming.27

I.3 Kết luận.29

CHƯƠNG II. NGÔN NGỮSCHEME.33

II.1 Giới thiệu Scheme.33

II.2 Các kiểu dữ liệu của Scheme.34

II.2.1. Các kiểu dữ liệu đơn giản.34

II.2.1.1. Kiểu số.34

II.2.1.2. Kiểu lôgích và vịtừ.36

II.2.1.3. Ký hiệu.38

II.2.2. Khái niệm về các biểu thức tiền tố.39

II.2.3. S-biểu thức.41

II.3 Các định nghĩa trong Scheme.41

II.3.1. Định nghĩa biến.41

II.3.2. Định nghĩa hàm.42

II.3.2.1. Khái niệm hàm trong Scheme.42

II.3.2.2. Gọi hàm sau khi định nghĩa.43

II.3.2.3. Sửdụng các hàmbổtrợ.44

II.3.2.4. Tính không định kiểu của Scheme.45

II.3.3. Cấu trúc điều khiển.45

II.3.3.1. Dạng điều kiện if.45

II.3.3.2. Biến cục bộ.47

1. Định nghĩa biến cục bộ nhờ dạng let.47

2. Phạm vi tự động của dạng let.48

3. Liên kết biến theo dãy : dạng let*.48

II.3.3.3. Định nghĩa các vị từ.49

II.3.4. Sơ đồ đệquy và sơ đồ lặp.50

II.3.4.1. Sơ đồ đệquy.50

II.3.4.2. Ví dụ.51

1. Tính tổng bình phương các sốtừ1 đến n.51

2. Tính giai thừa.51

3. Hàm fibonacci.51

4. Tính các hệ số nhị thức.52

II.3.4.3. Tính dừng của lời gọi đệ quy.52

II.3.4.4. Chứng minh tính dừng.54

II.3.4.5. Sơ đồ lặp.54

II.3.5. Vào/ra dữ liệu.56

1. Đọc vào dữ liệu : read.56

2. In ra dữ liệu : write và display.56

3. Xây dựng vòng lặp có menu.57

CHƯƠNG III. KIỂU DỮLIỆU PHỨC HỢP.61

III.1Kiểu chuỗi.61

III.2Kiểu dữliệu vectơ.64

III.3Kiểu dữliệu bộ đôi.64

III.3.1. Khái niệm trừu tượng hoá dữ liệu.64

III.3.2. Định nghĩa bộ đôi.66

III.3.3. Đột biến trên các bộ đôi.68

III.3.4. Ứng dụng bộ đôi.69

1. Biểu diễn các sốhữu tỷ.69

2. Biểu diễn hình chữ nhật phẳng.72

III.4Kiểu dữ liệu danh sách.74

III.4.1. Khái niệmdanh sách.74

III.4.2. Ứng dụng danh sách.76

III.4.2.1. Các phép toán cơbản cons, list, car và cdr.76

III.4.2.2. Các hàm xử lý danh sách.79

1. Các hàm length, append và reverse.79

2. Các hàm tham chiếu danh sách.80

3. Các hàm chuyển đổi kiểu.81

4. Các hàm so sánh danh sách.83

III.4.2.3. Dạng case xử lý danh sách.84

III.4.2.4. Kỹthuật đệ quy xử lý danh sách phẳng.86

1. Tính tổng các phần tử của một danh sách.86

2. Danh sách các số nguyên từ0 đến n.86

3. Nghịch đảo một danh sách.87

4. Hàm append có hai tham đối.87

5. Loại bỏ các phần tửkhỏi danh sách.87

6. Bài toán tính tổng con.88

7. Lập danh sách các sốnguyên tố.88

III.4.2.5. Kỹ thuật đệ quy xử lý danh sách bất kỳ.89

1. Làm phẳng một danh sách .89

2. Tính tổng các số có mặt trong danh sách .90

3. Loại bỏ khỏi danh sách một phần tử ở các mức khác nhau.90

4. Nghịch đảo danh sách.90

5. So sánh bằng nhau .91

III.4.3. Biểu diễn danh sách .92

III.4.3.1. Biểu diễn danh sách bởi kiểu bộ đôi .92

III.4.3.2. Danh sách kết hợp .96

1. Khái niệm danh sách kết hợp .96

2. Sử dụng danh sách kết hợp .97

III.4.3.3. Dạng quasiquote .98

III.4.4. Một số ví dụ ứng dụng danh sách .99

1. Tìm phần tử cuối cùng của danh sách .99

2. Liệt kê các vị trí một ký hiệu có trong danh sách .100

3. Tìm tổng con lớn nhất trong một vector.100

4. Bài toán sắp xếp dãy viên bi ba màu .101

5. Sắp xếp nhanh quicksort .102

CHƯƠNG IV. KỸTHUẬT XỬLÝ HÀM.107

IV.1 Sửdụng hàm.107

IV.1.1. Dùng tên hàm làm tham đối .107

IV.1.2. Áp dụng hàm cho các phần tửcủa danh sách .110

IV.1.3. Kết quả trả về là hàm .112

IV.2 Phep tính lambda .113

IV.2.1. Giới thiệu phép tính lambda.113

IV.2.2. Biễu diễn biểu thức lambda trong Scheme .114

IV.2.3. Định nghĩa hàm nhờ lambda .115

IV.2.4. Kỹthuật sử dụng phối hợp lambda .117

IV.2.5. Định nghĩa hàm nhờ tích luỹkết quả.120

1. Tính tổng giá trị của một hàm áp dụng cho các phần tử danh sách.120

2. Tính tích giá trịcủa một hàm áp dụng cho các phần tửdanh sách.120

3. Định nghĩa lại hàm append ghép hai danh sách .120

4. Định nghĩa lại hàm map cho hàm một biến h .120

5. Định nghĩa các hàm fold .122

IV.2.6. Tham đối hoá từng phần .122

IV.2.7. Định nghĩa đệquy cục bộ.123

IV.3 Xửlý trên các hàm.125

IV.3.1. Xây dựng các phép lặp.125

1. Hàm append-map .125

2. Hàm map-select.126

3. Các hàm every và some.126

IV.3.2. Trao đổi thông điệp giữa các hàm.127

IV.3.3. Tổhợp các hàm .129

IV.3.4. Các hàm có số lượng tham đối bất kỳ.130

IV.4 Một sốví dụ.132

IV.4.1. Phương pháp xấp xỉliên tiếp .132

IV.4.2. Tạo thủ tục định dạng.133

IV.4.3. Xửlý đa thức.134

IV.4.3.1. Định nghĩa đa thức.134

IV.4.3.2. Biễu diễn đa thức.134

IV.4.3.3. Xửlý đa thức.135

1. Nhân đa thức với một hằng số.135

2. So sánh hai đa thức.136

3. Phép cộng đa thức.136

4. Phép nhân hai đa thức.137

IV.4.3.4. Biễu diễn trong một đa thức.137

IV.4.3.5. Đưa ra đa thức.138

IV.4.4. Thuật toán quay lui.139

IV.4.4.1. Bài toán tám quân hậu.139

IV.4.4.2. Tìm kiếmcác lời giải.140

IV.4.4.3. Tổchức các lời giải.143

CHƯƠNG V. CẤU TRÚC DỮLIỆU.147

V.1 Tập hợp.147

1. Phép hợp trên các tập hợp.148

2. Phép giao trên các tập hợp.149

3. Phép hiệu của hai tập hợp.149

4. Tìm các tập hợp con của một tập hợp.150

V.2 Ngăn xếp.150

V.2.1. Kiểu dữliệu trừu tượng ngăn xếp.150

V.2.2. Xây dựng ngăn xếp.151

V.2.3. Xây dựng trình soạn thảo văn bản.152

V.2.4. Ngăn xếp đột biến.153

V.2.5. Tính biểu thức sốhọc dạng hậu tố.156

V.3 Tệp.158

V.3.1. Cấu trúc dữliệu trừu tượng kiểu tệp.158

V.3.2. Ví dụáp dụng tệp.159

V.3.3. Tệp đột biến.160

V.4 Cây.162

V.4.1. Cây nhịphân.163

V.4.1.1. Kiểu trừu tượng cây nhịphân.163

V.4.1.2. Biểu diễn cây nhịphân.164

1. Biểu diễn tiết kiệm sửdụng hai phép cons.164

2. Biểu diễn dạng đầy đủ.165

3. Biểu diễn đơn giản.165

V.4.1.3. Một sốví dụlập trình đơn giản.166

1. Đếm sốlượng các nút có trong một cây.166

2. Tính độcao của một cây.166

V.4.1.4. Duyệt cây nhịphân.167

V.4.2. Cấu trúc cây tổng quát.169

V.4.2.1. Kiểu trừu tượng cây tổng quát.169

V.4.2.2. Biểu diễn cây tổng quát.169

1. Biểu diễn cây nhờmột bộ đôi.169

2. Biểu diễn cây đơn giản qua các lá.170

V.4.2.3. Một sốví dụvềcây tổng quát.170

MỤC LỤC v

1. Đếm sốlượng các nút trong cây .170

2. Tính độcao của cây .171

V.4.2.4. Duyệt cây tổng quát không có xửlý trung tố.171

V.4.3. Ứng dụng cây tổng quát .172

V.4.3.1. Xây dựng cây cú pháp .172

V.4.3.2. Ví dụ: đạo hàm hình thức .173

CHƯƠNG VI. MÔI TRƯỜNG VÀ CẤP PHÁT BỘNHỚ.177

VI.1 Môi trường.177

VI.1.1. Một sốkhái niệm.177

VI.1.2. Phạm vi của một liên kết.178

VI.1.2.1. Phạm vi tĩnh .178

VI.1.2.2. Phép đóng = biểu thức lambda + môi trường.179

VI.1.2.3. Thay đổi bộnhớvà phép đóng .180

VI.1.2.4. Nhận biết hàm .181

VI.1.2.5. Phạm vi động.182

VI.1.3. Thời gian sống của một liên kết .184

VI.1.4. Môi trường toàn cục.184

VI.2 Cấp phát bộnhớ.185

VI.2.1. Ví dụ1 : mô phỏng máy tính bỏtúi .186

VI.2.2. Ví dụ2 : bài toán cân đối tài khoản .187

VI.3 Mô hình sửdụng môi trường.189

VI.4 Vào/ra dữliệu.192

VI.4.1. Làm việc với các tệp .192

VI.4.2. Đọc dữliệu trên tệp.193

1. Các hàm đọc tệp.193

2. Tệp văn bản .195

VI.4.3. Ghi lên tệp .196

1. Các hàm ghi lên tệp .196

2. Lệnh sao chép tệp.197

VI.4.4. Giao tiếp với hệthống.198

PHỤLỤC .203

TÀI LIỆU THAM KHẢO .205