Haskell程序設計基礎

《Haskell程序設計基礎》，喬海燕，周曉聰 著，出版社： 清華大學出版社。

清華大學出版社成立於1980年6月，是教育部主管、清華大學主辦的綜合性大學出版社。清華社現年出版圖書、音像製品、電子出版物等近3000種，銷售規模和綜合實力以及在高等教育教材市場、科技圖書市場、館配圖書市場占有率均名列前茅。

目錄

內容簡介

本書用Haskell 語言從函數式程序設計角度講解計算機程序設計。本書前半部分介紹程序設計的基本內容， 包括數據、類型、函數、遞歸函數、模塊、測試、多態和重載等；後半部分則突出了函數程序設計的特色內容， 包括高階函數、代數類型、惰性計算和單子等。

全書內容編排由淺入深，語言表達清晰準確，每章都提供了難度適中的練習，各章內容都配備講解視頻， 十分便於自學。

本書是為程序設計初學者編寫，可作為高等院校各專業學習程序設計的教材，也可供從事計算機軟件工作 的技術人員學習函數式程序設計參考。

前言/序言

學習程序設計，必須選擇一種高級程序設計語言。不同於其他介紹程序設計入門的一些書籍，本書選擇了Haskell 函數式程序設計語言從函數式程序設計角度介紹程序設計。

高級程序設計語言大致可分為命令式和聲明式兩種。命令式語言如C、Java 和Python 等，這類語言的程序用語句序列描述如何一步步完成一個計算，其特點是有副作用。例如，對於任意正整數n，計算1~n的和1 + 2 + … + n，命令式語言的程序通常形如：

s = 0

for (int i = 1; i <= n; i++)

s = s + i

這裡第一行設置變量s 的初值為0，接下來的循環語句（後兩行）不斷修改變量s 的值，最後s 的值便是計算結果。這種程序重點描述如何計算。

Haskell 函數式語言屬於聲明式語言，這種語言的程序用計算邏輯表達計算，不需要描述計算次序，其特點是無副作用。對於前面的求和問題，在Haskell 語言中可以定義數學函數sum：

sum 0 = 0

sum n = n + sum (n-1)

在這裡，計算1~n之和的Haskell 函數式程序是表達式sum n，sum 是一個純數學函數，n 是數學意義上的變量，沒有副作用。函數式程序重點描述計算什麼。

函數式程序設計語言是建立在計算模型演算上的通用高級程序設計語言。由於它具有更高的抽象層次，更接近於人類習慣的數學思維，因此，更便於初學者理解和掌握。

Haskell 函數式程序設計語言具有下列特點。

（1）程序簡潔優美，語義清晰，容易理解。例如，對於有一定程序設計基礎的程序員，用命令式語言實現快速排序並不容易。然而，下面幾行簡短的Haskell 代碼用列表就表達了快速排序的計算邏輯：

qsort [] = []

qsort (x:xs) = qsort [y|y <- xs, y < x] ++ [x] ++

qsort [y|y <- xs, y >= x]

這裡[] 表示空列表（空序列），(x:xs) 表示非空列表（非空序列），x 是第一個元素，xs 是其餘元素構成的列表，[y|y <- xs, y < x] 表示xs 中小於x 的元素構成的列表，[y|y <- xs, y >= x] 表示xs 中大於或等於x 元素構成的列表，++ 表示將兩個列表串接成一個列表的運算。

（2）純函數無副作用，程序錯誤更少。命令式程序中的函數多為有副作用的「過程」。一個Haskell 純函數的計算結果只與函數的輸入有關，與計算次序無關，由此避免了命令式程序中由副作用引起的一類錯誤。

（3）靜態強類型，確保類型安全。在Haskell 函數中，將一個輸入類型為整數的函數應用於布爾類型是類型錯誤，這種錯誤在編譯過程中可以檢測出來，由此可以避免出現運行時錯誤。因此，類型正確的函數式程序不會出現運行時錯誤。

（4）多態和重載支持代碼重用。Haskell 的參數多態和重載增強了程序的可重用性。例如，qsort 可用於任何類型的列表，只要這種類型支持小於、大於和等於運算即可。

（5）高階函數支持更高抽象性，支持模塊化。在Haskell 語言中，函數是「一等公民」，函數可以是其他函數的輸入和輸出，由此為表達更高層次的計算邏輯提供了支持，也為代碼重用性和模塊化提供了更大的方便。

（6）惰性計算為無窮數據結構提供支持。Haskell 是一種惰性語言，這表明它只有在需要計算時才進行計算，或者只做必要的計算。這種惰性計算允許表達無窮數據結構，由此也為模塊化提供了一種新途徑。

（7）支持和鼓勵形式化驗證。Haskell 函數沒有副作用，因此，可以像對數學表達式那樣對程序進行推理，也可以使用形式化工具驗證其正確性，確保程序的正確性。

本書內容涵蓋函數式程序設計入門的基本知識。第1章簡要介紹程序設計的概念；第2章介紹Haskell 函數式程序設計的基本知識，包括數據、類型、函數、遞歸函數、模塊和測試等基本知識；第3章進一步介紹列表程序設計，包括如何設計一個字符圖形庫；第4章介紹程序設計的多態和重載概念，以及Haskell 處理重載的類族機制；第5章介紹函數式程序設計的重要特性：高階函數，包括常用的map、foldr 和filter 等；第6章介紹如何自定義類型以更準確地表達數據；第7章介紹如何設計交互程序，包括模擬計算和小遊戲；第8章介紹Haskell 語言的惰性計算策略以及惰性計算對模塊劃分的支持，特別是生產者-消費者模式；第9章介紹函數式語言的高級特性函子與單子，包括一個單子語法分析器和一個簡單計算器的實現。

函數式程序設計語言（也簡稱為函數程序設計語言）(①雖然不是主流程序設計語言，但是函數程序設計的概念如表達式、函數對象、map、filter 和reduce 等高階函數已經滲透到各種主流程序設計語言如C++、Java 和Python 中。因此，從函數式程序設計語言入門學習程序設計，無論對初學者還是有基礎的程序員，都將開啟一扇新的程序設計科學的大門。

與其他函數式程序設計書籍相比，本書具有下列特點。

（1）適合初學程序設計的讀者。

（2）內容簡練，由淺入深，適合自學。

（3）本書是立體式教材，與中國大學慕課「Haskell 函數程序設計基礎」配套。

本書能以現在的面貌出版，得益於許多老師和學生的支持。特別感謝裘宗燕教授、宋方敏教授和羅朝暉教授三位專家在百忙之中閱讀本書初稿，並提出了許多中肯的意見！限於作者的水平，本書現在的面貌恐未能達到專家期望的水平，在此作者深表歉意！本書在編寫過程中得到了清華大學出版社白立軍老師和楊帆老師的大力協助，在此一併表示感謝！

本書可作為大中專院校非計算機專業程序設計入門教材，也可作為其他程序設計愛好者的自學教材。

限於作者的水平，書中可能有錯誤和疏漏，敬請讀者不吝指正。

作者

2022 年春於中山大學東校園

( ① 本書將把「函數式程序設計」簡稱為「函數程序設計」，「函數式程序」簡稱為「函數程序」。