14 min to read
CIS 194 01 Introduction to Haskell 簡介 Haskell
Source: 01-intro
▌Haskell 基礎
CIS 194 第 1 週
2013 年 1 月 14 日
建議閱讀：
- Learn You a Haskell for Great Good, chapter 2
- Real World Haskell, chapters 1 and 2
▌什麼是 Haskell ?
Haskell是一種懶惰的函數式編程語言，由學術委員會於 1980 年代後期創建。 周圍有很多 Lasy 惰性的函數式語言，每個人都有自己喜歡的語言，很難交流思想。 因此，一群人聚在一起，設計了一種新的語言，從現有語言中汲取了一些最好的主意（以及他們自己的一些新主意）。 Haskell出生。
那麼 Haskell 是什麼樣的呢？ Haskell 是：
▌Functional 函數式
“函數式” 一詞沒有確切的公認含義。 但是，當我們說 Haskell 是一種函數式語言時，我們通常會想到兩件事：
- 函數是一等的 (first-class)，也就是說，函數是可以與其他任何類型的值完全相同的方式使用的值。
- Haskell 程序的含義集中在 評估表達式 而不是 執行指令上 。
綜上所述，這些導致了對編程的完全不同的思考方式。這個學期我們大部分時間將花在探索這種思維方式上。
▌Pure 純粹
Haskell 表達式始終是參照透明的 (referentially transparent) ，即：
- 沒有突變 (mutation)！一切（變量，數據結構 …）都是不可變的 (immutable) 。
- 表達式永遠不會有 “副作用 (side effects)”（例如更新全局變量或在屏幕上打印）。
- 每次使用相同的參數調用相同的函數都會導致相同的輸出。
這可能聽起來很瘋狂。怎麼可能做任何沒有突變或副作用的事情？好吧，這當然需要轉變思維方式（如果您習慣了命令式或面向對象的範例）。但是，一旦做出了轉變，就會有許多好處：
- 方程式推理和重構：在 Haskell 中，人們總是可以“用 等式 代替 等式 ”，就像您在代數班中學到的一樣
- 並行性：如果保證不影響彼此，則並行評估表達式很容易
- 更少的頭痛 ：簡而言之，不受限制的效果和遠距離動作使程序難以調試，維護和推理
▌Lasy 惰性
在 Haskell 中，只有 在實際需要它們的結果時才對 表達式 求值 。這是一個具有深遠影響的簡單決定，我們將在整個學期中進行探討。一些後果包括：
- 僅通過定義函數就可以輕鬆定義新的 控制結構
- 可以定義和使用 無限的數據結構
- 它啟用了一種更加組合的編程樣式（請參見下面的 Wholemeal programming ）
- 然而，一個主要的缺點是時間和空間使用的推理變得更加複雜！
▌Statically typed 靜態類型
每個 Haskell 表達式都有一個類型，並且所有類型都在 編譯時 檢查。帶有類型錯誤的程序甚至無法編譯，運行更少
▌Themes 主題
在整個課程中，我們將重點關註三個主題
▌Type 類型
靜態類型系統看起來很煩人。實際上，在像 C ++ 和 Java 這樣的語言中，它們 很 煩人。但這並不是因為靜態類型系統 本身 很煩人；這是因為 C ++ 和 Java 的類型系統表現力不足！這個學期，我們將仔細研究 Haskell 的類型系統
-
有助於理清思路並表達程序結構
編寫 Haskell 程序的第一步通常是 寫下所有類型 。因為 Haskell 的類型系統表現力強，所以這是一個不平凡的設計步驟，並且對闡明人們對程序的想法有極大的幫助。
-
用作文件形式
給定一個具有表現力的類型系統，即使您只讀過一個書面文檔，僅查看函數的類型都會告訴您有關函數可能做什麼以及如何使用它的很多信息。
-
將運行時錯誤轉換為編譯時錯誤
能夠預先修復錯誤比僅僅進行大量測試並希望達到最佳效果要好得多。“如果可以編譯，它必須是正確的”在大多數情況下都是滑稽的（即使在類型正確的程序中，邏輯上仍然很可能會出錯），但是在 Haskell 中發生的情況要比其他語言多得多。
▌Abstraction 抽象化
“不要重複自己”(Don’t Repeat Yourself) 是編程界經常聽到的口頭禪。這種想法也被稱為 “抽象原理 (Abstraction Principle)”，它不應重複任何內容：每個想法，算法和數據片段應在代碼中僅出現一次。採用相似的代碼片段並排除它們共同性的過程稱為 抽象 。
Haskell 非常擅長抽象：參數多態性，高階函數和類型類之類的功能都有助於抵抗重複。本學期我們在 Haskell 的旅程很大程度上將是從具體到抽象的旅程。
▌Wholemeal programming
我們將探索的另一個主題是 Wholemeal 編程。拉爾夫 · 欣茲的一句話：
“函數式語言在 Wholemeal 編程方面表現出色，這是 Geraint Jones 創造的一個術語。Wholemeal 程序設計意味著要大膽思考：使用整個列表，而不是元素序列。開發解決方案空間，而不是單個解決方案；想像一個圖，而不是一條路徑。Wholemeal 方法通常會針對特定問題提供新見解或提供新觀點。它與投影編程的思想很好地互補：首先解決一個更通用的問題，然後通過將通用程序轉換成更專業的程序來提取有趣的點點滴滴。”
例如，考慮使用 C / Java 語言的這種偽代碼：
int acc = 0;
for ( int i = 0; i < lst.length; i++ ) {
acc = acc + 3 * lst[i];
}
該代碼被 Richard Bird 稱為 “indexitis”：它必須擔心通過跟踪當前索引來遍歷數組的底層細節。它還將可以更有用地視為兩個單獨的操作混合在一起：將列表中的每個項目乘以3，然後將結果相加。
在 Haskell 中，我們可以寫
sum (map (3*) lst)
本學期，我們將探討這種編程方式所代表的思維方式的轉變，並研究 Haskell 如何以及為何使之成為可能。
▌Literate Haskell
該文件是 “Literate Haskell 文檔”：只有以 > 開頭的行和一個空格（如下所示）才是代碼；其他所有內容（如本段）均為評論。您的編程任務不一定要有 Literate Haskell，儘管您願意也可以。Literate Haskell 文檔的擴展名為 .lhs ，而 non-literate Haskell 源文件使用 .hs 。
▌Declarations and variables 聲明和變量
這是一些 Haskell 代碼：
x :: Int
x = 3
-- Note that normal (non-literate) comments are preceded by two hyphens
{- or enclosed
in curly brace/hyphen pairs. -}
上面的代碼聲明了一個 x 類型為 type 的變量 Int（ :: 發音為“具有類型(has type)”），並聲明了值為 x be 3 。請注意，這將是 x 永遠的值 （至少在此特定程序中）。的值 x 以後不能更改。
嘗試取消註釋下面的行；它會產生一個錯誤，說像 Multiple declarations of 'x'。
-- x = 4
在 Haskell 中，變量不是可變的箱 ；它們只是值的名稱！
換句話說，= 並不像許多其他語言一樣表示 “分配”(assignment) 。相反， = 表示定義，就像在數學中一樣。也就是說，不應將 x = 4 理解為 “ x 得到 4” 或 “將 4 分配給 x”，而應將其理解為 “ x 被 定義為 4 ”。
您認為此代碼意味著什麼？
y :: Int
y = y + 1
▌Basic Types 基本類型
-- Machine-sized integers
i :: Int
i = -78
Haskell 語言標准保證整數 (Int) 可以容納至少 $\pm 2^{29}$ 的值，但是確切的大小取決於您的體系結構。例如，在我的 64 位計算機上，範圍是 $\pm 2^{63}$ 。您可以通過評估以下內容找到機器上的範圍：
biggestInt, smallestInt :: Int
biggestInt = maxBound
smallestInt = minBound
（請注意，慣用的 Haskell camelCase 用於標識符名稱。如果您不喜歡它，那麼運氣不好）
另一方面，Integer 類型僅受計算機內存量的限制
-- Arbitrary-precision integers
n :: Integer
n = 1234567890987654321987340982334987349872349874534
reallyBig :: Integer
reallyBig = 2^(2^(2^(2^2)))
numDigits :: Int
numDigits = length (show reallyBig)
對於浮點數，有 Double：
-- Double-precision floating point
d1, d2 :: Double
d1 = 4.5387
d2 = 6.2831e-4
還有一個單精度浮點數類型 Float
最後，有布爾值，字符和字符串：
-- Booleans
b1, b2 :: Bool
b1 = True
b2 = False
-- Unicode characters
c1, c2, c3 :: Char
c1 = 'x'
c2 = 'Ø'
c3 = 'ダ'
-- Strings are lists of characters with special syntax
s :: String
s = "Hello, Haskell!"
▌GHCi
GHCi 是 GHC 隨附的交互式 Haskell REPL（讀取-評估-打印循環）。 在 GHCi 提示符下，您可以評估表達式，使用 :load（ :l ） 加載 Haskell 文件（並使用 :reload（ :r ）重新加載它們），使用 :type（ :t ）詢問表達式的類型以及許多 其他事情（嘗試 :? 獲得命令列表）
▌Arithmetic 算術
嘗試評估 GHCi 中的以下每個表達式：
ex01 = 3 + 2
ex02 = 19 - 27
ex03 = 2.35 * 8.6
ex04 = 8.7 / 3.1
ex05 = mod 19 3
ex06 = 19 `mod` 3
ex07 = 7 ^ 222
ex08 = (-3) * (-7)
注意 “反引號”(``) 是如何將函數名稱轉換為中綴運算符。還請注意，負數通常必須用括號括起來，以避免將否定符號解析為減法。（是的，這很醜。對不起）
但是，這會導致錯誤：
-- badArith1 = i + n
加法僅在相同數字類型的值之間進行，Haskell 不會進行隱式轉換。您必須顯式轉換為：
fromIntegral：從任何整數類型（Int或Integer）轉換為任何其他數字類型。round,floor,ceiling：轉換浮點數到Int或Integer。
現在嘗試這個：
-- badArith2 = i / i
這是一個錯誤，因為 / 僅執行浮點除法。對於整數除法，我們可以使用 div
ex09 = i `div` i
ex10 = 12 `div` 5
如果您習慣於進行數字類型的隱式轉換的其他語言，那麼一開始這一切似乎都比較謹慎和煩人。但是，我保證您會習慣它，並且隨著時間的流逝，您甚至可能會逐漸體會到它。隱式數字轉換鼓勵草率地考慮數字代碼
▌Boolean logic 布爾邏輯
如您所料，布爾值可以與 (&&)（邏輯和），(||)（邏輯或）和組合 not。例如
ex11 = True && False
ex12 = not (False || True)
可以使用（==）和（/= ）比較事物是否相等，或使用相比，順序(<)，(>)，(<=) 和 (>=)
ex13 = ('a' == 'a')
ex14 = (16 /= 3)
ex15 = (5 > 3) && ('p' <= 'q')
ex16 = "Haskell" > "C++"
Haskell 也具有 if-expressions：如果 b 則 t else f 是一個表達式，如果布爾表達式 b 的值為 True，則計算結果為 t，如果 b 的值為 False，則計算結果為 f。 請注意，if 表達式與 if 語句非常不同。 例如，對於 if 語句，else 部分可以是可選的； 省略的 else 子句的意思是“如果測試結果為 False，則不執行任何操作”。 另一方面，對於 if 表達式，則需要 else 部分，因為 if 表達式必須產生某些值。
慣用的 Haskell 不太使用 if 表達式，通常使用模式匹配或 guards 後衛（請參閱下一節）。
▌Defining basic functions 定義基本函數
我們可以根據情況在整數上編寫函數
-- Compute the sum of the integers from 1 to n.
sumtorial :: Integer -> Integer
sumtorial 0 = 0
sumtorial n = n + sumtorial (n-1)
請注意函數類型的語法： sumtorial :: Integer -> Integer 表示該 sumtorial 函數以 Integer 作為輸入，並產生另一個 Integer 作為輸出
從上到下依次檢查每個子句，然後選擇第一個匹配子句。例如，由於第一個子句已匹配，因此 sumtorial 0 求值為 0。 sumtorial 3 與第一個子句不匹配（ 3 is not 0），因此嘗試第二個子句。像 n 這樣的變量可以匹配所有內容，因此第二個子句匹配並 sumtorial 3 求和 3 + sumtorial (3-1) （然後可以進一步求值）
也可以使用 guards 根據任意布爾表達式進行選擇。例如：
hailstone :: Integer -> Integer
hailstone n
| n `mod` 2 == 0 = n `div` 2
| otherwise = 3*n + 1
函數定義的每個子句都可以關聯任意數量的 guards ，每個 guards 都是一個布爾表達式。如果子句的模式匹配，則按從上到下的順序評估 guards ，並選擇第一個評估為True。如果所有 guards 均不等於True，則匹配繼續進行下一個子句
例如，假設我們評估 hailstone 3 。首先，3 與匹配 n，該匹配成功（因為變量匹配任何東西）。接下來， n mod 2 == 0 進行評估；這是 False 因為 n = 3 不會導致 0 除以時的餘數 2。 otherwise 只是一個方便的同義詞 True ，因此選擇了第二個後衛，因此的結果 hailstone 3 是 3*3 + 1 = 10
作為更複雜（但更人為）的示例：
foo :: Integer -> Integer
foo 0 = 16
foo 1
| "Haskell" > "C++" = 3
| otherwise = 4
foo n
| n < 0 = 0
| n `mod` 17 == 2 = -43
| otherwise = n + 3
什麼是foo (-3) ？ foo 0？foo 1？foo 36？foo 38？
作為關於布爾表達式和 guards 的最後說明，假設我們想抽象定義 hailstone 中使用的偶數測試 。第一次嘗試如下所示：
isEven :: Integer -> Bool
isEven n
| n `mod` 2 == 0 = True
| otherwise = False
這 有效 ，但是太複雜了。你知道為什麼嗎？
▌Pairs 對
我們可以將事物配對在一起，如下所示：
p :: (Int, Char)
p = (3, 'x')
注意，該 (x,y) 符號用於對 類型 和對的值。
可以使用 模式匹配 再次提取一對元素：
sumPair :: (Int,Int) -> Int
sumPair (x,y) = x + y
Haskell 也有三元組，四元組 ……，但是您永遠不要使用它們。我們將在下週看到，有更好的方法將三個或更多信息打包在一起
▌Using functions, and multiple arguments
使用函數和多個參數
要將函數應用於某些參數，只需在函數後列出參數，並用空格分隔即可，如下所示：
f :: Int -> Int -> Int -> Int
f x y z = x + y + z
ex17 = f 3 17 8
上述示例中的函數應用 f 到三個參數 3，17 和 8 。還要注意具有多個參數的函數類型的語法，例如 Arg1Type -> Arg2Type -> ... -> ResultType 。這對您來說似乎很奇怪（應該！）。為什麼所有的箭頭？f 像這樣的類型會更有意義 Int Int Int -> Int 嗎？實際上，語法絕非偶然：這是出於非常深刻而美麗的原因而產生的方式，我們將在幾週後了解到。現在，您只需相信我的話！
請注意，函數應用程序的優先級高於任何中綴運算符。所以寫是不正確的
f 3 n+1 7
如果您打算將 n+1 作為第二個參數傳遞給 f，因為它解析為
(f 3 n) + (1 7)
相反，必須寫
f 3 (n+1) 7
▌Lists 列表
列表 是 Haskell 中最基本的數據類型之一。
nums, range, range2 :: [Integer]
nums = [1,2,3,19]
range = [1..100]
range2 = [2,4..100]
Haskell （如 Python）也具有列表理解能力 ；您可以在 LYAH中 閱讀有關它們的 信息
字符串只是字符列表。也就是說， String 它只是的縮寫 [Char] ，而字符串文字語法（文本用雙引號引起來）只是一系列 Char 文字的縮寫
-- hello1 and hello2 are exactly the same.
hello1 :: [Char]
hello1 = ['h', 'e', 'l', 'l', 'o']
hello2 :: String
hello2 = "hello"
helloSame = hello1 == hello2
這意味著用於處理列表的所有標準庫函數也可以用於處理 String
▌Constructing lists 構造列表
最簡單的列表是空列表：
emptyList = []
其他列表是使用 cons 運算符從空列表中構建的 (:)。Cons 接受一個元素和一個列表，並產生一個新列表，該元素位於前面
ex18 = 1 : []
ex19 = 3 : (1 : [])
ex20 = 2 : 3 : 4 : []
ex21 = [2,3,4] == 2 : 3 : 4 : []
我們可以看到，[2,3,4] 符號只是的方便速記 2 : 3 : 4 : []。還要注意，這些實際上是 單鍊錶 ，而不是數組
-- Generate the sequence of hailstone iterations from a starting number.
hailstoneSeq :: Integer -> [Integer]
hailstoneSeq 1 = [1]
hailstoneSeq n = n : hailstoneSeq (hailstone n)
當到達1時，我們停止 hailstoneSeq。一般 n 的 hailstoneSeq 由 n 本身組成，然後是 hailstone n 的hailstoneSeq，即通過對 n 進行一次 hailstone 變換而獲得的數字
▌Functions on lists 列表中的函數
我們可以使用 模式匹配 在列表上編寫函數。
-- Compute the length of a list of Integers.
intListLength :: [Integer] -> Integer
intListLength [] = 0
intListLength (x:xs) = 1 + intListLength xs
第一個子句說一個空列表的長度是 0。第二個子句說如果輸入列表看起來像 (x:xs) ，即第一個元素被x約束在剩餘的列表上 xs ，那麼該長度比的長度大一個 xs
由於我們根本不使用 x ，因此也可以用下劃線代替：intListLength (_:xs) = 1 + intListLength xs
我們還可以使用嵌套模式：
sumEveryTwo :: [Integer] -> [Integer]
sumEveryTwo [] = [] -- Do nothing to the empty list
sumEveryTwo (x:[]) = [x] -- Do nothing to lists with a single element
sumEveryTwo (x:(y:zs)) = (x + y) : sumEveryTwo zs
請注意last子句如何匹配 x 以 … 開頭 y 和後跟的列表 … 以。開頭和後跟的列表 zs。我們實際上不需要多餘的括號，因此 sumEveryTwo (x:y:zs) = ... 是等效的
▌Combining functions 組合函數
通過組合許多簡單功能來構建更複雜的功能是一種很好的 Haskell 風格。
-- The number of hailstone steps needed to reach 1 from a starting
-- number.
hailstoneLen :: Integer -> Integer
hailstoneLen n = intListLength (hailstoneSeq n) - 1
這對您來說似乎效率低下：它先生成整個 hailstone 序列，然後找到其長度，這會浪費大量內存 …… 不是嗎？實際上，事實並非如此！由於 Haskell 的惰性計算，僅根據需要生成序列的每個元素，因此對序列生成和列表長度計算進行了交錯。無論序列多長時間，整個計算僅使用 O(1) 內存。（實際上，這是一個很小的謊言，但要解釋為什麼（以及如何解決）將需要等待幾週。）
我們將在幾週內進一步了解 Haskell 的惰性評估策略。目前，要傳達的信息是：不要害怕寫一些小的函數來轉換整個數據結構，並將它們組合起來以產生更複雜的函數。剛開始時可能會感覺不自然，但這是編寫慣用的（高效的）Haskell 的方法，並且實際上是一種習慣後就很容易編寫程序的方法。
▌A word about error messages 關於錯誤消息的一句話
實際上，有六個：
不要害怕錯誤消息！
GHC 的錯誤消息可能會很長，並且（似乎）令人恐懼。但是，通常它們長久以來並不是因為它們晦澀難懂，而是因為它們包含了大量有用的信息！這是一個例子：
Prelude> 'x' ++ "foo"
<interactive>:1:1:
Couldn't match expected type `[a0]' with actual type `Char'
In the first argument of `(++)', namely 'x'
In the expression: 'x' ++ "foo"
In an equation for `it': it = 'x' ++ "foo"
首先，我們被告知 “無法將預期類型 [a0] 與實際類型匹配 Char”。這意味著某些東西 應該具有列表類型，而實際上卻具有 type Char。什麼事 下一行告訴我們：它的第一個參數有 (++) 誤，即 'x'。接下來的幾行繼續為我們提供了更多背景信息。現在我們可以看到問題所在：正如第一行所說，顯然 'x' 具有 type Char。為什麼會期望它具有列表類型？好吧，因為它用作的參數 (++) ，它以列表作為第一個參數。
當您收到大量錯誤消息時，請抵制您最初的衝動逃跑；深吸一口氣；並仔細閱讀。您不一定會了解整個事情，但是您可能會學到很多東西，並且您可能只會獲得足夠的信息來找出問題所在。
