Haskell 程序設計基礎 (微課版)

目  錄

第 1 章  電腦程序設計  1 

1.1  命令式程序設計  1 

1.1.1  程序設計的概念  1 

1.1.2  命令式算法和偽代碼 2 

1.1.3  命令式程序  3 

1.2  函數程序設計  4 

1.2.1  程序是函數  4 

1.2.2  Haskell 函數程序  5 

1.2.3  Haskell 函數語言的特點 5 

1.3  Haskell 解釋器和編譯器  6 

1.3.1  下載 Haskell 解釋器和編譯器 7 

1.3.2  運行 Haskell 程序 8 

1.3.3  解釋器常用命令 10 

1.4  習題  10 

第 2 章  函數程序設計基礎  12 

2.1  程序與函數 12 

2.1.1  數學函數 13 

2.1.2  Haskell 函數 14 

2.2  數據和類型 15 

2.2.1  數據類型  15 

2.2.2  數值類型  15 

2.2.3  布爾類型  17 

2.2.4  查看表達式的類型  18 

2.2.5  字符和字符串 19 

2.2.6  列表類型   19 

2.2.7  多元組類型  21 

2.2.8  多元組類型和列表類型的對比 22

2.2.9  函數類型  23 

2.2.10  函數應用與類型推導規則 23 

2.3  Haskell 函數定義 24 

2.3.1  函數定義語法規則 24 

2.3.2  函數定義舉例  26 

2.4  遞歸函數 31 

2.4.1  階乘函數  31 

2.4.2  斐波那契數列  32 

2.4.3  漢諾塔 33 

2.5  模塊 35 

2.5.1  模塊的定義 35 

2.5.2  模塊的使用 35 

2.5.3  查找庫函數 37 

2.6  軟件調試與測試 38 

2.6.1  軟件調試  38 

2.6.2  軟件測試  40 

2.6.3  程序的規格說明  40 

2.6.4  QuickCheck 隨機測試工具 41 

2.7  習題 43 

第 3 章  列表程序設計 47 

3.1  列表的構造  47 

3.1.1  構造函數  47 

3.1.2  列表概括  50 

3.2  圖書借閱管理  52 

3.2.1  借閱卡的數據及其類型  53 

3.2.2  圖書查詢  53 

3.2.3  借閱管理  54 

3.3  超市購物清單  55 

3.3.1  數據類型的設計  55 

3.3.2  屏幕打印函數  56 

3.3.3  打印清單函數  57 

3.4  一個簡單圖形庫 58 

3.4.1  圖形的類型 59 

3.4.2  圖形的顯示 60 

3.4.3  圖形上的運算 60 

3.4.4  圖形模塊及其應用 64

3.5  習題 65 

第 4 章  多態與重載 68 

4.1  多態函數  68 

4.1.1  單態與多態 68 

4.1.2  多態函數舉例  70 

4.2  重載 71 

4.2.1  類族和重載 71 

4.2.2  常用的已定義類族 73 

4.2.3  重載函數舉例   76 

4.3  習題 79 

第 5 章  高階函數 81 

5.1  函數也是數據  81 

5.1.1  map 計算模式   81 

5.1.2  λ 表達式  82 

5.2  常用高階函數  84 

5.2.1  折疊計算模式 foldr 84 

5.2.2  過濾計算模式 filter 85 

5.2.3  前綴處理函數 takeWhile 和 dropWhile 85 

5.2.4  函數的復合 86 

5.2.5  卡瑞化   88 

5.2.6  部分應用  89 

5.3  詞頻統計  89 

5.3.1  問題分析及解決步驟  89 

5.3.2  設計分步函數 90 

5.3.3  步驟的復合 91 

5.4  習題 92 

第 6 章  代數類型 95 

6.1  自定義類型   95 

6.1.1  簡單有窮類型   95 

6.1.2  定義新類型為類族的實例 96 

6.1.3  無窮類型  98 

6.2  數據類型的歸納定義 100 

6.2.1  自定義自然數類型 100 

6.2.2  一個表達式類型  101

6.3  帶類型參數的自定義類型  103 

6.3.1  列表類型的定義  103 

6.3.2  Maybe 類型  104 

6.4  習題 106 

第 7 章  IO 程序  111 

7.1  IO 類型  111 

7.1.1  IO 類型的基本操作  111 

7.1.2  連續動作的表示和 do 語法  113 

7.1.3  使用遞歸實現動作的重復性 115 

7.2  模擬計算  116 

7.2.1  隨機數與猜數遊戲 116 

7.2.2  隨機事件的模擬  119 

7.2.3  識別計算模式   121 

7.2.4  用蒙特卡洛方法估算 π 的近似值  123 

7.2.5  一個簡單猜拳遊戲 125 

7.3  文件讀寫與數據處理 129 

7.3.1  文件讀寫 129 

7.3.2  數據處理 130 

7.4  習題  133 

第 8 章  惰性計算  134 

8.1  惰性計算概述  134 

8.1.1  惰性與嚴格  134 

8.1.2  計算規則 135 

8.1.3  局部定義 136 

8.2  無窮數據結構  137 

8.2.1  斐波那契數列   137 

8.2.2  埃拉托色尼篩法  137 

8.2.3  牛頓-拉森疊代法 138 

8.3  習題   140 

第 9 章  函子與單子 141 

9.1  類型構造函數及其種 141 

9.2  函子 142 

9.2.1  Functor 類族  143 

9.2.2  Functor 的實例  143

9.2.3  函子定律 144 

9.3  Applicative 類族   146 

9.3.1  Applicative 類族及其實例   146 

9.3.2  Applicative 定律 148 

9.4  單子 149 

9.4.1  單子定義和實例  149 

9.4.2  單子的 do 語法  150 

9.4.3  單子定律 151 

9.4.4  單子解釋器   152 

9.5  單子語法分析器 153 

9.5.1  算術表達式定義  154 

9.5.2  語法分析器   154 

9.5.3  基本語法分析器  155 

9.5.4  算術表達式計算器 158 

9.6  習題   159 

附錄 A  GHC 的安裝 161 

A.1  使用 GHCup 工具安裝 161 

A.2  其他安裝方法 161 

附錄 B 部分 Prelude 函數 163 

參考文獻 168 

索引 169