Haskell/可打印版本

維基教科書,自由的教學讀本


Table Of Contents

Haskell基礎

起步
變量和函數
列表和元組
更進一步
類型基礎
簡單的輸入輸出
類型聲明

初級Haskell

遞歸
模式匹配
深入列表
控制結構
列表處理
深入函數
高階函數

Haskell進階

模塊
縮進
更多數據類型
類的聲明
類與類型
保持狀態記錄

Monads

理解 Monad
高級 Monad
Monad 進階
MonadPlus
Monadic parser combinators
Monad transformers
Monad 實務

高級Haskell

Monoid類型類
Applicative類型類
箭頭
理解箭頭
Foldable類型類
Traversable類型類
延續過渡風格(CPS)
可變對象
拉鏈
適用函子
獨異點
Lens 和引用
並行

類型的樂趣

多形性基礎
存在性類型
高級類型類
幻影類型
通用代數數據類型
數據類型代數學

理論提升

指稱語義
Equational reasoning
Program derivation
Category theory
The Curry-Howard isomorphism
fix 和遞歸

Haskell性能

Introduction
Step by Step Examples
Graph reduction
Laziness
Strictness
Algorithm complexity
Data structures
Parallelism

程序庫參考

The Hierarchical Libraries
Lists:Arrays:Maybe:Maps
IO:Random Numbers

普通實務

構建一個獨立的應用
除錯
測試
打包你的程序
使用外部程序接口

專門任務

圖形用戶界面
數據庫
網絡編程
使用XML
使用正則表達式

Haskell基礎


起步

本章節展示了如何安裝軟件,以便讓你用 Haskell 編寫程序。

安裝Haskell

Haskell 是一種程式語言,表達人類如何讓計算機工作。類似寫菜譜,人來寫而計算機負責烹調。

要運行 Haskell 編寫的程序,首先,你需要一個 Haskell 編譯器。編譯器是一種電腦程式,將 Haskell 代碼變成機器碼,而電腦能理解機器碼。照上頭的比喻來說的話,編譯器就是把麵糊(程式碼)轉化為餅乾(可執行檔)的烤爐,而在經過烘烤後,要得知原來的食譜是困難的。

下載並安裝 Haskell platform,它包含 Glasgow Haskell Compiler(縮寫:GHC)與其他所需組件。

如果你只是想試試 Haskell,或者不願意完整地安裝編譯器,你可能會喜歡 Hugs,Haskell的輕量級可攜式直譯器,或 TryHaskell,一個線上直譯器。值得注意的是本課程假定你使用的是 GHC。

註解

給 UNIX 用戶:

如果你是想編譯源碼的人:這對於 GHC 來說是一個壞主意, 特別是如果你是第一次安裝。GHC 本身幾乎全部使用 Haskell 編寫,所以試着手工從源碼引導它的編譯是非常麻煩的。除此之外,編譯會消耗大量時間並且消耗大量磁盤空間。如果你堅持從源碼編譯 GHC,參見GHC主頁上的「編譯和移植GHC」.

簡而言之,我們強烈建議安裝 Haskell platform 而非從源碼編譯。

第一步

在 Haskell Platform 安裝完畢後,現在可以開始寫第一份 Haskell 代碼了。 需要使用一個叫做GHCi(i代表交互式,interactive)。根據不同的作業系統,進行以下操作

  • Windows:『開始』菜單,然後『運行』,輸入 cmd 並回車,輸入 ghci 後再次回車
  • MacOS:打開在『應用程式/實用工具』中的『終端』,在新打開的窗口中輸入 ghci 並按回車
  • Linux:打開一個終端(或模擬器)然後運行 ghci 程序

你會看到類似於下面的界面:

GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Prelude>

首先看到的是 GHCi 的版本號。然後提示你正在載入基本包,可以通過 :?help 命令查找幫助。最後的 Prelude> 就是提示符了。你可以在這之後輸入命令,GHCi 會立刻把計算出來的結果顯示出來。

現在可以開始寫第一份 Haskell 代碼了,讓我們先來試一試一些基本的算術功能:

Prelude> 2 + 2
4
Prelude> 5 + 4 * 3
17
Prelude> 2 ^ 5
32

這些運算符和其它程式語言中是大致相同的:+ 是加法,* 是乘法,^ 是乘方。由第二個例子,我們能看出 Haskell 遵守一般的運算子優先順位。

現在我們已經知道如何把 Haskell 當作計算器使用,Haskell 語言中的關鍵點在於,它總是像計算器,當我們不僅僅計算數字,而是與其他像字符、列表、函數、樹甚至其他程序等對象來使用時便顯得更加強大(如果你現在還不熟悉,用不着擔心)。

如果你想關閉解釋器 GHCi,可以使用 :quit (或者 :q):

Prelude> :quit
Leaving GHCi.

GHCi 是一個非常強大的開發平台。隨着課程的進行,我們會學到如何在 GHCi 中載入源文件,並計算其中不同的部分。

下一章節,我們會介紹 Haskell 基本概念。然後會寫我們第一個函數。



可打印版本
Haskell基礎

起步  >> 變量和函數  >> 列表和元組  >> 更進一步  >> 類型基礎  >> 簡單的輸入輸出  >> 類型聲明


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務


變量和函數

(本章的所有例子都可以寫進Haskell原始碼文件並利用GHC或Hugs加載進行求值運算。請注意不要輸入開頭的提示符,如果代碼前面有提示符,可以在GHCi等環境中輸入;如果沒有,則寫進文件再運行。)

變量

我們已經了解如何把GHCi當作計算器來使用,當然只是極其簡短的例子。對於更長的計算以及Haskell程序而言,需要對運算的中間結果進行追蹤。

中間結果可以存入變量,通過名字來訪問。一個變量包含一個,當使用變數時,變數內的值會被代入。舉個例子,請考慮以下情況

ghci> 3.1416 * 5^2
78.53999999999999

在前一章節中,我們知道了如何做像加法和減法這樣的算術運算。提問:半徑是5厘米的圓的面積是多少?別擔心,你並不是錯看了幾何課本。這個圓的面積是,其中是半徑(5厘米),簡單地說就是。那麼,讓我們在GHCi中試一下吧:

   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.4.1, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base-1.0 ... linking ... done.
Prelude>

我們要把pi(3.14)乘以半徑的平方,那就這樣

Prelude> 3.14 * 5^2
78.5

太棒了!我們讓這台奇妙而又偉大的計算機幫我們計算出了我們想要的結果。但我們不想pi僅僅保留2位小數。那麼就讓我們再試一次,這次pi變得有點長。

Prelude> 3.14159265358979323846264338327950 * (5 ^ 2)
78.53981633974483

很好,這次我們來計算一下圓的周長(提示:)。

Prelude> 2 * 3.14159265358979323846264338327950 * 5
31.41592653589793

那麼半徑是25的圓的面積呢?

Prelude> 3.14159265358979323846264338327950 * (25 ^ 2)
1963.4954084936207

我們遲早會厭倦把上述代碼一遍又一遍的輸入(或拷貝粘貼)的。如我們所言,編程的目的就是擺脫類似於把pi的前20位輸入一億遍這樣愚蠢、乏味的重複勞動。我們要做的就是讓解釋器記住pi的值:

Prelude> let pi = 3.14159265358979323846264338327950
註解

如果這條命令沒用的話,你可能使用的是hugs而不是GHCi,hugs的語法有一點不同。

這裏你就告訴了Haskell:「讓pi等於3.14159……」。這裏引入了一個新的變量pi,它被定義為一個數字3.14159265358979323846264338327950。這樣就變得非常方便了,我們只要再次輸入pi就可以了:

Prelude> pi
3.141592653589793

別在意那些丟失的小數位,他們僅僅是不顯示罷了。所有這些小數位都會在將來的計算中被使用到的。

有了變量,事情就變得輕鬆了。半徑是5厘米的圓的面積是多少呢?半徑是25厘米的呢?

Prelude> pi * 5^2
78.53981633974483
Prelude> pi * 25^2
1963.4954084936207
註解

我們這裏所說的「變量」("variables"),在其它函數式編程的書籍中經常被叫做是「符號」("symbols")。那是因為在其它的語言中,也就是命令式語言中,變量被賦予了完全不同的使用方式:跟蹤狀態(keeping track of state)。在Haskell中的變量不是這樣的:變量保存了一個值,然後再也不可以修改它了。

類型

按照上面的示例,你可能會想把半徑保存在一個變量里。讓我們看看會發生什麼吧!

Prelude> let r = 25
Prelude> 2 * pi * r

<interactive>:1:9:
    Couldn't match `Double' against `Integer'
      Expected type: Double
      Inferred type: Integer
    In the second argument of `(*)', namely `r'
    In the definition of `it': it = (2 * pi) * r

怎麼回事!這裏,你遇到了程序設計上的一個概念:類型(types)。類型是許多程式語言都有的一個特性,它被設計用來在你自己發現之前,儘早的捕獲程序設計上的錯誤。我們將在之後的類型基礎詳細討論型別,現在讓我們把它想像成插頭和插座。例如,計算機背後的不同功能的插頭被設計成不同的形狀和大小,這樣你就不必擔心插錯插頭了。類型也有着類似的目的,但是在這個特殊的例子裏,類型好像不怎麼有用啊。

這裏的詭異之處在於,像25這樣的數字會被解釋成Double(雙精度浮點型)或Integer(整型),或者可能是其它類型。由於缺少必要的信息,Haskell「猜測」它的類型是Integer(它不能和一個Double型別的數字相乘)。為了解決這個問題,我們只需簡單的強調一下,把它作為Double就可以了。

Prelude> let r = 25 :: Double
Prelude> 2 * pi * r
157.07963267948966

請注意,Haskell的這裏「猜測」只會發生在當它缺乏足夠的信息來推斷出型別的時候。下面我們會看到,在大多數情況下,Haskell是能夠根據上下文的信息來作出推斷的。也就是說,是否把一個數字作為Integer,或是其它型別。

註解

事實上在這個難題背後有一點點微妙。它涉及一個叫作單一同態限定(monomorphism restriction)的語言特性。事實上現在你不需要知道這個,所以如果只想快一點你可以跳過這條提示。除了指定Double類型,你也可以給它一個多態(polymorphic)類型,像Num a => a,意思是"屬於Num類的任意類型a"。示例代碼如下,它們運行起來像先前的代碼一樣:

Prelude> let r = 25 :: Num a => a
Prelude> 2 * pi * r
157.07963267948966

Haskell可以從理論上系統地指定這樣的多態類型,而不是做缺省的存在潛在錯誤的猜測,比如整數。但在現實世界,這可能導致數值被不必要地複製或重複計算。要避免這個潛在的陷阱,Haskell的設計者贊同更謹慎的「單一同態限定」。這意味着如果可以從上下文推斷出來,或者你明確指定了一個,那麼數值只能有一個多態類型。否則編譯器會強制選擇一個默認的單一同態(也就是非多態)類型。無論如何,這個特性是有爭議的。甚至可以使用GHC參數(-fno-monomorphism-restriction)來禁用它,但是這帶來了一些低效率的風險。除此之外,多數情況下它就像明確指定類型一樣容易。


變量中的變量

變量不僅可以保存像3.14這樣的數值,還可以保存任何Haskell表達式。那麼,為了方便的表達半徑是5的圓的面積,我們可以寫如下代碼:

Prelude> let area = pi * 5^2

多麼有意思啊,我們在一個變量裏面保存了一個複雜的Haskell程序塊(一個包含變量的算術表達式)。

我們可以在變量裏面保存任意的Haskell代碼。那麼,讓我們繼續吧!

Prelude> let r = 25.0
Prelude> let area2 = pi * r ^ 2
Prelude> area2
1963.4954084936207

到現在為止,一直都還不錯。

Prelude> let r = 2.0
Prelude> area2
1963.4954084936207
變量不可以被修改

等一下,怎麼不對?為什麼我們改了半徑,面積還是原來的結果?原因就是Haskell里的變量是不可以被修改的[1]。在你第二次定義r的時候,實際上,操作的是另一個r。這種事情在現實生活中也經常碰到。名字叫John的人有多少呢?很多人名字都會是John。當你向朋友們提起「John」的時候,你朋友會根據當時的情況知道到底是哪一個John。在程序設計上也有類似於「當時的情況」這樣的概念:作用域。我們並不在這裏解釋作用域(至少現在不)。Haskell作用域的詭異之處在於可以定義兩個不同的r,而總能取用正確的那個。遺憾的是,作用域並沒有解決當前的問題。我們要的是定義一個通用的area函數,來告訴我們圓的面積。我們現在能做的,只能把它再定義一遍:

Prelude> let area3 = pi * r ^ 2
Prelude> area3
12.566370614359172

我們是程式設計師,程式設計師是討厭重複勞動的。有更好的解決方法嗎?

函數

我們為了完成一個通用的求面積功能,其實就是定義一個函數。就如同定義一個變量那樣,在Haskell中定義一個函數十分的簡單。不同之處在於等號的左邊有一些額外的東西。例如,下面我們定義一個pi,接着就是面積函數area:

Prelude> let pi = 3.14159265358979323846264338327950
Prelude> let area r = pi * r ^ 2

要計算兩個圓的面積,只要把不同的半徑傳入就可以了:

Prelude> area 5
78.53981633974483
Prelude> area 25
1963.4954084936207

函數的出現使得我們對代碼的重用方面有了極大的飛躍。先等一下,讓我們來剖析一下上面事物的本質。注意到area r = ...中的r了嗎?這就是所謂的參數。參數用來表示一個函數的輸入。當Haskell在執行這個函數的時候,參數的值是來自於外部的。在area這個例子中,當你調用area 5的時候,r5,而調用area 25的時候,r25.

練習

在Haskell中輸入如下代碼:(先不要在解釋器中輸入)

Prelude> let r = 0
Prelude> let area r = pi * r ^ 2
Prelude> area 5
  1. 你認為會發生什麼?
  2. 實際發生了什麼為什麼(提示:記得以前我們提過的「作用域」嗎?))

作用域和參數

警告:此章節包含上面練習的一些信息

我們希望你完成上面那個小小的練習(也可說是一個實驗)。那麼,下面的代碼並不會讓你出乎意料:

Prelude> let r = 0
Prelude> let area r = pi * r ^ 2
Prelude> area 5
78.53981633974483

你可能認為會得到一個0,但結果出乎你的預料。原因就上我們上面所說的,一個命名參數的值是你調用這個函數時傳入的。那就是我們的老朋友,作用域。let r = 0中的r和我們定義的函數area中的r,並不是同一個r。在area中的r覆蓋了其它的r。你可以認為Haskell選取了一個最近的一個r。如果你有很多朋友都叫John,那麼和你在一起的那個John就是你在說話中提到的那個Jonh。類似的,r的值是什麼取決於作用域。

多重參數

關於函數你也許應該知道另一項知識。那就是,函數可以接受一個以上的參數。例如,你想要計算一個矩形的面積。這很容易表達:

Prelude> let areaRect l w = l * w
Prelude> areaRect 5 10
50

又或者你想要計算一個直角三角形的面積

Prelude> let areaTriangle b h = (b * h) / 2
Prelude> areaTriangle 3 9
13.5

參數傳入的方式很直接:只需要根據和定義時一樣的順序傳入參數就可以了。因此,areaTriangle 3 9會給出底為3而高為9的三角形面積,而areaTriangle 9 3將給出底為9而高為3的三角形面積。

練習
寫一個計算立方體體積的函數。立方體有長、寬、高。把它們乘起來就可以了。


函數中的函數

我們可以在其他函數的內部調用函數以進一步刪減重複的數量。一個簡單的例子將用於展示怎樣利用這些創建一個計算正方形面積的函數。我們都知道正方形是矩形的一個特殊情況(面積仍然是寬乘以長);然而,我們知道它的寬和長是相同的,因此為什麼我們需要鍵入兩次呢?

Prelude> let areaRect l w = l * w
Prelude> let areaSquare s = areaRect s s
Prelude> areaSquare 5
25
練習
編寫一個計算圓柱體體積的函數. 圓柱體的體積是圓形底的面積 (你已經在這章編寫了這個函數, 所以重新利用它) 乘以高.

總結

  1. 變量保存着值。其實,他們可以保存任意的Haskell表達式。
  2. 變量不可以改變。
  3. 函數可以幫助你編寫可重複利用的代碼。
  4. 函數可以接受一個以上的參數。

註釋

  1. 依據讀者以前的編程經驗:變量不可以改變?我只能得到常量?震驚!恐怖!不……相信我們,我們希望在這本書的剩下部分給你說明,不改變一個單一的變量對你大有幫助!事實上,這些不能改變的變量可以使生活更加方便,因為它可以使程序變得更加可以預測。



可打印版本
習題解答
Haskell基礎

起步  >> 變量和函數  >> 列表和元組  >> 更進一步  >> 類型基礎  >> 簡單的輸入輸出  >> 類型聲明


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務


列表和元組

列表和元組是把多個值融為單個值的兩種方法

列表

函數式編程程式設計師的下一個好友

上一章我們介紹了Haskell變量和函數的概念。 在Haskell程序中,函數是兩個主要的構成塊之一。另一個則是通用列表。那麼乾脆,我們切換到解釋器里,並創建一些列表:

例子 - 在解釋器中創建列表

Prelude> let numbers = [1,2,3,4]
Prelude> let truths  = [True, False, False]
Prelude> let strings = ["here", "are", "some", "strings"]

方括號指出列表的開始和結束,逗號操作符","分隔列表元素。另外,列表元素必須是同一類型。因此, [42, "life, universe and everything else"] 不是一個正確的列表,因為它包含了兩種不同類型的元素,也就分別是整型和字符串型。而 [12, 80] 或者, ["beer", "sandwiches"] 都是合法的列表,因為他們都是單一類型的。

如果定義一個含有多個類型元素的列表,就會發生這樣的錯誤:

Prelude> let mixed = [True, "bonjour"]

<interactive>:1:19:
    Couldn't match `Bool' against `[Char]'
      Expected type: Bool
      Inferred type: [Char]
    In the list element: "bonjour"
    In the definition of `mixed': mixed = [True, "bonjour"]

如果你對列表和類型感到困惑,不用擔心。我們還沒有太多地討論到類型,我們相信在以後的章節你會明白。

創建列表

方括號與逗號並不是創建列表的唯一方式。使用(:)cons操作符,你可以逐步地把數據附加(consing[1])到一個列表上,從而創建另一個列表。

Example
Example

例子: 把數據附加(Cons)到列表

Prelude> let numbers = [1,2,3,4]
Prelude> numbers
[1,2,3,4]
Prelude> 0:numbers
[0,1,2,3,4]


當你附加數據到列表(something:someList)時,你得到的是另一個列表。那麼,毫無懸念,這種構建方式是可以複合的。

Example
Example

例子: 附加(Cons)

Prelude> 1:0:numbers
[1,0,1,2,3,4]
Prelude> 2:1:0:numbers
[2,1,0,1,2,3,4]
Prelude> 5:4:3:2:1:0:numbers
[5,4,3,2,1,0,1,2,3,4]


事實上所有的列表都是在一個空的列表([])的基礎上通過附加數據創建的。逗號與方括號的記法實際上是一種語法糖般的令人愉快的形式。 換句話說,[1,2,3,4,5]精確地等同於1:2:3:4:5:[]

你需要留意一類形如1:2的錯誤,你會得到如下錯誤。

Example
Example

例子: Whoops!

Prelude> 1:2

<interactive>:1:2:
    No instance for (Num [a])
      arising from the literal `2' at <interactive>:1:2
    Probable fix: add an instance declaration for (Num [a])
    In the second argument of `(:)', namely `2'
    In the definition of `it': it = 1 : 2


再一個例子True:False,但仍然錯誤

Example
Example

例子: 更簡單但仍然錯誤

Prelude> True:False

<interactive>:1:5:
    Couldn't match `[Bool]' against `Bool'
      Expected type: [Bool]
      Inferred type: Bool
    In the second argument of `(:)', namely `False'
    In the definition of `it': it = True : False


可以看到(:)cons構建適用於something:someList這種形式,但當我們將其使用於something:somethingElse形式下時它就不適用了。可以看到(:)cons是如何依賴於列表的。 在這裏我們開始接觸到類型的概念。讓我們來總結一下:

  • 列表中的元素必須有相同的類型
  • 只能附加(cons)數據到一個列表上

類型是不是很煩人?確實,但是我們可以從Haskell/類型基礎可以看到它也可以為我們節約時間。當你以後使用Haskell編程時遇到了錯誤,你會習慣想到這很可能是一個類型錯誤。

練習
  1. 如下Haskell是否正確: 3:[True,False]?為什麼?
  2. 寫一個函數cons88添加到一個列表中。並進行如下測試:
    1. cons8 []
    2. cons8 [1,2,3]
    3. cons8 [True,False]
    4. let foo = cons8 [1,2,3]
    5. cons8 foo
  3. 寫一個有兩個參數的函數,一個參數為list,另一個為thing,把thing附加到list。你可以這樣開始let myCons list thing =

列表組成的列表

列表可以包含任意數據,只要它們都屬於同一種類型。那麼,接下來思考這樣一個問題:列表也是數據,所以,列表可以包含……是的的確,其它列表!在解釋器上嘗試以下語句:

Example
Example

例子: 列表可以包含列表

Prelude> let listOfLists = [[1,2],[3,4],[5,6]] 
Prelude> listOfLists
[[1,2],[3,4],[5,6]]


有時列表組成的列表可能相當狡猾,因為一個列表所包含的單個數據並不和這個列表自身同屬一種數據類型。讓我們用幾個練習來說明這個概念:

練習
  1. 下列哪些是正確的Haskell表達式,哪些不是?用cons記法重寫。
    1. [1,2,3,[]]
    2. [1,[2,3],4]
    3. [[1,2,3],[]]
  2. 下列哪些是正確的Haskell表達式,哪些不是?用逗號和方括號記法重寫。
    1. []:[[1,2,3],[4,5,6]]
    2. []:[]
    3. []:[]:[]
    4. [1]:[]:[]
  3. Haskell中可以創建包含由列表組成的列表的列表嗎?為什麼能或者為什麼不能?
  4. 下面的列表為什麼不正確?如果你還不能回答不要太煩惱。
    1. [[1,2],3,[4,5]]

列表組成的列表極其有用,因為它們允許你表達一些非常複雜的、結構化的數據(例如二維矩陣)。它們也是Haskell類型系統中眾多真正的閃光點之一。人類程式設計師,或者至少這本Wikibook的作者,在使用列表組成的列表時,總是變得困惑;同時,有限制的類型經常幫助我們艱難地通過這些潛在的困難。

元組

另一種多值記法

元組是另一種把多個值儲存到一個值的方式,但是它們與列表在某些方面有一些精巧的差異。若你事先知道你要儲存多少個值為一組元組是十分有用的,其次元組對其中每一個值是分別進行類型限制的。舉些例子,我們想用一個類型來表達平面坐標,現在我們知道要儲存的值的個數為兩個(xy),所以在這個例子中可以使用元組來儲存平面坐標。或者,我們要寫一個電話本程序,我們可以把某人的名字,電話號碼以及地址儲存到一個元組中。在第二個例子中,我們同樣知道我們需要儲存三個值為一組。儘管三個值的類型不盡相同,但元組對其中值的類型沒有同一性的要求。

讓我們看一下這些元組樣本。

Example
Example

例子: 一些元組

(True, 1)
("Hello world", False)
(4, 5, "Six", True, 'b')


第一個例子是一個有兩個元素的元組,第一個元素是True第二個是1。第二個例子同樣是一個有兩個元素的元組,第一個是"Hello world"第二個是False。第三個例子比較複雜,這個元組有五個元素,第一個是數字4,第二個是數字5,第三個是"Six",第四個是True,最後一個是字母'b'。元組的組成就是用逗號吧各個元素分開,兩端圍上圓括號。

術語:若元組的長度為n則稱其為n-tuple。特殊地如果元組的長度為2則稱其為'pairs'(對),如果元組的長度為3則稱其為'triples'。

元組跟列表有一點是相似的,就是它們都能儲存多個值。但是,很重要的一點,不同長度的元組的類型是不一樣的。雖然這裏再次提及類型這個概念,一個你可能還不清楚的概念,但是可以看到列表跟元組對待自身長度的方式是不一樣的。換一種說法,如果對一個由數字組成的列表添加一個新的數字,它依然是一個列表。但是如果你往一個長度為2的元組中添加一個元素,則你得到了一個完全不同的元組[2]

練習
  1. 寫一個 3-tuple 第一個元素為 4, 第二個元素為 "hello" , 第三個元素為 True。
  2. 以下哪幾個是元組 ?
    1. (4, 4)
    2. (4, "hello")
    3. (True, "Blah", "foo")
  3. 往一個列表堆疊(consing)新的元素: 你可以往一個數字列表添加數字,得到一個數字列表,但是元組是沒有這種堆疊方法的。
    1. 你是怎樣理解的?
    2. 討論:如果有一個函數可以對元組進行堆疊,堆疊後得到的是什麼?

元組有何用途?

當你想在某個函數中返回多個值的時候,元組很好使。在大多數語言中,返回多個值意味着那些值必須被封裝成一種特殊的數據結構,而這種數據結構也許僅僅就在這個函數中使用一次(這種情況下顯得有點浪費)。 在Haskell中,僅僅需要返回一個元組就夠了。

Haskell記錄常常達到同樣的目的,但是你將不得不指定元素的名字。我們將在接下來的學習中與記錄不期而遇。

你也可將元組視為一種原子數據結構。 這需要對類型有所了解,而到我們還沒說到那。

從元組中取出數據

在本節中,我們的注意力將僅僅集中在包含2個元素的元組上。雖然這主要是為了簡化,但2個元素的元組確實是被使用最多的一種元組。

好的,我們已經看到,簡單地使用(x, y, z)語法,可以把數值放進元組。我們怎樣再把它們取出來?例如,元組的一個典型用途是儲存一個點的(x, y)坐標:想像你有一個棋盤,而你想要指定一個特定的方格。你可以通過給所有的行打上從1到8的標籤來做到,列同理,然後說,(2, 5)代表第2行第5列。我們要定義一個能找出一個給定列中所有點的函數。方法之一是找到所有點的坐標,然後看行部分是否等於我們要找的行。一旦有了一個點的坐標(x, y),這個函數將需要提取x(行部分)。這裏有兩個函數可以做到,fstsnd,它們分別「投影」出一個對中的第一和第二個元素(用數學語言來說,從結構體中取出數據的函數叫做「投影」(Projection))。讓我們來看一些例子:

Example
Example

例子: 使用fstsnd

Prelude> fst (2, 5)
2
Prelude> fst (True, "boo")
True
Prelude> snd (5, "Hello")
"Hello"


以上函數的功能容易明白。但是要注意的是fstsnd只能使用到長度為2的元組中。[3]

練習
  1. 使用fstsnd的組合將4從(("Hello", 4), True)中取出。
  2. 思考列表 [(4, 'a'),(5,'b')] 與 列表 [(4, 1),(5, 2)] 之間的區別。

將元素從元組中取出的通用技巧是模式匹配(是的,由於這是一個函數式編程的出眾特徵,我們過些時候將深入討論)。為避免使事情比原本的更複雜,讓我們僅僅向你展示我怎麼寫一個和fst有同樣功能、命名為first的函數:

Example
Example

例子: first的定義

 Prelude> let first (x, y) = x
 Prelude> first (3, True) 
 3


這就是說如果輸入(x, y)first (x, y)會返回x

元組組成的元組(以及其它組合)

我們可以像在列表中儲存列表一樣來操作元組。元組也是數據,所以你可以在元組中儲存元組(嵌套在元組中直到任意複雜的級別)。同樣,你也可以創建元組組成的列表,列表組成的元組,以下例子的每一行分別表達了一中不同的組合方法。

Example
Example

例子: 嵌入元組和列表

((2,3), True)
((2,3), [2,3])
[(1,2), (3,4), (5,6)]


一些相關討論——你更應該從中看到數據分組的重要思想

無論如何,這裏還有一個難點需要當心。決定元組類型的不僅有它的大小,還有它其中所包含的元素的類型。例如,("Hello",32)(47,"World")是完全不同的兩個類型。一個是(String,Int)類型的元組,然而另一個是(Int,String)。因此我們在構造包含元組的列表時,只能構建形如[("a",1),("b",9),("c",9)]這樣的列表,而[("a",1),(2,"b"),(9,"c")]就是錯誤的。你能指出其中的區別嗎?

練習
  1. 以下哪些是正確的Haskell表達式,為什麼?
    • fst [1,2]
    • 1:(2,3)
    • (2,4):(2,3)
    • (2,4):[]
    • [(2,4),(5,5),('a','b')]
    • ([2,4],[2,2])

概要

在這一章我們已經介紹了兩種新的記法,列表和元組。總結一下:

  1. 列表用方括號和逗號定義:[1,2,3].
    • 它們可以包含任意數據,只要這個列表的所有元素都屬於相同類型
    • 也可以用cons操作符(:)來創建它們,但是你只能附加(cons)數據到列表
  2. 元組用圓括號和逗號定義:("Bob",32)
    • 它們可以包含任意數據,甚至不同類型的數據
    • 它們有一個固定的長度,或者至少它們的長度被它們的類型決定。就是說,兩個不同長度的元組有不同的類型。
  3. 列表和元組可以任意方式嵌套:列表組成的列表,元組組成的列表,等等

我們希望在這一刻,你已經能熟練運用Haskell的基本構建(變量,函數,列表),因為我們現在會轉移到一些更振奮人心的主題,類型和遞歸。 類型,雖然我們已經在這一章提及了三次,但是卻沒有明確說明它是什麼。 在解釋什麼是類型前,我們還是先對GHC作一個介紹,使你能更好地使用GHC解釋器。

提示

  1. 你應該反對因為你認為那甚至不是一個正確的單詞。好的,它不是。在程式設計師中,一個由LISP開始的傳統是把這種追加元素到列表頭部的操作稱為"consing"。因為這是一種構造列表的方式,所以這個動詞在這裏是"cons",也就是"constructor"(構造)的簡寫。
  2. 這至少涉及到類型,但是我們正試着避免使用這個詞 :)
  3. 更專業的說,fstsnd有限制它們配對的類型。你將不能定義通用的以元組為參數的射影函數(projection function),因為它們將不得不接受不同大小的數據,從而使這個函數的類型多樣化。



可打印版本
習題解答
Haskell基礎

起步  >> 變量和函數  >> 列表和元組  >> 更進一步  >> 類型基礎  >> 簡單的輸入輸出  >> 類型聲明


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務


提示


更進一步

Haskell文件

到現在,我們已經多次使用了GHC解釋器。它的確是一個有用的調試工具。但是接下來的課程如果我們直接輸入所有表達式是麻煩的。所以現在我們開始寫第一個Haskell源文件。

在你最喜愛的編輯器中打開一個文件Varfun.hs(hs是Haskell的簡寫)然後把下面的定義粘貼進去。Haskell使用縮進和空格來決定函數(及其它表達式)的開始和結束,所以確保沒有前置的空格並且縮進是正確的,否則GHC將報錯。

area r = pi * r^2

(為避免你的疑慮,pi事實上已經被Haskell定義,不需要在這裏包含它了)。現在轉到你保存文件的目錄,打開ghci,然後使用 :load(或者簡寫為 :l):

Prelude> :load Varfun.hs
Compiling Main             ( Varfun.hs, interpreted )
Ok, modules loaded: Main.
*Main> 

如果ghci給出一個錯誤,"Could not find module 'Varfun.hs'"(「找不到模塊'Varfun.hs'」),那麼使用:cd來改變當前目錄到包含Varfun.hs的目錄:

Prelude> :cd c:\myDirectory
Prelude> :load Varfun.hs
Compiling Main             ( Varfun.hs, interpreted )
Ok, modules loaded: Main.
*Main> 

現在你可以執行文件中的函數:

*Main> area 5
78.53981633974483

如果你修改了文件,只需使用:reload(簡寫為 :r)來重新載入文件。

註解

GHC也可以用作編譯器。就是說你可以用GHC來把你的Haskell文件轉換為一個獨立的可執行程序。詳情見其文檔。

你將注意到直接在ghci輸入語句與從文件載入有一些不同。這些不同現在看來可能非常隨意,但它們事實上是十分明智的範圍的結果,其餘的,我們保證將晚點解釋。

沒有let

初學者要注意,源文件里不要像這樣寫

let x = 3
let y = 2
let area r = pi * r ^ 2

而是要像這樣寫

x = 3
y = 2
area r = pi * r ^ 2

關鍵字let事實上在Haskell中用的很多,但這裏不強求。在這一章討論let綁定的用法後,我們將看得更遠。

不能定義同一個量兩次

先前,解釋器高興地允許我們像這樣寫

Prelude> let r = 5
Prelude> r
5
Prelude> let r = 2
Prelude> r
2

另一方面,在源文件里像這樣寫不對

--这不对
r = 5
r = 2

像我們先前提及的那樣,變量不能改變,並且當你寫一個源文件時甚至更關鍵。這裏有一個漂亮的暗示。它意味着:

順序不重要

你聲明變量的順序不重要。例如,下面的代碼片段可以得到完全同樣的結果:

 y = x * 2
 x = 3
 x = 3
 y = x * 2

這是Haskell和其它函數式程式語言的一個獨特的特性。變量不可改變的事實意味着我們隨意選擇以任何順序寫代碼(但是這也是我們不能聲明一個量一次以上的原因--否則那將是模稜兩可的的)。

練習
把你在上一章寫的作業保存在一個Haskell文件中。在GHCi中載入這個文件並用一些參數測試裏面的函數

關於函數的更多特性

當我們開始使用源文件工作而不只是在解釋器中敲一些代碼時,定義多個子函數會讓工作變得簡單。 讓我們開始見識Haskell函數的威力吧。

條件表達式

if / then / else

Haskell支持標準的條件表達式。我們可以定義一個參數小於時返回、參數等於時返回、參數大於時返回的函數。事實上,這個函數已經存在(被稱為符號(signum)函數),但是讓我們定義一個我們自己的,把它叫做mySignum

mySignum x =
    if x < 0 then 
        -1
    else if x > 0 then 
        1
    else 
        0

我們可以這樣像這樣測試它:

Example
Example

例子:

*Main> mySignum 5
1
*Main> mySignum 0
0
*Main> mySignum (5-10)
-1
*Main> mySignum (-1)
-1

注意最後一個測試「-1」兩邊的括弧是必需的;如果沒有,系統將認為你正試圖將值「mySignum」減去「1」,而這是錯誤的。

Haskell中的結構與大多數其它程式語言非常相似;無論如何,你必須同時有一個then一個else子句。在執行條件語句後如果它的值為True,接着會執行then部分;在執行條件語句後如果它的值為False,接着會執行else部分。

你可以把程序修改到文件里然後重新裝載到GHCI中,除了可以用命令:l Varfun.hs 重新裝載外,你還可以通過更快捷更簡單的方法:reload:r 把當前已經載入的文件重新載入。

case

Haskell跟很多語言一樣提供了 case 結構用於組合多個條件語句。(case其實有更強大的功能 -- 詳情可以參考 模式匹配).


假設我們要定義一個這樣的函數,如果它的參數為它會輸出;如果它的參數為它會輸出;如果它的參數為它會輸出;如果它的參數為其它,它會輸出。如果使用if 語句我們會得到一個可讀性很差的函數。但我們可以用case語句寫出如下形式可讀性更強的函數:


f x =
    case x of
      0 -> 1
      1 -> 5
      2 -> 2
      _ -> (-1)

在這個程序中,我們定義了函數f它有一個參數x,它檢查x的值。如果它的值符合條件那麼f的值為,如果它的值符合條件那麼f的值為,如此類推。如果x不符合之前任何列出的值那麼f的值為"_"為「通配符」表示任何值都可以符合這個條件)


注意在這裏縮進是非常重要的。Haskell 使用一個叫「layout"的佈局系統對程序的代碼進行維護(Python 語言也使用一個相似的系統)。這個佈局系統允許我們可以不需要像C,Java語言那樣加分號跟花括號來對代碼段進行分割。



縮進

更多了解請到 縮進。 有人不喜歡使用使用縮進的佈局方法,而使用分號跟花括號的方法。如果使用這種方法,以上的程序可以寫成以下的形式:

f x = case x of
        { 0 -> 1 ; 1 -> 5 ; 2 -> 2 ; _ -> -1 }

當然, 如果你使用分號跟花括號的佈局方法, 你可以更隨意地編寫你的代碼。以下的方式是完全可以的。

f x =
    case x of { 0 -> 1 ;
      1 -> 5 ; 2 -> 2
   ; _ -> -1 }

但是用這種方法有時候代碼可讀性是很差的。(譬如在以上情況下)

為不同參數定義一個函數

函數也可以通過分段定義的方法進行定義,也就是說你可以為不同個參數定義同一個函數的不同版本。例如,以上的函數f可以寫成一下方式

f 0 = 1
f 1 = 5
f 2 = 2
f _ = -1

就跟以上的case語句一樣,函數的執行是與定義的順序有關的。如果我們把最後的一行移到最前面,那麼無論參數是什麼,函數f的值都會是-1,無論是0 ,1 ,2 (大部分編譯器會對這種參數定義重合發出警告)。如果我們不使用f _ = -1,當函數遇到 0 ,1 ,2 以外的參數時會拋出一個錯誤(大部分編譯器也會會發出警告)。這種函數分段定義的方法是非常常用的,而且會經常在這個教程裏面使用。以上的方法跟case語句實質上是等價的 —— 函數分段定義將被翻譯成case語句

函數合成

複雜的函數可以通過簡單的函數相互合成進行構建。函數合成就是把一個函數的結果作為另一個函數的參數。其實我們曾經在起步那一章見過,5*4+3就是兩個函數合成。在這個例子中先執行,然後執行的結果作為 參數,最後得出結果。我們也可以把這種方法應用到squaref

square x = x^2
Example
Example

例子:

*Main> square (f 1)
25
*Main> square (f 2)
4
*Main> f (square 1)
5
*Main> f (square 2)
-1

每一個函數的結果都是顯而易見的。在例子的第一句中括號是非常必要的;不然,解釋器認為你要嘗試得到square f的值,但這顯然沒有意義。函數的這種合成方式普遍存在於其它程式語言中。在Haskell中有另外一種更數學化的表達方法:(.) 點函數。點函數源於數學中的()符號。


註解

在數學裏我們用表達式 表達 "f following g." 在Haskell , 代碼f . g 也表達為 "f following g."

其中 等同於


(.)函數(函數的合成函數),將兩個函數合稱為一個函數。例如,(square . f)表示一個有一個參數的函數,先把這個參數代入函數f,然後再把這個結果代入函數square得到最後結果。相反地,(f . square)表示一個有一個參數的函數,先把這個參數代入函數square,然後再把這個結果代入函數f得到最後結果。我們可以通過一下例子中的方法進行測試:

Example
Example

例子:

*Main> (square . f) 1
25
*Main> (square . f) 2
4
*Main> (f . square) 1
5
*Main> (f . square) 2
-1

在這裏,我們必須用括號把函數合成語句括起來;不然,如(square . f) 1Haskell的編譯器會認為我們嘗試把squaref 1的結果合成起來,但是這是沒有意義的因為f 1甚至不是一個函數。

現在我們可以稍稍停下來看看在Prelude中已經定義的函數,這是十分明智的。因為很有可能把已經在Prelude中定義了的函數,自己卻不經意再定義一遍(我已經不記得我這樣做了多少遍了),這樣浪費掉了很多時間。

let綁定

我們經常在函數中聲明局部變量。 如果你記得中學數學課的內容,這裏有一個例子, 一元二次方程可以用下列等式求解

我們將它轉換為函數來得到:的兩個值

roots a b c =
    ((-b + sqrt(b*b - 4*a*c)) / (2*a),
     (-b - sqrt(b*b - 4*a*c)) / (2*a))

請注意我們的定義中有一些冗餘,不如數學定義優美。在函數的定義中我們重複了sqrt(b*b - 4*a*c)。 用Haskell的局部綁定(local binding)可以解決這個問題。也就是說我們可以在函數中定義只能在本函數中使用的值。 我們來創建sqrt(b*b-4*a*c)的局部綁定disc,並在函數中替換sqrt(b*b - 4*a*c)

我們使用了let/in來聲明disc:

roots a b c =
    let disc = sqrt (b*b - 4*a*c)
    in  ((-b + disc) / (2*a),
         (-b - disc) / (2*a))

在let語句中可以同時聲明多個值,只需注意讓它們有相同的縮進就可以:

roots a b c =
    let disc = sqrt (b*b - 4*a*c)
        twice_a = 2*a
    in  ((-b + disc) / twice_a,
         (-b - disc) / twice_a)



可打印版本
習題解答
Haskell基礎

起步  >> 變量和函數  >> 列表和元組  >> 更進一步  >> 類型基礎  >> 簡單的輸入輸出  >> 類型聲明


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務


類型基礎

類型在編程中是一種分組相似值的方法。在Haskell中,類型系統是一種確保你的代碼中存在更少錯誤的強有力的途徑。

介紹

編程處理不同的條目。例如,考慮把兩個數相加:

2 + 3

2和3是什麼?很清楚,它們是數。但是這個添加在中間的加號是什麼?當然不是一個數。那它又是什麼?

類似地,考慮一個程序問你的名字,然後說「Hello」。你的名字和Hello這個詞都不是數字。它們是什麼?我們應該提及所有的句子和段落等等作為文本。事實上,編程時使用的一個稍微更秘密的詞「String」,要更普通。

Haskell中,規則是所有的類型名必須以一個大寫字母開始。今後我們應該堅持這個轉變。

如果你之前曾經設置過一個數據庫,你將可能遇到過類型。例如,說我們在一個數據庫中有一個表來存儲一個人的詳細聯繫信息;一種個人電話本。它的內容應該像這樣:

電話號碼 地址
743756 北京新天地小區22#1B
655523 上海藍瑪仁小區99#3B

字段中包含着值。「李」是一個值,「上海藍瑪仁小區99#3B」是一個值,「655523」也是一個值。如此說來,類型是用以分辨數據的標準。上表中有何類型?一二行的名和姓屬於文字,所以這二個值的類型是String(字符串)。第三行是一個以名來定的值,電話號碼。此值的類型是Number(數字)。

初看之下,地址行的值也是String類型的。然而事實上地址相當複雜。地址中有許多約定俗成的意義在。比如說,地址最後的一部分,通常是房間號,如果不是,也可能是信箱號,但總之是一個人的最詳細地址。簡單點說,此處的意義不止Text(文本)本身那點可憐的意義。我們可以說地址屬於Text;這沒什麼關係。然而聲明它屬於另一種類型,比如Address,會更科學。如果我們知道某些數據時Text,這通常於事無補。然而若知道它屬於Address,我們立刻就可以對它有更多解讀。

這道理我們可以用在電話號碼行上。故,TelephoneNumber這種類型產生了。以後我們要是再看到一串數字,只要知道是TelephoneNumber的類型,就會明白這不止是一串數字,而意會更多的信息。

不把TelephoneNumber看做Number(數字)類型的另一個原因是數字可以進行數學運算。那一個TelephoneNumber和1相加又有什麼意義吶?電話可不會幫你轉接張三的弟弟張四。因此把電話號碼做成一種更強的類型而不僅僅是一個數字是有足夠的理由的。而且,電話號碼中的每個數字都是很重要的,不能多也不能少,所以沒有四捨五入的說法,在電話號碼前面加0就更是匪夷所思了。另一個理由是可能需要指定區號的位置,添加國家碼。這樣,最好的辦法就是抽象出一個單獨的類型。

為什麼類型有用

到現在,我們都好像只是在搞搞分類,幾乎沒有一點可以讓現代計算機語言設計者吸收之處。別急,下一篇,我們會探究Haskell如何善用類型,使程式設計師獲益。

使用交互式的:type命令

字符和字符串

在Haskell中,探尋類型如何發揮作用的最好方法是使用 GHCi 。運行之,來了解一下 :type 命令。

Example
Example

例子: 在GHCi中對字符使用 :t 命令

Prelude> :type 'H'
'H' :: Char


提示: :type 命令可縮寫為 :t

這就是我們的使用方式。在 GHCi中,它會對一個值給出其類型。此例中,我們給了一個字符 'H' ——一個包在單引號里的字母 H ,GHCi 顯示了它,其後跟着"::" ,也就是「類型是」的意思。整句話的意思是: 'H' 的類型是 Char 。

如果想給出一個字符串,要用雙引號括起來。

Example
Example

例子: 在GHCi中對字符串使用 :t 命令

Prelude> :t "Hello World"
"Hello World" :: [Char]


這次,我們給出的是一個用雙引號括起來的文本,GHCi的反應是: "Hello World" :: [Char] 。[Char] 意思是「字符構成的表」。注意區別 Char 和 [Char] ——帶方括號的被用來構造文字列表。

練習
  1. 試用 :type 查詢 "H" 的類型(注意雙引號的使用),返回什麼?為什麼?.
  2. 試用 :type 查詢 'Hello World' 的類型(注意單引號的使用),返回什麼?為什麼?.


在Haskell中字符串實質就是字符列表。在Haskell中可以用幾種方法初始化字符串: 用雙引號(ANSI 34)括起的連續的字符; 也可以像構建列表那樣用":"將多個字符連接起來從而構成一個字符串,如 'H':'e':'l':'l':'o':[]; 還可以使用字符列表的形式來構建。

Haskell 有一個同義類的概念。就像英語裏面的 'fast' 與 'quick', 兩者意義相同,在Haskell中這種字面不同,但意義相同的兩個類稱為同義類(type synonyms)。就是說能使用 [Char]的地方一樣能用 String來代替,如:

"Hello World" :: String

這樣的表達也是正確的 。從這裏開始我們將會更多的使用String,而不是[Char]來表示字符串。

布爾值

另一種在其他語言中很常見的類型是布爾型(Boolean),或簡稱Bool。這是一種十分有用的類型。這種類型有兩個值:True 或 False(對或錯)。例如一個程序向使用者詢問一個名字並在一個文件中查找這個名字相關項目。這時候如果我們有一個函數 nameExists用來確認這個名字是否存在是十分方便的。如果名字存在,可以用True來表達,如果名字不存在可以將結果表達為False。要注意的是在Haskell中布爾值是頭字母大寫的(其中的原因在逐步深入後會變得清晰)

Example
Example

例子: 在GHCI中探索 True 與 False的類型

Prelude> :t True
True :: Bool
Prelude> :t False
False :: Bool


這裏就不用太多的解釋了。 True 與 False 被歸類為布爾型。

數值類型

如果你已經使用:t對所有你已經熟悉的值進行查詢,可能你會發現對5進行查詢會返回如下的複雜類型。


Prelude> :t 5
5 :: (Num t) => t


簡單來說,有很多數型(整數,小數等)而5可以屬於不同的數型。這個看起來比較複雜的類型與Haskell的類型類特性有關。我們將會在以後的章節詳細解釋這種複雜的類型表示。

函數類型

So far, the types we have talked about apply to values (strings, booleans, characters, etc), and we have explained how types not only help to categorize them, but also describe them. The next thing we'll look at is what makes the type system truly powerful: We can assign types not only to values, but to functions as well[1]. Let's look at some examples.

之前我們展示了類型是如何應用在值(字符串,布爾值,字符,等)上的,可以看出Haskell中的類型不只是簡單用於分分類,而且可用以描述值的特性。接着我們介紹,使類型系統真正強大的特性 -- 類型不只能應用在值上,還能應用在函數上 [2]。讓我們看幾個例子.

例子:not

Example
Example

例子: Negating booleans

not True  = False
not False = True


not is a standard Prelude function that simply negates Bools, in the sense that truth turns into falsity and vice versa. For example, given the above example we gave using Bools, nameExists, we could define a similar function that would test whether a name doesn't exist in the spreadsheet. It would likely look something like this:

not是一個標準的Prelude函數。功能就是把True變成False,False變成True。這裏重新使用之前使用過的nameExists例子,重新定義一個相似的函數,但是這個函數是檢驗名字(not)是否"不"存在於電子數據表中。如下:

Example
Example

例子: nameDoesntExist: using not

nameDoesntExist name = not (nameExists name)


To assign a type to not we look at two things: the type of values it takes as its input, and the type of values it returns. In our example, things are easy. not takes a Bool (the Bool to be negated), and returns a Bool (the negated Bool). Therefore, we write that:

要為not寫一個類型標記我們關心兩個方面:輸入的值的類型,輸出的值的類型。在我們的例子中,給not一個布爾型的值,然後返回一個布爾型的值。一次我們可以為not寫出一下的類型標記:

Example
Example

例子: not的類型標記

not :: Bool -> Bool
注意: not是类型标记的一部分。


You can read this as 'not is a function from things of type Bool to things of type Bool'.

我們可以這樣來描述這個類型標記: not函數取一個布爾值作為輸入,返回一個布爾值。

例子:unlinesunwords

A common programming task is to take a list of Strings, then join them all up into a single string, but insert a newline character between each one, so they all end up on different lines. For example, say you had the list ["Bacon", "Sausages", "Egg"], and wanted to convert it to something resembling a shopping list, the natural thing to do would be to join the list together into a single string, placing each item from the list onto a new line. This is precisely what unlines does. unwords is similar, but it uses a space instead of a newline as a separator. (mnemonic: un = unite)

程序設計中有一種任務很常見,這就是對一個字符串列表含有的每個元素添加換行符,再將它們連接成一個新的字符串。例如,對於列表 ["Bacon", "Sausages", "Egg"],我們希望把它合併為一個採購清單,對此,最直接的方法是,將列表中的每一項放入一個新行。這種方法就是unlinesunwords與它類似,區別在於後者用空格代替換行。(助記符: un = unite)

Example
Example

例子: unlines and unwords

Prelude> unlines ["Bacon", "Sausages", "Egg"]
"Bacon\nSausages\nEgg\n"
Prelude> unwords ["Bacon", "Sausages", "Egg"]
"Bacon Sausages Egg"


Notice the weird output from unlines. This isn't particularly related to types, but it's worth noting anyway, so we're going to digress a little and explore why this is. Basically, any output from GHCi is first run through the show function, which converts it into a String. This makes sense, because GHCi shows you the result of your commands as text, so it has to be a String. However, what does show do if you give it something which is already a String? Although the obvious answer would be 'do nothing', the behaviour is actually slightly different: any 'special characters', like tabs, newlines and so on in the String are converted to their 'escaped forms', which means that rather than a newline actually making the stuff following it appear on the next line, it is shown as "\n". To avoid this, we can use the putStrLn function, which GHCi sees and doesn't run your output through show.

請注意unlines的輸出格式。雖與本章內容無關,我們將稍微解釋一下這種格式。GHCi的所有輸出,都首先利用show函數,此函數將輸出轉化為一個字符串。這是因為GHCi將把你命令的結果作為文本輸出。如果輸出已經是字符串了,show函數將做什麼?毫無疑問,它什麼都不會做;但具體行為上,與「什麼都不會做」略有不同:字符串中出現的特殊字符,如tab,換行等,將被轉義為\t,\n等格式。為了避免這種情況,可以使用putStrLn函數,這樣將不會像平常一樣默認調用show函數

Example
Example

例子: Using putStrLn in GHCi

Prelude> putStrLn (unlines ["Bacon", "Sausages", "Egg"])
Bacon
Sausages
Egg

Prelude> putStrLn (unwords ["Bacon", "Sausages", "Egg"])
Bacon Sausages Egg


The second result may look identical, but notice the lack of quotes. putStrLn outputs exactly what you give it (actually putStrLn appends a newline character to its input before printing it; the function putStr outputs exactly what you give it). Also, note that you can only pass it a String. Calls like putStrLn 5 will fail. You'd need to convert the number to a String first, that is, use show: putStrLn (show 5) (or use the equivalent function print: print 5).

第二個結果看起來似乎一致,但不要忘記它少了引號。putStrLn函數將嚴格輸出你給它的東西(但實際上,putStrLn會給自己的輸出自動加個換行符,putStr才會給出真正嚴格的輸出)。同時,注意它將僅僅接受一個字符串作為參數。諸如putStrLn 5的函數調用將會失敗,你必須將數字5轉化為字符串才行,例如putStrLn (show 5) (或者print: print 5))

Getting back to the types. What would the types of unlines and unwords be? Well, again, let's look at both what they take as an argument, and what they return. As we've just seen, we've been feeding these functions a list, and each of the items in the list has been a String. Therefore, the type of the argument is [String]. They join all these Strings together into one long String, so the return type has to be String. Therefore, both of the functions have type [String] -> String. Note that we didn't mention the fact that the two functions use different separators. This is totally inconsequential when it comes to types — all that matters is that they return a String. The type of a String with some newlines is precisely the same as the type of a String with some spaces.

現在讓我們回到類型上來。unlinesunwords 是什麼類型?觀察它們的輸入和輸出,注意到這兩個函數都將接受一個字符串列表,所以,它們的輸入參數類型為[String]。處理並連接列表後,它們都將輸出一個較長的字符串。所以,這兩個函數的類型是 [String] -> String。注意,我們並未提及這兩個函數用於連接的字符的不同,因為這對類型來說是微不足道的,它們都將輸出一個字符串,含有換行的字符串的類型和含有空格的字符串的類型是一致的。

例子:chrord

文字處理是計算機的一個問題. 當一切東西都到達最底層的時候, 計算機所知道的僅僅是1和0, 正如其在二進制下工作. 然而直接操作二進制並不方便, 人們開始讓計算機保存文字信息. 每個字符應該先轉換為數字, 然後再轉換為二進制來存儲. 因此, 文字, 或者說一串字符, 能夠被編碼為二進制. 一般來說, 我們只是關心字符如何用數字來表示, 因為再將數字轉為二進制將會非常容易.


轉換字元變成數字這件事是簡單的,只要將所有可能的字元寫下來,然後每個字元給一個數字。舉例來說,我們可能給予字元 'a' 對應到 1, 字元 'b' 對應到2, 依此類推。這件事有一個稱為ASCII標準已經幫我們做了,有128個標準常用的字元,數字都被編碼在 ASCII 的表格裏面。但是當我們每次需要用到一個字元時,都需要從表格中去把這些字元對應的數字找出來,或從數字中找出這些字元來,這真是一件無聊的事。所以,我們可以用兩個函式來幫我們解決這個問題,chr(發音是 'char') 以及 ord

Example
Example

例子: Type signatures for chr and ord

chr :: Int  -> Char
ord :: Char -> Int


記得我們之前說過Haskell有多少數字類型麼? 最簡單的是Int類型, 它表示一個整數, to give them their proper name. [3] 記得上面類型標識麼? 回憶一下上面的not是怎麼工作的. 我們先是看到函數的參數類型, 然後是其返回類型. chr函數(返回對應數字編碼的字符)的類型標識表示其接受一個Int類型的參數, 並返回一個Char. 執行反操作的是ord函數(返回對應字符的數字編碼).

具體來說, 參考以下幾個調用chrord的例子, 你可以看到這些類型是如何工作得. 注意這兩個函數並不是內建函數, 而是在Data.Char模塊中的, 因此你需要使用:m (:module的縮寫)命令來加載之.

Example
Example

例子: Function calls to chr and ord

Prelude> :m Data.Char
Prelude Data.Char> chr 97
'a'
Prelude Data.Char> chr 98
'b'
Prelude Data.Char> ord 'c'
99


多參數函數

So far, we've only worked with functions that take a single argument. This isn't very interesting! For example, the following is a perfectly valid Haskell function, but what would its type be?

到目前為止,我們只使用只有一個參數的函數。這太沒趣了。例如,下面就是一個完全有效的Haskell函數,但是它是什麼類型的呢?

Example
Example

例子: A function in more than one argument

f x y = x + 5 + 2 * y


As we've said a few times, there's more than one type for numbers, but we're going to cheat here and pretend that x and y have to be Ints.

正如前面說的,數字可以表達為多種類型,只是我們在這裏假裝 x 和 y 必須是 Int 的。

There are very deep reasons for this, which we'll cover in the chapter on Currying.

這種做法有着深層次的原因。我們將在Currying一章中進行解讀。

The general technique for forming the type of a function in more than one argument, then, is to just write down all the types of the arguments in a row, in order (so in this case x first then y), then write -> in between all of them. Finally, add the type of the result to the end of the row and stick a final -> in just before it. So in this case, we have:

對多參數函數來說最普遍的方式是把所有參數的類型都寫在同一行,按字母排序(所以在這個例子中 x先於y),在它們中間插入->。最後,在行尾寫上結果的類型並且在它前面加最後一個->。所以在這個例子中,我們有:

-->
  1. Write down the types of the arguments. We've already said that x and y have to be Ints, so it becomes:
    Int             Int
    ^^ x is an Int  ^^ y is an Int as well
    
  2. Fill in the gaps with ->:
    Int -> Int
  3. Add in the result type and a final ->. In our case, we're just doing some basic arithmetic so the result remains an Int.
    Int -> Int -> Int
                  ^^ We're returning an Int
        ^^ There's the extra -> that got added in 

現實例子:openWindow

A library is a collection of common code used by many programs.

As you'll learn in the Practical Haskell section of the course, one popular group of Haskell libraries are the GUI ones. These provide functions for dealing with all the parts of Windows or Linux you're familiar with: opening and closing application windows, moving the mouse around etc. One of the functions from one of these libraries is called openWindow, and you can use it to open a new window in your application. For example, say you're writing a word processor like Microsoft Word, and the user has clicked on the 'Options' button. You need to open a new window which contains all the options that they can change. Let's look at the type signature for this function [4]:

Example
Example

例子: openWindow

openWindow :: WindowTitle -> WindowSize -> Window


Don't panic! Here are a few more types you haven't come across yet. But don't worry, they're quite simple. All three of the types there, WindowTitle, WindowSize and Window are defined by the GUI library that provides openWindow. As we saw when constructing the types above, because there are two arrows, the first two types are the types of the parameters, and the last is the type of the result. WindowTitle holds the title of the window (what appears in the blue bar (XP and before) or black translucent bar (Vista) - you didn't change the color, did you? - at the top), WindowSize how big the window should be. The function then returns a value of type Window which you can use to get information on and manipulate the window.

練習

Finding types for functions is a basic Haskell skill that you should become very familiar with. What are the types of the following functions?

  1. The negate function, which takes an Int and returns that Int with its sign swapped. For example, negate 4 = -4, and negate (-2) = 2
  2. The (&&) function, pronounced 'and', that takes two Bools and returns a third Bool which is True if both the arguments were, and False otherwise.
  3. The (||) function, pronounced 'or', that takes two Bools and returns a third Bool which is True if either of the arguments were, and False otherwise.

For any functions hereafter involving numbers, you can just assume the numbers are Ints.

  1. f x y = not x && y
  2. g x = (2*x - 1)^2
  3. h x y z = chr (x - 2)

多態性的類型

So far all we've looked at are functions and values with a single type. However, if you start playing around with :t in GHCi you'll quickly run into things that don't have types beginning with the familiar capital letter. For example, there's a function that finds the length of a list, called (rather predictably) length. Remember that [Foo] is a list of things of type Foo. However, we'd like length to work on lists of any type. I.e. we'd rather not have a lengthInts :: [Int] -> Int, as well as a lengthBools :: [Bool] -> Int, as well as a lengthStrings :: [String] -> Int, as well as a...

到目前為止,我們已經看過一些具有單一型態的函式和值。然而,如果你開始在GHCi中玩 :t,你將會碰到一些型態的第一個字母不是熟悉的大寫字母。舉例來說,有一個函式用來找出列表的長度,稱作 length. 記住,[Foo] 是一個存放型態Foo的事情的列表。然而我們希望length可以使用在存放任何型態的列表。而不是用計算存放整數的列表的長度用 lengthInts :: [Int] -> Int,計算存放布爾值的列表長度用 lengthBools :: [Bool] -> Int,計算存放字串列表的長度用 lengthStrings :: [String] -> Int, 等等。

That's too complicated. We want one single function that will find the length of any type of list. The way Haskell does this is using type variables. For example, the actual type of length is as follows:

這太複雜了,我們想要有一個單一的函式,可以計算出每一種存放所有型態列表的長度,所以, Haskell 使用型態變數來解決這個問題。例如:真實的型態長度如下:

Example
Example

例子: Our first polymorphic type

length :: [a] -> Int


We'll look at the theory behind polymorphism in much more detail later in the course.

The "a" you see there in the square brackets is called a type variable. Type variables begin with a lowercase letter. Indeed, this is why types have to begin with an uppercase letter — so they can be distinguished from type variables. When Haskell sees a type variable, it allows any type to take its place. This is exactly what we want. In type theory (a branch of mathematics), this is called polymorphism: functions or values with only a single type (like all the ones we've looked at so far except length) are called monomorphic, and things that use type variables to admit more than one type are therefore polymorphic.

例子:fstsnd

As we saw, you can use the fst and snd functions to extract parts of pairs. By this time you should be in the habit of thinking "What type is that function?" about every function you come across. Let's examine fst and snd. First, a few sample calls to the functions:

Example
Example

例子: Example calls to fst and snd

Prelude> fst (1, 2) 
1
Prelude> fst ("Hello", False)
"Hello"
Prelude> snd (("Hello", False), 4)
4


To begin with, let's point out the obvious: these two functions take a pair as their parameter and return one part of this pair. The important thing about pairs, and indeed tuples in general, is that they don't have to be homogeneous with respect to types; their different parts can be different types. Indeed, that is the case in the second and third examples above. If we were to say:

fst :: (a, a) -> a

That would force the first and second part of input pair to be the same type. That illustrates an important aspect to type variables: although they can be replaced with any type, they have to be replaced with the same type everywhere. So what's the correct type? Simply:

Example
Example

例子: The types of fst and snd

fst :: (a, b) -> a
snd :: (a, b) -> b


Note that if you were just given the type signatures, you might guess that they return the first and second parts of a pair, respectively. In fact this is not necessarily true, they just have to return something with the same type of the first and second parts of the pair.

代碼中的類型標記

Now we've explored the basic theory behind types and types in Haskell, let's look at how they appear in code. Most Haskell programmers will annotate every function they write with its associated type. That is, you might be writing a module that looks something like this:

Example
Example

例子: Module without type signatures

module StringManip where

import Data.Char

uppercase = map toUpper
lowercase = map toLower
capitalise x = 
  let capWord []     = []
      capWord (x:xs) = toUpper x : xs
  in unwords (map capWord (words x))


This is a small library that provides some frequently used string manipulation functions. uppercase converts a string to uppercase, lowercase to lowercase, and capitalize capitalizes the first letter of every word. Providing a type for these functions makes it more obvious what they do. For example, most Haskellers would write the above module something like the following:

Example
Example

例子: Module with type signatures

module StringManip where

import Data.Char

uppercase, lowercase :: String -> String
uppercase = map toUpper
lowercase = map toLower

capitalise :: String -> String
capitalise x = 
  let capWord []     = []
      capWord (x:xs) = toUpper x : xs
  in unwords (map capWord (words x))


Note that you can group type signatures together into a single type signature (like ours for uppercase and lowercase above) if the two functions share the same type.

類型推斷

So far, we've explored types by using the :t command in GHCi. However, before you came across this chapter, you were still managing to write perfectly good Haskell code, and it has been accepted by the compiler. In other words, it's not necessary to add type signatures. However, if you don't add type signatures, that doesn't mean Haskell simply forgets about typing altogether! Indeed, when you didn't tell Haskell the types of your functions and variables, it worked them out. This is a process called type inference, whereby the compiler starts with the types of things it knows, then works out the types of the rest of the things. Type inference for Haskell is decidable, which means that the compiler can always work out the types, even if you never write them in [5]. Let's look at some examples to see how the compiler works out types.

到目前為止,我們已經可以透過命令 :t 來看型態。然而,在你結束這章前,你正學習寫一個完美的 Hasekell 程式碼,這程式碼已經可以被編譯器接受。 換句話說,你不需要加上型別簽章。如果你沒有加上型別簽章,這不代表 Hasekell 全部忽略型別這件事。相反地,當你沒有告訴 HaseKell 你的函式或變數型別,Hasekell 會想辦法生出來。這個流程叫做型別推論。藉着它所知道的事情的型別,推論出其他事情的型別。型別推論對 Haskell來說是可決定性的,代表着編譯器總是能夠推論出型別,甚至你從沒寫過他們。


Example
Example

例子: Simple type inference

-- We're deliberately not providing a type signature for this function
-- 我们故意不提供这个函数的类型指纹.
isL c = c == 'l'


This function takes a character and sees if it is an 'l' character. The compiler derives the type for isL something like the following:

Example
Example

例子: A typing derivation

(==)  :: a -> a -> Bool
'l'   :: Char
Replacing the second ''a'' in the signature for (==) with the type of 'l':
(==)  :: Char -> Char -> Bool
isL   :: Char -> Bool


The first line indicates that the type of the function (==), which tests for equality, is a -> a -> Bool [6]. (We include the function name in parentheses because it's an operator: its name consists only of non-alphanumeric characters. More on this later.) The compiler also knows that something in 'single quotes' has type Char, so clearly the literal 'l' has type Char. Next, the compiler starts replacing the type variables in the signature for (==) with the types it knows. Note that in one step, we went from a -> a -> Bool to Char -> Char -> Bool, because the type variable a was used in both the first and second argument, so they need to be the same. And so we arrive at a function that takes a single argument (whose type we don't know yet, but hold on!) and applies it as the first argument to (==). We have a particular instance of the polymorphic type of (==), that is, here, we're talking about (==) :: Char -> Char -> Bool because we know that we're comparing Chars. Therefore, as (==) :: Char -> Char -> Bool and we're feeding the parameter into the first argument to (==), we know that the parameter has the type of Char. Phew!

But wait, we're not finished yet! What's the return type of the function? Thankfully, this bit is a bit easier. We've fed two Chars into a function which (in this case) has type Char -> Char -> Bool, so we must have a Bool. Note that the return value from the call to (==) becomes the return value of our isL function.

So, let's put it all together. isL is a function which takes a single argument. We discovered that this argument must be of type Char. Finally, we derived that we return a Bool. So, we can confidently say that isL has the type:

Example
Example

例子: isL with a type

isL :: Char -> Bool
isL c = c == 'l'


And, indeed, if you miss out the type signature, the Haskell compiler will discover this on its own, using exactly the same method we've just run through.

使用類型標記的原因

So if type signatures are optional, why bother with them at all? Here are a few reasons:

  • Documentation: the most prominent reason is that it makes your code easier to read. With most functions, the name of the function along with the type of the function is sufficient to guess at what the function does. (Of course, you should always comment your code anyway.)
  • Debugging: if you annotate a function with a type, then make a typo in the body of the function, the compiler will tell you at compile-time that your function is wrong. Leaving off the type signature could have the effect of allowing your function to compile, and the compiler would assign it an erroneous type. You wouldn't know until you ran your program that it was wrong. In fact, this is so important, let's explore it some more.

類型防止錯誤發生

假如你有以下幾個函數:

Example
Example

例子: Type inference at work

fiveOrSix :: Bool -> Int
fiveOrSix True  = 5
fiveOrSix False = 6

pairToInt :: (Bool, String) -> Int
pairToInt x = fiveOrSix (fst x)


Our function fiveOrSix takes a Bool. When pairToInt receives its arguments, it knows, because of the type signature we've annotated it with, that the first element of the pair is a Bool. So, we could extract this using fst and pass that into fiveOrSix, and this would work, because the type of the first element of the pair and the type of the argument to fiveOrSix are the same.

This is really central to typed languages. When passing expressions around you have to make sure the types match up like they did here. If they don't, you'll get type errors when you try to compile; your program won't typecheck. This is really how types help you to keep your programs bug-free. To take a very trivial example:

Example
Example

例子: A non-typechecking program

"hello" + " world"


Having that line as part of your program will make it fail to compile, because you can't add two strings together! More likely, you wanted to use the string concatenation operator, which joins two strings together into a single one:

Example
Example

例子: Our erroneous program, fixed

"hello" ++ " world"


An easy typo to make, but because you use Haskell, it was caught when you tried to compile. You didn't have to wait until you ran the program for the bug to become apparent.

This was only a simple example. However, the idea of types being a system to catch mistakes works on a much larger scale too. In general, when you make a change to your program, you'll change the type of one of the elements. If this change isn't something that you intended, then it will show up immediately. A lot of Haskell programmers remark that once they have fixed all the type errors in their programs, and their programs compile, that they tend to 'just work': function flawlessly first time, with only minor problems. Run-time errors, where your program goes wrong when you run it rather than when you compile it, are much rarer in Haskell than in other languages. This is a huge advantage of a strong type system like Haskell's.

練習

Infer the types of following functions:

  1. f x y = uppercase (x ++ y)
  2. g (x,y) = fiveOrSix (isL x) - ord y
  3. h x y = pairToInt (fst x,y) + snd x + length y

提示

  1. In fact, these are one and the same concept in Haskell.
  2. 事實上, 在Haskell中值跟函數是沒有理論上的區別的.
  3. 其實Haskell擁有很多種整數類型! 不過不要擔心, 我們將會在恰當的時候告訴你.
  4. This has been somewhat simplified to fit our purposes. Don't worry, the essence of the function is there.
  5. Some of the newer type system extensions to GHC do break this, however, so you're better off just always putting down types anyway.
  6. This is a slight lie. That type signature would mean that you can compare two values of any type whatsoever, but this clearly isn't true: how can you see if two functions are equal? Haskell includes a kind of 'restricted polymorphism' that allows type variables to range over some, but not all types. Haskell implements this using type classes, which we'll learn about later. In this case, the correct type of (==) is Eq a => a -> a -> Bool.



可打印版本
習題解答
Haskell基礎

起步  >> 變量和函數  >> 列表和元組  >> 更進一步  >> 類型基礎  >> 簡單的輸入輸出  >> 類型聲明


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務


簡單的輸入輸出

迄今為止這本教材已經討論了返回數值的函數,它們很不錯。但是我們怎樣才能寫出"Hello world"?為了給你第一印象,這裏有一個Haskell版的"Hello world"程序:

Example
Example

例子: Hello! What is your name?

main = do
  putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")


這個小程序至少說明了haskell沒有忘記提供輸入輸出功能(IO)! 因為IO會產生副作用,函數式語言基本上都在這方面存在問題。對於相同的參數,函數總是應該返回相同的結果。但是像getLine這樣的函數怎麼可能每次都返回相同的結果呢?在給出答案前,讓我們來仔細思考一下這個問題的難點。

任何IO庫至少應該提供以下功能:

  • 在屏幕上打印字符串
  • 從鍵盤上讀取字符串
  • 向文件寫入數據
  • 從文件中讀取數據

這裏有兩個問題。 我們先考慮前面的兩個例子應該是什麼類型. 第一個操作 (叫它「函數」似乎不合適) 應該取一個String類型的參數並返回一些東西,它應該返回什麼呢?它應該返回一個()單元,因為打印字符串本身什麼都不生成。第二個操作跟第一個類似,應該返回String類型的值,但它應該不需要參數。

我們希望這兩個操作是函數,但是從定義上說它們不是函數。從鍵盤讀取字符串的操作每次都返回不同的String類型值。如果putStrLn每次都返回(),依照引用透明性,我們可以把這個函數替換為f _ = ()。很明顯這樣做是不能得到相同結果的。

動作(Actions)

當Philip Wadler發現monads將會是一個解決IO計算的好方法時,這個問題有了突破性的進展。實際上,monads能夠解決比上述簡單操作更複雜的問題。我們可以用monads來解決一大類問題,比如並發、異常、IO、非確定性等等。而且,monads也不難在編譯器的層面上處理(雖然這樣,編譯器經常會優化monadic操作)。在某種程度上monads經常被人們誤解為是難以理解的。這些我們會稍後解釋,目前我們只需要知道IO使用的monads,我們可以在不了解背後理論細節的情況下使用它(其實monads理論也不是非常複雜)。目前我們可以暫時忘記monads的存在了。

就像前面說過的, 我們不能把類似「在屏幕上打印字符串」或是「從文件中讀數據」的操作作為函數, 因為它們不是函數(從純數學的角度)。因此,我們給它另一個名字:「動作」。我們不僅給它一個特殊的名字,我們還給了它一個特殊的類型。 一個非常有用的動作是putStrLn,它在屏幕上打印字符串。這個行為的類型是:

putStrLn :: String -> IO ()

跟我們想的一樣,putStrLn需要一個字符串參數。那它的返回類型IO ()是什麼呢?這說明這個函數是一個IO動作(這就是IO的意義)。此外,當這個動作被「執行」(或是「運行」)時,結果的類型是()

註解

實際上這個類型說明putStrLn是一個「IO monad"中的動作, 但是目前我們會先忽略它。

你現在可能已經猜到了getLine的類型:

getLine :: IO String

這個類型說明getLine是一個IO動作,執行這個動作後會返回類型為String的結果.

眼前的事情是我們怎樣運行一個動作?這個看起來是編譯器該干的活。你不能直接運行一個動作,而是要通過main函數執行這個動作。main函數本身也是一個動作,運行編譯後的程序就會直接執行這個動作。因此,編譯器要求main函數是類型IO (),也就是一個什麼都不返回的IO動作。(譯者:然而這並不代表程序在這個運行期間不修改外部的世界如屏幕輸出,文件修改等,而是這個動作在執行完後沒有任何結果給予後繼程序使用)

However, while you are not allowed to run actions yourself, you are allowed to combine actions. There are two ways to go about this. The one we will focus on in this chapter is the do notation, which provides a convenient means of putting actions together, and allows us to get useful things done in Haskell without having to understand what really happens. Lurking behind the do notation is the more explicit approach using the (>>=) operator, but we will not be ready to cover this until the chapter Understanding monads

雖然,你不能直接運行一個動作,但是你可以把同類型的動作組合 combine 起來。 有兩種方法可以用,其中一種方法是使用do我們將會在這章詳細介紹。隱藏在do背後的 是一個更顯式的方法,顯式使用(>>=),我們會在Understanding monads這章詳細解釋。

註解

Do notation is just syntactic sugar for (>>=). If you have experience with higher order functions, it might be worth starting with the latter approach and coming back here to see how do notation gets used. 實際上do(>>=)的語法糖。如果你有使用高階函數的經驗,可以直接閱讀學習第二種方法然後回來這章學習如何使用do

Let's consider the following name program:

Example
Example

例子: What is your name?

main = do
  putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")


We can consider the do notation as a way to combine a sequence of actions. Moreover, the <- notation is a way to get the value out of an action. So, in this program, we're sequencing three actions: a putStrLn, a getLine and another putStrLn. The putStrLn action has type String -> IO (), so we provide it a String, so the fully applied action has type IO (). This is something that we are allowed to run as a program.

練習

Write a program which asks the user for the base and height of a triangle, calculates its area and prints it to the screen. The interaction should look something like:

The base?
3.3
The height?
5.4
The area of that triangle is 8.91
Hint: you can use the function read to convert user strings like "3.3" into numbers like 3.3 and function show to convert a number into string.

Left arrow clarifications

左箭頭說明

The <- is optional

While we are allowed to get a value out of certain actions like getLine, we certainly are not obliged to do so. For example, we could very well have written something like this:

從特定的動作如 getLine 中取值是被容許的,但並非是必要的.我們可以這樣寫:

Example
Example

例子: executing getLine directly

main = do
  putStrLn "Please enter your name: "
  getLine
  putStrLn ("Hello, how are you?")


Clearly, that isn't very useful: the whole point of prompting the user for his or her name was so that we could do something with the result. That being said, it is conceivable that one might wish to read a line and completely ignore the result. Omitting the <- will allow for that; the action will happen, but the data won't be stored anywhere.

顯然, 這樣寫沒有太多用處: 提示用戶輸入名字是為了能利用輸入結果來做一些事情. 而上面的代碼卻可以理解為, 進行讀取一行的操作, 忽略讀取結果. 忽略 <- 就是這效果; 動作發生, 但結果未在任何地方保存.

In order to get the value out of the action, we write name <- getLine, which basically means "run getLine, and put the results in the variable called name."

The <- can be used with any action (except the last)

On the flip side, there are also very few restrictions which actions can have values obtained from them. Consider the following example, where we put the results of each action into a variable (except the last... more on that later):

Example
Example

例子: putting all results into a variable

main = do
  x <- putStrLn "Please enter your name: "
  name <- getLine
  putStrLn ("Hello, " ++ name ++ ", how are you?")


The variable x gets the value out of its action, but that isn't very interesting because the action returns the unit value (). So while we could technically get the value out of any action, it isn't always worth it. But wait, what about that last action? Why can't we get a value out of that? Let's see what happens when we try:

Example
Example

例子: getting the value out of the last action

main = do
  x <- putStrLn "Please enter your name: "
  name <- getLine
  y <- putStrLn ("Hello, " ++ name ++ ", how are you?")

Whoops!

YourName.hs:5:2:
    The last statement in a 'do' construct must be an expression


This is a much more interesting example, but it requires a somewhat deeper understanding of Haskell than we currently have. Suffice it to say, whenever you use <- to get the value of an action, Haskell is always expecting another action to follow it. So the very last action better not have any <-s.

這是一個很有趣的例子,相對於我們現在所認知的它需要一些對 Haskell 更深入的瞭解。只要用一句話就夠了,那就是無論你何時要使用 <- 去取得一個動作的值,Hasekell 總是期待後面還會有其它動作。所以,在最後一個動作最好不要有這個 <-

Controlling actions

Normal Haskell constructions like if/then/else and case/of can be used within the do notation, but you need to be somewhat careful. For instance, in a simple "guess the number" program, we have:

    doGuessing num = do
       putStrLn "Enter your guess:"
       guess <- getLine
       if (read guess) < num
         then do putStrLn "Too low!"
                 doGuessing num
         else if (read guess) > num
                then do putStrLn "Too high!"
                        doGuessing num
                else do putStrLn "You Win!"

If we think about how the if/then/else construction works, it essentially takes three arguments: the condition, the "then" branch, and the "else" branch. The condition needs to have type Bool, and the two branches can have any type, provided that they have the same type. The type of the entire if/then/else construction is then the type of the two branches.

In the outermost comparison, we have (read guess) < num as the condition. This clearly has the correct type. Let's just consider the "then" branch. The code here is:

              do putStrLn "Too low!"
                 doGuessing num

Here, we are sequencing two actions: putStrLn and doGuessing. The first has type IO (), which is fine. The second also has type IO (), which is fine. The type result of the entire computation is precisely the type of the final computation. Thus, the type of the "then" branch is also IO (). A similar argument shows that the type of the "else" branch is also IO (). This means the type of the entire if/then/else construction is IO (), which is just what we want.

註解

In this code, the last line is else do putStrLn "You Win!". This is somewhat overly verbose. In fact, else putStrLn "You Win!" would have been sufficient, since do is only necessary to sequence actions. Since we have only one action here, it is superfluous.

It is incorrect to think to yourself "Well, I already started a do block; I don't need another one," and hence write something like:

    do if (read guess) < num
         then putStrLn "Too low!"
              doGuessing num
         else ...

Here, since we didn't repeat the do, the compiler doesn't know that the putStrLn and doGuessing calls are supposed to be sequenced, and the compiler will think you're trying to call putStrLn with three arguments: the string, the function doGuessing and the integer num. It will certainly complain (though the error may be somewhat difficult to comprehend at this point).

We can write the same doGuessing function using a case statement. To do this, we first introduce the Prelude function compare, which takes two values of the same type (in the Ord class) and returns one of GT, LT, EQ, depending on whether the first is greater than, less than or equal to the second.

doGuessing num = do
  putStrLn "Enter your guess:"
  guess <- getLine
  case compare (read guess) num of
    LT -> do putStrLn "Too low!"
             doGuessing num
    GT -> do putStrLn "Too high!"
             doGuessing num
    EQ -> do putStrLn "You Win!"

Here, again, the dos after the ->s are necessary on the first two options, because we are sequencing actions.

If you're used to programming in an imperative language like C or Java, you might think that return will exit you from the current function. This is not so in Haskell. In Haskell, return simply takes a normal value (for instance, one of type Int) and makes it into an action that returns the given value (for the same example, the action would be of type IO Int). In particular, in an imperative language, you might write this function as:

void doGuessing(int num) {
  print "Enter your guess:";
  int guess = atoi(readLine());
  if (guess == num) {
    print "You win!";
    return ();
  }

  // we won't get here if guess == num
  if (guess < num) {
    print "Too low!";
    doGuessing(num);
  } else {
    print "Too high!";
    doGuessing(num);
  }
}

Here, because we have the return () in the first if match, we expect the code to exit there (and in most imperative languages, it does). However, the equivalent code in Haskell, which might look something like:

doGuessing num = do
  putStrLn "Enter your guess:"
  guess <- getLine
  case compare (read guess) num of
    EQ -> do putStrLn "You win!"
             return ()

  -- we don't expect to get here if guess == num
  if (read guess < num)
    then do print "Too low!";
            doGuessing num
    else do print "Too high!";
            doGuessing num

First of all, if you guess correctly, it will first print "You win!," but it won't exit, and it will check whether guess is less than num. Of course it is not, so the else branch is taken, and it will print "Too high!" and then ask you to guess again.

On the other hand, if you guess incorrectly, it will try to evaluate the case statement and get either LT or GT as the result of the compare. In either case, it won't have a pattern that matches, and the program will fail immediately with an exception.

練習

What does the following program print out?

main =
 do x <- getX
    putStrLn x

getX =
 do return "hello"
    return "aren't"
    return "these"
    return "returns"
    return "rather"
    return "pointless?"
Why?
練習

Write a program that asks the user for his or her name. If the name is one of Simon, John or Phil, tell the user that you think Haskell is a great programming language. If the name is Koen, tell them that you think debugging Haskell is fun (Koen Classen is one of the people who works on Haskell debugging); otherwise, tell the user that you don't know who he or she is.

Write two different versions of this program, one using if

statements, the other using a case statement.

Actions under the microscope

Actions may look easy up to now, but they are actually a common stumbling block for new Haskellers. If you have run into trouble working with actions, you might consider looking to see if one of your problems or questions matches the cases below. It might be worth skimming this section now, and coming back to it when you actually experience trouble.

Mind your action types

One temptation might be to simplify our program for getting a name and printing it back out. Here is one unsuccessful attempt:

Example
Example

例子: Why doesn't this work?

main =
 do putStrLn "What is your name? "
    putStrLn ("Hello " ++ getLine)

Ouch!

YourName.hs:3:26:
    Couldn't match expected type `[Char]'
           against inferred type `IO String'


Let us boil the example above down to its simplest form. Would you expect this program to compile?

Example
Example

例子: This still does not work

main =
 do putStrLn getLine


For the most part, this is the same (attempted) program, except that we've stripped off the superflous "What is your name" prompt as well as the polite "Hello". One trick to understanding this is to reason about it in terms of types. Let us compare:

putStrLn :: String -> IO ()
getLine  :: IO String

We can use the same mental machinery we learned in Type basics to figure how everything went wrong. Simply put, putStrLn is expecting a String as input. We do not have a String, but something tantalisingly close, an IO String. This represents an action that will give us a String when it's run. To obtain the String that putStrLn wants, we need to run the action, and we do that with the ever-handy left arrow, <-.

Example
Example

例子: This time it works

main =
 do name <- getLine
    putStrLn name

Working our way back up to the fancy example:

main =
 do putStrLn "What is your name? "
    name <- getLine
    putStrLn ("Hello " ++ name)


Now the name is the String we are looking for and everything is rolling again.

Mind your expression types too

Fine, so we've made a big deal out of the idea that you can't use actions in situations that don't call for them. The converse of this is that you can't use non-actions in situations that DO expect actions. Say we want to greet the user, but this time we're so excited to meet them, we just have to SHOUT their name out:

Example
Example

例子: Exciting but incorrect. Why?

import Data.Char (toUpper)

main =
 do name <- getLine
    loudName <- makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)

-- Don't worry too much about this function; it just capitalises a String
makeLoud :: String -> String
makeLoud s = map toUpper s
This goes wrong...
    Couldn't match expected type `IO' against inferred type `[]'
      Expected type: IO t
      Inferred type: String
    In a 'do' expression: loudName <- makeLoud name


This is quite similar to the problem we ran into above: we've got a mismatch between something that is expecting an IO type, and something which is not. This time, the cause is our use of the left arrow <-; we're trying to left arrow a value of makeLoud name, which really isn't left arrow material. It's basically the same mismatch we saw in the previous section, except now we're trying to use regular old String (the loud name) as an IO String, which clearly are not the same thing. The latter is an action, something to be run, whereas the former is just an expression minding its own business. Note that we cannot simply use loudName = makeLoud name because a do sequences actions, and loudName = makeLoud name is not an action.

So how do we extricate ourselves from this mess? We have a number of options:

  • We could find a way to turn makeLoud into an action, to make it return IO String. But this is not desirable, because the whole point of functional programming is to cleanly separate our side-effecting stuff (actions) from the pure and simple stuff. For example, what if we wanted to use makeLoud from some other, non-IO, function? An IO makeLoud is certainly possible (how?), but missing the point entirely.
  • We could use return to promote the loud name into an action, writing something like loudName <- return (makeLoud name). This is slightly better, in that we are at least leaving the makeLoud itself function nice and IO-free, whilst using it in an IO-compatible fashion. But it's still moderately clunky, because by virtue of left arrow, we're implying that there's action to be had -- how exciting! -- only to let our reader down with a somewhat anticlimatic return
  • Or we could use a let binding...

It turns out that Haskell has a special extra-convenient syntax for let bindings in actions. It looks a little like this:

Example
Example

例子: let bindings in do blocks.

main =
 do name <- getLine
    let loudName = makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)


If you're paying attention, you might notice that the let binding above is missing an in. This is because let bindings in do blocks do not require the in keyword. You could very well use it, but then you'd have to make a mess of your do blocks. For what it's worth, the following two blocks of code are equivalent.

sweet unsweet
 do name <- getLine
    let loudName = makeLoud name
    putStrLn ("Hello " ++ loudName ++ "!")
    putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)
 do name <- getLine
    let loudName = makeLoud name
    in  do putStrLn ("Hello " ++ loudName ++ "!")
           putStrLn ("Oh boy! Am I excited to meet you, " ++ loudName)
練習
  1. Why does the unsweet version of the let binding require an extra do keyword?
  2. Do you always need the extra do?
  3. (extra credit) Curiously, let without in is exactly how we wrote things when we were playing with the interpreter in the beginning of this book. Why can you omit the in keyword in the interpreter, when you'd have to put it in when typing up a source file?




Learn more

At this point, you should have the skills you need to do some fancier input/output. Here are some IO-related options to consider.

  • You could continue the sequential track, by learning more about types and eventually monads
  • Alternately: you could start learning about building graphical user interfaces in the GUI chapter
  • For more IO-related functionality, you could also consider learning more about the System.IO library



可打印版本
習題解答
Haskell基礎

起步  >> 變量和函數  >> 列表和元組  >> 更進一步  >> 類型基礎  >> 簡單的輸入輸出  >> 類型聲明


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務


類型聲明



Haskell has three basic ways to declare a new type:

Haskell有三種基本的方式申明一個新類:

  • The data declaration for structures and enumerations.
  • The type declaration for type synonyms.
  • The newtype declaration, which is a cross between the other two.

In this chapter, we will focus on the most essential way, data, and to make life easier, type. You'll find out about newtype later on, but don't worry too much about it; it's there mainly for optimisation.

data for making your own types

使用 data 來創建你自己的類型

Here is a data structure for a simple list of anniversaries: 這裏有兩個最簡單的紀念日列表數據結構 :

data Anniversary = Birthday String Int Int Int       -- name, year, month, day
                 | Wedding String String Int Int Int -- partner1name, partner2name, year, month, day

This declares a new data type Anniversary with two constructor functions called Birthday and Wedding. As usual with Haskell the case of the first letter is important: type names and constructor functions must always start with capital letters. Note also the vertical bar: this marks the point where one alternative ends and the next begins; you can think of it almost as an or - which you'll remember was || - except used in types.

這裏定義了一個新的數據類型 Anniversary ,它有兩個 constructor (構造)函數: BirthdayWedding. 通常情況下在Haskell里,單詞的第一個字母大小寫是很重要的: 類型名 和 構造函數必須以大寫開頭.注意這裏的符號'|': 它代表着一個構造函數的結束和一個可選構造函數的開始。你可以把它記成'或' -- '||',用在指定類型的時候少一豎就可以了.

The declaration says that an Anniversary can be one of two things; a Birthday or a Wedding. A Birthday contains one string and three integers, and a Wedding contains two strings and three integers. The comments (after the "--") explain what the fields actually mean.

以上聲明表達的是,一個紀念日可以是生日或者結婚日。生日包含一個字符串和三個整數,然後一個結婚紀念日包含兩個字符串和三個整數。註釋(在符號'--'後面的文字)解釋了這些參數的意義。

Now we can create new anniversaries by calling the constructor functions. For example, suppose we have John Smith born on 3rd July 1968:

現在我們可以通過調用兩個構造函數來創建新的紀念日。比如,John Smith 的生日是1968年7月3號:

johnSmith :: Anniversary
johnSmith = Birthday "John Smith" 1968 7 3

He married Jane Smith on 4th March 1987:

他在1987年3月4日娶了Jane Smith:

smithWedding :: Anniversary
smithWedding = Wedding "John Smith" "Jane Smith" 1987 3 4

These two objects can now be put in a list:

這兩個對象可以放在一個列表裏:

anniversaries :: [Anniversary]
anniversaries = [johnSmith, smithWedding]

(Obviously a real application would not hard-code its entries: this is just to show how constructor functions work).

Constructor functions can do all of the things ordinary functions can do. Anywhere you could use an ordinary function you can use a constructor function.

Anniversaries will need to be converted into strings for printing. This needs another function:

showAnniversary :: Anniversary -> String

showAnniversary (Birthday name year month day) =
   name ++ " born " ++ showDate year month day

showAnniversary (Wedding name1 name2 year month day) =
   name1 ++ " married " ++ name2 ++ " " ++ showDate year month day

This shows the one way that constructor functions are special: they can also be used to deconstruct objects. showAnniversary takes an argument of type Anniversary. If the argument is a Birthday then the first version gets used, and the variables name, month, date and year are bound to its contents. If the argument is a Wedding then the second version is used and the arguments are bound in the same way. The parenthesis indicate that the whole thing is one argument split into five or six parts, rather than five or six separate arguments.

Notice the relationship between the type and the constructors. All versions of showAnniversary convert an Anniversary to a String. One of them handles the Birthday case and the other handles the Wedding case.

It also needs an additional showDate routine:

showDate y m d = show y ++ "-" ++ show m ++ "-" ++ show d

Of course, it's a bit clumsy having the date passed around as three separate integers. What we really need is a new datatype:

data Date = Date Int Int Int   -- Year, Month, Day

Constructor functions are allowed to be the same name as the type, and if there is only one then it is good practice to make it so.

type for making type synonyms

It would also be nice to make it clear that the strings in the Anniversary type are names, but still be able to manipulate them like ordinary strings. The type declaration does this:

type Name = String

This says that a Name is a synonym for a String. Any function that takes a String will now take a Name as well, and vice versa. The right hand side of a type declaration can be a more complex type as well. For example String itself is defined in the standard libraries as

type String = [Char]

So now we can rewrite the Anniversary type like this:

data Anniversary = 
   Birthday Name Date
   | Wedding Name Name Date

which is a lot easier to read. We can also have a type for the list:

type AnniversaryBook = [Anniversary]

The rest of the code needs to be changed to match:

johnSmith :: Anniversary
johnSmith = Birthday "John Smith" (Date 1968 7 3)

smithWedding :: Anniversary
smithWedding = Wedding "John Smith" "Jane Smith" (Date 1987 3 4)

anniversaries :: AnniversaryBook
anniversaries = [johnSmith, smithWedding]


showAnniversary :: Anniversary -> String

showAnniversary (Birthday name date) =
   name ++ " born " ++ showDate date

showAnniversary (Wedding name1 name2 date) =
   name1 ++ " married " ++ name2 ++ showDate date


showDate :: Date -> String
showDate (Date y m d) = show y ++ "-" ++ show m ++ "-" ++ show d



可打印版本
習題解答
Haskell基礎

起步  >> 變量和函數  >> 列表和元組  >> 更進一步  >> 類型基礎  >> 簡單的輸入輸出  >> 類型聲明


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務



初級Haskell


遞歸

可打印版本 (解答)
Elementary Haskell

Template:Haskell章節/Elementary Haskell

遞歸這個絕妙想法是Haskell(一般也是計算機科學)的中心:即,遞歸是在一個函數定義的內部用到自身。有此種定義的函數叫做遞歸。聽起來好像會導致無限重複,但只要定義適當,就不會這樣。

一般來說,一個遞歸函數的定義有兩個部分。首先,至少要有一個底線,就是一個簡單的線,越過此處,遞歸會停止(換言之,此時函數會直接返回值,而不會繼續「遞歸般地」調用自身。底線保證了此函數必定結束。其次,是更一般的遞歸區,若參數在此範圍內就會以某種形式調用自身。下面是例子。

數值遞歸

階乘函數

數學上,尤其是組合數學,有一個相當常用的函數叫做階乘(Factorial)。[1]階乘函數的參數是一個自然數,它會返回1與此數之間所有數的乘積。比如,6的階乘是 1 × 2 × 3 × 4 × 5 × 6 = 720 。這相當有趣,因為對我們來說,它可以用一種遞歸函數來表示。

首先,我們比較相鄰兩個數的階乘。

Example
Example

例子: 相鄰數的階乘

Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1
Factorial of 5 =     5 × 4 × 3 × 2 × 1


注意我們是如何對齊的。明顯可以看出6的階乘和5的階乘有關係。6的階乘就是6 × (5的階乘)。讓我們來看另一個例子。

Example
Example

例子: Factorials of adjacent numbers

Factorial of 4 = 4 × 3 × 2 × 1
Factorial of 3 =     3 × 2 × 1
Factorial of 2 =         2 × 1
Factorial of 1 =             1


確實,我們可以看出任何數字的階乘就是此數字乘以比此數小1的數的階乘。除了一個例外:0的階乘,我們不會把0和-1的階乘相乘。事實上,我們只是認為0的階乘是1(我們就是這樣定義的,怎麼着了,你不同意?[2])。所以,0是此處遞歸的底線,當我們遇到0的時候,我們會立刻說答案是1,不需遞歸。我們可以把階乘函數的定義簡述如下。

  • 0的階乘是1
  • 任何數的階乘都是此數乘以比此數小一的數的階乘。

這個在Haskell中表示為:

Example
Example

例子: 階乘函數

factorial 0 = 1
factorial n = n * factorial (n-1)

這就定義了一個新的叫做factorial的函數。第一行表示0的階乘是1,第二行表示任意別的數n的階乘等於n乘以 n-1的階乘。注意那個把n-1括起來的括弧:沒有這個括弧代碼就會被解析稱為(factorial n) - 1;函數行為的優先級是很高的,會最先執行。 Template:Warning

到現在為止,你都會覺得有點微妙。實際上起作用嗎?來看看到底執行了factorial 3到底會發生什麼事情吧:

  • 3不是0,所以「遞歸」(再次執行factorial函數):看2的階乘是幾(也就是factorial 3
    • 2不是0,所以「遞歸」
      • 1不是0,遞歸
        • 0就是0,所以我們返回1
      • 我們將得到的1和本來的1相乘,得到 1 ,即(1 × 1),返回它
    • 我們將得到的1和本來的2相乘,得到2,即(2 × 1 × 1),返回它
  • 我們將得到的2和本來的3相乘,得到6,即6 (3 × 2 × 1 × 1)

我們可以看出乘法如何貫穿整個遞歸過程。

注意,我們最終的式子中1出現了兩次,因為底線是0而不是1;不過這造不成什麼錯誤,因為乘1還會是原來的數。如果我們想讓 factorial 在1處停下也辦得到,但0做底線符合常理,而且會很實用。

還有一點需要注意的:兩個聲明(一個是factorial 0的聲明,一個是factorial n的聲明)的順序很重要。Haskell會先匹配第一個句子,來決定函數的定義。所以,如果我們把兩句聲明掉個,第一個n語句將會匹配任何數(包括0)。所以語句 factorial 0的執行過程是去匹配情況n,於是factorial 0 的結果將會是0 * factorial (-1),然後就會沒完沒了。無限循環不是我們想要的。一般來說:特殊情況應該置於前,一般情況置於後。

練習
  1. 將階乘函數鍵入到一個源文件中,再載入到你的Haskell環境中
    • factorial 5是幾?
    • factorial 1000呢?如果你有個計算器,先用它算一算,然後看看和電腦中的一樣嗎?
    • 要是 factorial (-1)會如何?為何如此?
  2. 雙階乘意為:從1(或2)隔一個數字乘一個,一直乘到n。比如,8的雙階乘是 8 × 6 × 4 × 2 = 384, 7的雙階乘是 7 × 5 × 3 × 1 = 105. 定義一個雙階乘函數doublefactorial.

一次小小的跑題

此段落欲為習慣命令式語言如c或Java的用戶提供指導。

在命令式語言中,「循環」是很普遍的。在命令式語言中,階乘函數的通常寫法是用一個「for」循環,如下(用c語言):

Example
Example

例子: 命令式語言中的階乘函數

int factorial(int n) {
  int res = 1;
  for (i = 1; i <= n; i++)
    res *= i;
  return res;
}

這在Haskell中直接實現是不可能的,因為改變變量resi的值(以一種破壞性的方式)是不可以的。然而,我們依然可以將一個循環轉換為同作用的遞歸形式。重點是讓每個需要改變的循環變量變成一個遞歸函數的參數。比如,以下將上個循環「直譯」為Haskell。

Example
Example

例子: 用遞歸模擬循環

factorial n = factorialWorker 1 n 1 where
factorialWorker i n res | i <= n    = factorialWorker (i+1) n (res * i)
                        | otherwise = res

垂直號之後的表達式叫做「guards」(衛士),更詳細的可以參考control structures。現在,我們應該可以通過與以上的c語言代碼相比弄懂它是如何工作的。

很明顯,在Haskell中,要實現階乘函數,這不是一個簡明、優雅的方式,但我們應該也知道,這種翻譯也可以實現。

另一點需要提醒的是不必擔心Haskell中遞歸性能會很低。一般來說,函數式語言的編譯器都會對遞歸多所優化,包括一個重要的「尾遞歸優化」;記住:Haskell很懶,如果不必要,就不會發生。

其他遞歸函數

正如它本身所揭示的,factorial函數沒有什麼特殊之處;一大批數學函數都可以一種自然地方式遞歸定義。比如,乘法。你第一次接觸乘法(回憶一下那是什麼時候?:)),你認為那就是「重複加」而已。就是說, 5 × 4 和加四個5的結果是一樣的。當然,加四個5和先加三個5再加一個5是一樣的——也就是說, 5 × 4 = 5 × 3 + 5。這讓我們自然想到了乘法的遞歸定義形式。

Example
Example

例子: 遞歸地定義乘法

mult n 0 = 0                      -- 任何数乘 0 是 0
mult n 1 = n                      -- 任何数乘 1 是它本身
mult n m = (mult n (m - 1)) + n   -- 递归体:乘个数减1再加本身

回頭看看,我們可以看到數字遞歸式如何寫成一般遞歸形式的。數字遞歸的基線通常包括一個或更多特殊數字(通常是 0 或 1 ),對這些數字,我們可以立刻給出答案。遞歸體中,通過調用具有更小的參數的函數,相加返回值來產生結果。「更小的參數」通常比本處的參數更小,從而導致遞歸會「朝着更小的數走去」(就像factorial的例子一樣)。當然,更小的參數也可以由其他方式產生。

練習
  1. 展開 5 × 4 ,方式參考 factorial 3的展開。
  2. 定義一個遞歸函數 power ,使得 power x y 計數 xy 次冪。
  3. 已有一個函數 plusOne x = x + 1. 不使用任何 (+)(加號), 定義一個 addition,使得 addition x yxy 相加。
  4. (難) 實現函數 log2, 意思是求以 2 為底的對數。 即, log2 會計算以 2 為底的適合參數的最大的冪。比如, log2 16 = 4log2 11 = 3log2 1 = 0 。(小建議:解題之前,再看一遍最後一段。)


基於表的遞歸

Haskell中「很多」函數都是遞歸函數,尤其是跟表有關的。[3]設想一個可以計算表長度的 length 函數。

Example
Example

例子: length的遞歸定義

length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs


別被眼花繚亂的語法弄蒙了,我們會在 模式匹配 章節更深入的了解。現在,我們把代碼翻譯成人話,搞懂它如何發揮作用。第一行說明了 length的類型:它允許任何表進去,並且產生一個 Int,也就是整數。下一行表示一個空表的長度是 0 。當然,這也是基線(底線)。最後一行是遞歸區:如果一個表包括一個第一元素 x 和表的其餘部分、另外一個表 xs ,那麼表的長度是 xs 的長度加1。

那麼一個 (++) 函數,這個函數可以實現兩個表相連,該如何實現呢?(下面給出這個運算符的幾個例子,因為我們還沒見到過這個功能呢。)

{{HaskellExample|<遞歸的code>(++)函數|

Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
Prelude> "Hello " ++ "world" -- Strings are lists of Chars
"Hello world"

(++) :: [a] -> [a] -> [a]
[] ++ ys     = ys
(x:xs) ++ ys = x : xs ++ ys

length 複雜點是吧,然而掰開了講也很簡單。類型句表明 (++) 函數吸收兩個表,再產生一個表。基線句表明一個空表和一個名為 ys 的表連接還是表 ys 自身。最後一句,遞歸區把第一個表斷為頭部(x)和尾部(xs),然後將第一個表的尾部和第二個表連接,最後將頭部 x 訂在前面。

這就是模式:在基於表的函數中,基線通常和空表相關,遞歸區通常會把表的尾部再傳回函數自身以遞歸,這樣表會越來越小。

練習

給出以下基於表的函數的遞歸定義。對每一題,想想基線是什麼,而遞歸區又如何,又如何做到參數越來越小?

  1. replicat :: Int -> a -> [a],作用是接受一個數字和一個元素,返回有此數字個元素的表。比如: replicat 3 'a' = "aaa" 。(提示:考慮下0個元素的表是什麼樣子,個數 0 就是你的基線。
  2. (!!) :: [a] -> Int -> a在給出的 index(指針) 處返回元素。第一個元素是 index 0第二個是 1 ,以此類推。注意在此函數中,你得對數字和表同時「遞歸」。
  3. (有點難度) zip :: [a] -> [b] -> [(a, b)] ,拉鏈函數,將每個表中對應位置的元素連在一起,組成一個大表。比如 zip [1,2,3] "abc" = [(1, 'a'), (2, 'b'), (3, 'c')] 。如果某個表比較短,則立即停止即可。如 zip [1,2] "abc" = [(1, 'a'), (2, 'b')]

遞歸幾乎是所有表函數和數字函數的實現方法。下一次你再遇到基於表的函數時,先看看空表時的情況,再看看不空時的情況,也就知道這個算法是不是遞歸的了。呵呵。

不要太愛遞歸

雖然我們對遞歸有個牢固的理解很重要,但這並不意味着在Haskell中我們要時時用遞歸編東西。事實上,有各種各樣的用遞歸函數標準庫,你只需要使用它們就可以了。比如,一種實現factorial(階乘)函數的簡單方式是這樣的:

Example
Example

例子: 用標準庫實現 factorial 函數

factorial n = product [1..n]


簡直跟作弊差不多,對吧? :) 這就是有經驗的 Haskell 程式設計師會如何寫程序,他們不會動輒祭起遞歸這個法寶。當然, product 函數的本質就是表遞歸[4],但當我們用這種方式寫代碼的時候,不用操心其實現方式了。

概要

遞歸是一種在函數定義內部調用自身的一種做法。它幾乎都是由兩種成分構成:基線和遞歸區。遞歸在處理表和數字時特別有用。



可打印版本
習題解答
Elementary Haskell

Template:Haskell章節/Elementary Haskell

Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務


註釋

  1. 在數學上,n的階乘用n!表示,但Haskell可沒有這種語法,所以這裏我們不會這樣用。
  2. 事實上,定義0的階乘是1絕非任意,而是因為0的階乘代表了 empty product.
  3. 這並非巧合,沒有變量,遞歸是實現控制結構的唯一方法。這聽起來很像限制,但只要習慣了,它絕不會礙手礙腳。
  4. 事實上,這個函數叫做 foldl ,經常被用來實現遞歸。


模式匹配

Haskell/模式匹配

深入列表

Haskell/深入列表

控制結構

Haskell提供了幾種方式來表達在不同的值間選擇。本節描述了所有的方式並解釋了他們的用途:

if 表達式

你已經見過這些表達式了。完整的語法是:

if <condition> then <true-value> else <false-value>

這裏,條件是一個求值後得到一個布朗型的表達式。如果<條件>True的,那麼<true-value>被返回,否則<false-value>被返回。注意Haskell中if是一個(被轉化為一個值的)表達式──並非如通常的命令式語言那樣是一個(被執行的)語句。這個事實的一個非常重要的後果則是Haskell中else是"必須的"。由於if是一個表達式,它必須求值得到一個結果,else保證了這一點。由於同一原因,通常的縮進同命令式語言有所不同。如果你需要把一個if表達式分為數行,那你應採用下面的縮進方式之一:

if <condition>
   then <true-value>
   else <false-value>

if <condition>
   then
      <true-value>
   else
      <false-value>

下面是一個簡單的例子:

message42 :: Integer -> String
message42 n =
   if n == 42
      then "The Answer is forty two."
      else "The Answer is not forty two."

case表達式

One interesting way of thinking about case expressions is seeing them as a generalization of if expressions. We could even write a clone of if as a case:

alternativeIf :: Bool -> a -> a -> a
alternativeIf cond ifTrue ifFalse =
  case cond of
    True  -> ifTrue
    False -> ifFalse

First, this checks cond for a pattern match against True. If there is a match, the whole expression will evaluate to ifTrue, otherwise it will evaluate to ifFalse (since a Bool can only be True or False there is no need for a default case). case is more general than if because the pattern matching in which case selection is based allows it to work with expressions which evaluate to values of any type. [1] In fact, the left hand side of any case branch is just a pattern, so it can also be used for binding:

describeString :: String -> String
describeString str = 
  case str of
    (x:xs) -> "The first character is: " ++ [x] ++ "; the rest of the string is: " ++ xs
    ""     -> "This is an empty string."

This expression tells you whether str is an empty string or something else. Of course, you could just do this with an if-statement (with a condition of str == []), but using a case binds variables to the head and tail of our list, which is convenient in this instance.

Equations and Case Expressions

Remember you can use multiple equations as an alternative to case expressions. The describeString function above could be written like this:

describeString :: String -> String
describeString (x:xs) = "The first character is " ++ [x] ++ "; the rest of the string is " ++ xs
describeString ""     = "This is the empty string."

Named functions and case expressions at the top level are completely interchangeable. In fact the function definition form shown here is just syntactic sugar for a case expression.

One handy thing about case expressions, and indeed about Haskell control structures in general, is that since they evaluate to values they can go inside other expressions just like an ordinary expression would. For example, this case expression evaluates to a string which is then concatenated with two other strings, all inside a single expression:

data Colour = Black | White | RGB Int Int Int

describeColour :: Colour -> String
describeColour c = 
  "This colour is "
  ++ case c of
       Black           -> "black"
       White           -> "white"
       RGB 0 0 0       -> "black"
       RGB 255 255 255 -> "white"
       _               -> "freaky, man, sort of in between"
  ++ ", yeah?"

Writing this function in an equivalent way using the multiple equations style would need a named function inside something like a let block.

Guards

As shown, if we have a top-level case expression, we can just give multiple equations for the function instead, which is often neater. Is there an analogue for if expressions? It turns out there is. We use some additional syntax known as "guards". A guard is a boolean condition, like this:

describeLetter :: Char -> String
describeLetter c
   | c >= 'a' && c <= 'z' = "Lower case"
   | c >= 'A' && c <= 'Z' = "Upper case"
   | otherwise            = "Not a letter"

Note the lack of an = before the first |. Guards are evaluated in the order they appear. That is, if you have a set up similar to the following:

f (pattern1) | predicate1 = w
             | predicate2 = x
f (pattern2) | predicate3 = y
             | predicate4 = z

Then the input to f will be pattern-matched against pattern1. If it succeeds, then predicate1 will be evaluated. If this is true, then w is returned. If not, then predicate2 is evaluated. If this is true, then x is returned. Again, if not, then we jump out of this 'branch' of f and try to pattern match against pattern2, repeating the guards procedure with predicate3 and predicate4. Unlike the else in if statements, otherwise is not mandatory. Still, if no guards match an error will be produced at runtime, so it's always a good idea to provide the 'otherwise' guard, even if it is just to handle the "But this can't happen!" case (which normally does happen anyway...).

The otherwise you saw above is actually just a normal value defined in the Standard Prelude as:

otherwise :: Bool
otherwise = True

This works because of the sequential evaluation described a couple of paragraphs back: if none of the guards previous to your 'otherwise' one are true, then your otherwise will definitely be true and so whatever is on the right-hand side gets returned. It's just nice for readability's sake.

Notes

  1. Again, this is quite different from what happens in most imperative languages, in which switch/case statements are restricted to equality tests, often only on integral primitive types.



可打印版本
Haskell基礎

起步  >> 變量和函數  >> 列表和元組  >> 更進一步  >> 類型基礎  >> 簡單的輸入輸出  >> 類型聲明


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務

列表處理

Haskell/列表處理

深入函數

Haskell/深入函數

高階函數

Haskell/高階函數


Haskell進階


模塊

Haskell/模塊

縮進

Haskell/縮進

更多數據類型

Haskell/更多數據類型

類的聲明

Haskell/類的聲明

類與類型

Haskell/類與類型


Monads


理解monads

Haskell/理解monads

高級monads

Haskell/高級monads

MonadPlus

我們已經學習過, Maybe 和列表都表示了一個計算能夠擁有的結果數量. 換句話說, 我們使用 Maybe 來表示計算或許會失敗的情況 (即0種或1種結果), 我們使用列表來表示計算能夠返回0個或任意多個結果的情況.

或許有時我們會需要將兩個這些類型的計算所表示的所有結果合併起來. 比如說, 我們能夠將兩個列表 (++) 起來以"合併"兩個列表所表示的計算結果.

定義

MonadPlus 類型類定義了兩個函數. mzero 是表示沒有結果的值; mplus 則是一個將兩個計算合併的二元函數.

class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

以下是 Maybe 和列表的 instance:

instance MonadPlus [] where
  mzero = []
  mplus = (++)
 
instance MonadPlus Maybe where
  mzero                   = Nothing
  Nothing `mplus` Nothing = Nothing -- 0 个结果 + 0 个结果 = 0 个结果
  Just x  `mplus` Nothing = Just x  -- 1 个结果  + 0 个结果 = 1 个结果
  Nothing `mplus` Just x  = Just x  -- 0 个结果 + 1 个结果  = 1 个结果
  Just x  `mplus` Just y  = Just x  -- 1 个结果  + 1 个结果  = 2 个结果,
                                    -- 但是 Maybe 最多只能表示1个结果,
                                    -- 因此我们丢弃掉第二个.

另外, 在 Control.Monad.Error 模塊中, (Either e) 也定義了 MonadPlus 的 instance:

instance (Error e) => MonadPlus (Either e) where
  mzero            = Left noMsg
  Left _  `mplus` n = n
  Right x `mplus` _ = Right x

Maybe 一樣, (Either e) 表示了可能會失敗的計算. 但和 Maybe 不一樣的是, (Either e) 允許這個失敗的計算包含一條信息 (通常是一個字符串). 一般來說, Left s 表示一個信息為 s 的失敗的計算, Right x 則表示結果為 x 的成功的計算.

例子: 並行解析

傳統的輸入解析一般會使用一次"消耗"一個字符的一系列函數. 換句話說, 一個解析函數接收一個輸入字符串, 從頭部削去 (也就是所謂的"消耗") 一個滿足特定條件的字符. 比如說, 一個消耗一個大寫字符的函數. 但是如果這個頭部的字符不滿足這個特定的條件, 本次解析就失敗了; 因此在這樣的函數中使用 Maybe 或許是個好主意.

我們將使用 mplus並行運行兩個解析器. 換句話說, 如果第一個解析器成功我們就返回它的結果, 否則如果第二個成功我們就返回第二個的結果. 若兩個都失敗了, 我們返回, Nothing.

下例中, 我們消耗一個特定的數字字符並返回它所代表的數字.

digit :: Int -> String -> Maybe Int
digit i s | i > 9 || i < 0 = Nothing
          | otherwise      = do
  let (c:_) = s
  if [c] == show i then Just i else Nothing

我們的 guard 保證了我們所檢查的 Int只有一位. 然後, 我們檢查字符串的首位是否匹配我們所想要的數字. 如果匹配的話, 我們返回一個包裹在 Just 中的數字. do 代碼塊保證了失敗的任何模式匹配都將返回 Nothing.

我們使用 digitmplus 函數來解析一個由二進制位組成的字符串:

binChar :: String -> Maybe Int
binChar s = digit 0 s `mplus` digit 1 s

解析器庫一般都以類似的方式使用 MonadPlus. 好奇的話, 你可以看看 Text.ParserCombinators.ReadP 中 (+++) 函數的實現, 或者 Text.ParserCombinators.Parsec.Prim 中的 (<|>).

MonadPlus 法則

MonadPlus 的 instance 必須滿足一些法則, 就如同 Monad 的 instance 需要滿足三條 Monad 法則一樣. 不幸的是, 人們對 MonadPlus 法則並沒有達成一致的意見. 最通常的意見是, mzeromplus 需要形成一個么半群 (monoid). 換句話說:

-- mzero 是一个无具体意义的"中立"值
mzero `mplus` m  =  m
m `mplus` mzero  =  m
-- mplus 满足结合律
-- (但并不是所有的 instance 都满足这条定律, 因为这和一些无尽的值构造相悖)
m `mplus` (n `mplus` o)  =  (m `mplus` n) `mplus` o

"形成一個么半群" 並沒有什麼特別之處: 在上例中, "中立值" 和 "結合律" 可以比作整數加法的交換律和整數0. 事實上, 這也是為什麼這兩個函數叫做 mzero (m零) 和 mplus (m加).

Control.Monad 的 Haddock 文檔 額外規定了以下法則:

mzero >>= f  =  mzero
m >> mzero   =  mzero

HaskellWiki 則給出了具有爭議的另一條:

(m `mplus` n) >>= k  =  (m >>= k) `mplus` (n >>= k)

甚至還有更多的法則. 有時例如 IO 的 Monad 也會有 MonadPlus 的 instance. 參見 All About Monads 以及 Haskell Wiki.

實用函數

除了基礎的 mplusmzero, 還有兩個應用了 MonadPlus 的通用函數:

msum

處理 MonadPlus 的常見操作: 將一個列表中的 MonadPlus 值, 例如 [Maybe a][[a]], 用 mplus 進行 fold. msum 函數正是為此而生:

msum :: MonadPlus m => [m a] -> m a
msum = foldr mplus mzero

某種意義上, msum 是只能用在列表上的函數 concat 的推廣. 事實上, 當應用在列表上時這兩個函數完全相同. 對於 Maybe, msum 返回其中的第一個 Just x,若其不存在則返回 Nothing.

guard

我們注意到, 列表 monad 和列表解析之間的驚人相似, 但我們或許不是很清楚列表解析中的過濾是如何實現的. guard 就是實現的方式.

我們來看看這個計算所有勾股數 (也就是能形成直角三角形三邊長的三個數) 的列表解析. 首先我們檢查暴力的方法. 我們用一個布爾條件來過濾那些非勾股數的組合:

pythags = [ (x, y, z) | z <- [1..], x <- [1..z], y <- [x..z], x^2 + y^2 == z^2 ]

將如上的列表解析寫成列表 monad 的形式:

pythags = do
  z <- [1..]
  x <- [1..z]
  y <- [x..z]
  guard (x^2 + y^2 == z^2)
  return (x, y, z)

guard 函數的定義:

guard :: MonadPlus m => Bool -> m ()
guard True  = return ()
guard _ = mzero

具體地, 當它獲得一個 False 作為參數時, guard 會將整個 do 代碼塊的運算結果化為 mzero. 因為由於 MonadPlus 法則第一條, mzero 位於 (>>=) 左側的運算將總是得回 mzero. do 代碼塊實際上是一系列用 (>>=) 串聯起來的表達式的語法糖, 因此在任何位置出現的 mzero 都將使它的最終結果變為 mzero.

我們將擴展上面的 pythags 函數以展示 guard 在列表 monad 中的應用. 首先, 這是將 guard 特化到列表 monad 後的實現:

guard :: Bool -> [()]
guard True  = [()]
guard _ = []

簡單地說, guard 堵住了 一條運算路徑. 在 pythags 中, 我們希望能夠堵住所有 x^2 + y^2 == z^2False 的路徑 (或者說, x, yz 的組合). 讓我們在展開 do 代碼塊後的代碼:

pythags =
  [1..] >>= \z ->
  [1..z] >>= \x ->
  [x..z] >>= \y ->
  guard (x^2 + y^2 == z^2) >>= \_ ->
  return (x, y, z)

(>>=)return 替換成它們在列表 monad 中的特化 (並使用 let 綁定來增加可讀性), 我們得到如下等價代碼:

pythags =
 let ret x y z = [(x, y, z)]
     gd  z x y = concatMap (\_ -> ret x y z) (guard $ x^2 + y^2 == z^2)
     doY z x   = concatMap (gd  z x) [x..z]
     doX z     = concatMap (doY z  ) [1..z]
     doZ       = concatMap (doX    ) [1..]
 in doZ

我們注意到當它的參數為 False 時, guard 返回一個空列表. 而無論我們使用什麼函數, 對一個空列表 map 總是返回一個空列表. 因此在 gd 的 let 綁定中對於 guard 的調用中返回的空列表將使 gd 返回一個空列表, 因此 ret 也是一個空列表.

為了更好地理解, 我們可以將列表 monad 中的計算想像成一棵樹. 用我們的算法, 我們需要從頂部開始為每一個 x 的選取創建一個分支, 然後再在這些分支地下為所有 y 的選擇創建分支, z 也是同樣. 因此這棵"計算樹"會長這樣:

   start
   |____________________________________________ ...
   |                     |                    |
x  1                     2                    3
   |_______________ ...  |_______________ ... |_______________ ...
   |      |      |       |      |      |      |      |      |
y  1      2      3       2      3      4      3      4      5
   |___...|___...|___... |___...|___...|___...|___...|___...|___...
   | | |  | | |  | | |   | | |  | | |  | | |  | | |  | | |  | | |
z  1 2 3  2 3 4  3 4 5   2 3 4  3 4 5  4 5 6  3 4 5  4 5 6  5 6 7


每一個 x, y 和 z 的組合都代表了樹中的一條路徑. 當所有計算完成以後, 每一個分支被從下至上合併起來. 任何不滿足條件的路徑此時被轉化成空列表, 因此對合併過程沒有影響.

練習
  1. 證明 Maybe 和列表確實滿足 MonadPlus 法則.
  2. 我們能夠修改上面的解析器, 使其接收任意字符:
     -- | 消耗输入中的一个指定字符, 返回一个二元组,
          其中包含了这个字符以及余下的字符串. 我们用
          一个 do 代码块使得任意位置失败的模式匹配
          都将返回 Maybe 的"失败状态" (也就是 Nothing)
     char :: Char -> String -> Maybe (Char, String)
     char c s = do
       let (c':s') = s
       if c == c' then Just (c, s') else Nothing
    
    此時我們能夠實現一個 hexChar 函數, 其接收任何合法的十六進制數字符 (0-9 或 a-f). 試着實現這個函數 (提示: map digit [0..9] :: [String -> Maybe Int]).

和 Monoid 的關係

當我們討論 MonadPlus 法則時, 我們提到了數學上的么半群 (Monoid). 事實上 Haskell 中存在着一個 Monoid 類型類, 詳細教程請參見Haskell趣學指南中的章節:

class Monoid m where 
  mempty  :: m
  mappend :: m -> m -> m

列表是一個簡單的 monoid:

instance Monoid [a] where
  mempty  = []
  mappend = (++)

看起來是不是很熟悉呢? 儘管和 MonadPlus 有些相似, 它們有一點關鍵而微妙的區別. 注意在 instance 聲明中我們使用了 [a] 而不是 []. Monoid 並不一定是其他類型的"容器", 或者說不一定是多態的. 比如說, 整數加法構成了一個 Monoid, 其中"中立值" (mempty) 為0.

確實, MonadPlus 的 instance 看起來和 Monoid 類似, 因為兩者都有"零"和"加"的概念. 事實上, 我們能夠讓 MonadPlus 成為 Monoid 的子類 (如果值得這番功夫的話):

 instance MonadPlus m => Monoid (m a) where
   mempty  = mzero
   mappend = mplus
註解

由於 instance 聲明中自由變量 a 的存在, 上述代碼在 Haskell 98 中並不合法. 除非你開啟 GHC 的 語言擴展 FlexibleInstances:

  • 如果你使用的是 GHCi, 使用參數 -XFlexibleInstances 啟動它或者在交互提示符下輸入 :set -XFlexibleInstances.
  • 如果你編譯後再運行程序的話, 在源文件第一行加上 {-# LANGUAGE FlexibleInstances #-}.

我們重申一下, MonoidMonadPlus 工作與不同的"層次". 正如之前所說, Monoid 並不一定是其他類型的"容器", 或者說不一定是多態的. 更加正式地, Monoid 的 kind 為 *, 但 MonadPlus 的 instance 的 kind 為 * -> *. (後者本身也是 Monad).

Template:Haskell/NotesSection



可打印版本
習題解答
Monads

理解 Monad  >> 高級 Monad  >> Monad 進階  >> MonadPlus  >> Monadic parser combinators  >> Monad transformers  >> Monad 實務


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務

Monad transformers

我們已經學習了Monad能夠如何簡便對於 IO, Maybe, 列表, 和 State 的處理. 每一個Monad都是如此的有用且用途廣泛, 我們自然會尋求將幾個Monad的特性組合起來的方法. 比如, 也許我們可以定義一個既能處理I/O操作, 又能使用 Maybe 提供的異常處理的函數. 雖然這可以用形如 IO (Maybe a) 的函數實現, 但是在這種方式下我們將被迫在 IO 的 do 代碼塊中手工模式匹配提取值, 而避免寫出這種繁瑣而無謂的代碼卻恰恰是 Maybe Monad存在的原因.

於是我們發明了 monad transformers: 它們能夠將幾種Monad的特性融合起來, 同時不失去使用Monad的靈活性.

密碼驗證

我們先來看一看這個幾乎每一個IT從業人員都會遇到的實際問題: 讓用戶設置足夠強的密碼. 一種方案是: 強迫用戶輸入大於一定長度, 且滿足各種惱人要求的密碼 (例如包含大寫字母, 數字, 字符, 等等).

這是一個用於從用戶處獲取密碼的Haskell函數:

getPassphrase :: IO (Maybe String)
getPassphrase = do s <- getLine
                   if isValid s then return $ Just s
                                else return Nothing

-- 我们可以要求密码满足任何我们想要的条件
isValid :: String -> Bool
isValid s = length s >= 8
            && any isAlpha s
            && any isNumber s
            && any isPunctuation s

首先, getPassphrase 是一個 IO Monad, 因為它需要從用戶處獲得輸入. 我們還使用了 Maybe, 因為若密碼沒有通過 isValid 的建議, 我們決定返回 Nothing. 需要注意的是, 我們在這裏並沒有使用到 Maybe 作為Monad的特性: do 代碼塊的類型是 IO monad, 我們只是恰巧 return 了一個 Maybe 類型的值罷了.

Monad transformers 不僅僅使 getPassphrase 的實現變簡單了, 而且還能夠簡化幾乎所有運用了多個monad的代碼. 這是不使用Monad transformers的程序:

askPassphrase :: IO ()
askPassphrase = do putStrLn "输入新密码:"
                   maybe_value <- getPassphrase
                   if isJust maybe_value
                     then do putStrLn "储存中..." -- 假装存在数据库操作
                     else putStrLn "密码无效"

這段代碼單獨使用了一行來獲得 maybe_value, 然後又手工對它進行驗證.

如果使用 monad transformers, 我們將可以把獲得輸入和驗證這兩個步驟合二為一 — 我們將不再需要模式匹配或者等價的 isJust. 在我們的簡單例子中, 或許 monad transformers 只作出了微小的改進, 但是當問題規模進一步擴大時, 它們將發揮巨大的作用.

一個簡單的 monad transformer: MaybeT

為了簡化 getPassphrase 以及所有使用到它的函數, 我們定義一個賦予 IO monad 一些 Maybe monad 特性的 monad transformer; 我們將其命名為 MaybeT. 一般來說, monad transformers 的名字都會以 "T" 結尾, 而之前的部分 (例如, 在本例中是"Maybe") 表示它所提供的特性.

MaybeT 是一個包裝 (wrap) 了 m (Maybe a) 的類型, 其中 m 可以是任何Monad (在本例中即為 IO):

newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }

這裏的 datatype 聲明定義了 MaybeT, 一個被 m 參數化的類型構造子 (type constructor), 以及一個值構造函數 (value constructor), 同樣被命名為 MaybeT, 以及一個作用為簡便的內部值訪問的函數 runMaybeT.

Monad transformers 的關鍵在於 他們本身也是monads; 因此我們需要寫出 MaybeT mMonad 類型類實例:

instance Monad m => Monad (MaybeT m) where
    return  = MaybeT . return . Just

首先, 我們先用 Just 將值裝入最內層的 Maybe 中, 然後用 return 將前述 Maybe 裝入 m monad里, 最後再用 MaybeT 將整個值包裝起來.


我們也可以這樣實現 (雖然是不是增加了可讀性仍然有待商榷) return = MaybeT . return . return.

如同在所有monad中一樣, (>>=) 也是 transformer 的核心.

-- 特化为 MaybeT m 的 (>>=) 函数类型签名 
(>>=) :: MaybeT m a -> (a -> MaybeT m b) -> MaybeT m b

x >>= f = MaybeT $ do maybe_value <- runMaybeT x
                      case maybe_value of
                           Nothing    -> return Nothing
                           Just value -> runMaybeT $ f value

我們從 do 代碼塊的第一行開始解釋:

  • 首先, runMaybeTx 中取出 m (Maybe a). 我們由此可知整個 do 代碼塊的類型為 monad m.
  • 第一行稍後, <- 從上述值中取出了 Maybe a.
  • case 語句對 maybe_value 進行檢測:
    • 若其為 Nothing, 我們將 Nothing 返回至 m 當中;
    • 若其為 Just, 我們將函數 f 應用到其中的 value 上. 因為 f 的返回值類型為 MaybeT m b, 我們需要再次使用 runMaybeT 來將其返回值提取回 m monad 中.
  • 最後, do 代碼塊的類型為 m (Maybe b); 因此我們用 MaybeT 值構造函數將它包裝進 MaybeT 中.

這咋看來獲取有些複雜; 但是若剔除大量的包裝和解包裝, 我們的代碼和 Maybe monad 的實現其實很像:

-- Maybe monad 的 (>>=)
maybe_value >>= f = case maybe_value of
                        Nothing -> Nothing
                        Just value -> f value

我們在 do 代碼塊中仍然能夠使用 runMaybeT, 為何要在前者上應用 MaybeT 值構造函數呢? 這是因為我們的 do 代碼塊必須是 m monad, 而不是 MaybeT m monad, 因為後者此時還沒有定義 (>>=). (回想一下 do 語法糖是如何工作的)

註解

return 的實現中層層相疊的函數也許可以為我們提供一個(或許)有助於理解的比喻: 將複合的 monad 想像為一個 三明治; 雖然這個比喻似乎在暗示實際上有三個 monad 在起作用, 但是實際上只有兩個: 內層的以及"融合了的" monad. 置於基層的 monad (本例中即Maybe) 中並沒有用到 (>>=) 或者 return, 它只是作為 transformer 實現的一部分罷了. 如果你覺得這個比喻很有道理, 將 transformer 和 底層 monad 想像成三明治的兩片包裹着內層 monad 的麵包. [1]

理論上, 這就是我們所需的全部了; 但是, 為 MaybeT 實現幾個其他類型類的 instance 又何妨呢?

instance Monad m => MonadPlus (MaybeT m) where
    mzero     = MaybeT $ return Nothing
    mplus x y = MaybeT $ do maybe_value <- runMaybeT x
                            case maybe_value of
                                 Nothing    -> runMaybeT y
                                 Just _     -> return maybe_value

instance MonadTrans MaybeT where
    lift = MaybeT . (liftM Just)

MonadTrans monad 實現了 lift 函數, 由此我們可以在 MaybeT m monad 的 do 代碼塊中使用m monad 的值. 至於 MonadPlus, 因為 Maybe 有着這個類型類的 instance, MaybeT 也應該有着對應的 instance.

應用在密碼驗證的例子中

現在, 前例的密碼管理可以被改寫為:

getValidPassphrase :: MaybeT IO String
getValidPassphrase = do s <- lift getLine
                        guard (isValid s) -- MonadPlus 类型类使我们能够使用 guard.
                        return s

askPassphrase :: MaybeT IO ()
askPassphrase = do lift $ putStrLn "输入新密码:"
                   value <- getValidPassphrase
                   lift $ putStrLn "储存中..."

這段代碼簡潔多了, 特別是 askPassphrase 函數. 最重要的是, 有着 (>>=) 為我們代勞, 我們不再需要手動檢查結果是 NothingJust 中的哪一個了.

我們使用了 lift 函數以在 MaybeT IO monad 中使用 getLineputStrLn; 因為 MaybeT IO 有着 MonadPlus 類型類的 instance, guard 可以為我們檢查代碼的合法性. 在密碼不合法時其將返回 mzero (即 IO Nothing).

碰巧, 有了 MonadPlus, 我們可以優雅地不停要求用戶輸入一個合法的密碼:

askPassword :: MaybeT IO ()
askPassword = do lift $ putStrLn "输入新密码:"
                 value <- msum $ repeat getValidPassphrase
                 lift $ putStrLn "储存中..."

泛濫的 transformer

transformers 包提供了許多包含常見 monad 的 transformer 版本的模塊 (例如 Template:Haskell lib 模塊提供了 MaybeT). 它們和對應的非 transformer 版本 monad 是兼容的; 換句話說, 除去一些和另一個 monad 交互所用到的包裝和解包裝 , 它們的實現基本上是一致的. 從今往後, 我們稱 transformer monad 所基於的非 transformer 版本的 monad 為 基層 monad (例如 MaybeT 中的 Maybe); 以及稱應用在 transformer 上的 monad 為 內層 monad (例如 MaybeT IO 中的 IO).

我們隨便舉一個例子, ReaderT Env IO String. 這是一個能夠從某個外部環境讀取 Env 類型的值 (並且和 Reader, 也就是基 monad, 使用方法相同) 並且能夠進行一些I/O, 最後返回一個 String 類型的值的 monad. 由於這個 transformer 的 (>>=)return 語義和基 monad 相同, 一個 ReaderT Env IO String 類型的 do 語句塊從外部看來和另一個 Reader 類型的 do 語句塊並無二致, 除了我們需要用 lift 來使用 IO monad.

類型戲法

我們已經了解到, MaybeT 的類型構造子實際上是一個對內層 monad 中的 Maybe 值的包裝. 因此, 用於取出內部值的函數 runMaybeT 返回給我們一個類型為 m (Maybe a) 的值 - 也就是一個由內層 monad 包裝着的基 monad 值. 類似的, 對於分別基於列表和 Either 構建的 ListTExceptT transformer:

runListT :: ListT m a -> m [a]

and

runExceptT :: ExceptT e m a -> m (Either e a)

然而並不是所有的 transformer 都和它們的基 monad 有着類似的關係. 不同於上面兩例所給出的基 monad, Writer, Reader, State, 以及 Cont monad 既沒有多個值構造子, 也沒有接收多個參數的值構造函數. 因此, 它們提供了形如 run... 的函數以作為解包裝函數, 而它們的 transformer 則提供形如 run...T 的函數. 下表給出了這些 monad 的 run...run...T 函數的類型, 而這些類型事實上就是包裝在基 monad 和對應的 transformer 中的那些. [2]

基 Monad Transformer 原始類型
(被基 monad 包裝的類型)
複合類型
(被 transformer 包裝的類型)
Writer WriterT (a, w) m (a, w)
Reader ReaderT r -> a r -> m a
State StateT s -> (a, s) s -> m (a, s)
Cont ContT (a -> r) -> r (a -> m r) -> m r

我們可以注意到, 基 monad 並沒有出現在複合的類型中. 這些 monad 並沒有一個像 Maybe 或列表那樣的有意義的構造函數, 因此我們選擇不在 transformer monad 中保留基 monad. 值得注意的是, 在後三個例子中我們包裝的值是函數. 拿 StateT 作例子, 將原有的表示狀態轉換的 s -> (a, s) 函數變為 s -> m (a, s) 的形式; 然而我們只將函數的返回值 (而不是整個函數) 包裝進內層 monad 中. ReaderT 也與此差不多. ContT 卻與它們不同: 由於 Cont (表示延續的 monad) 的性質, 被包裝的函數和作這個函數參數的函數返回值必須相同, 因此 transformer 將兩個值都包裝入內層 monad 中. 遺憾的是, 並沒有一種能將普通的 monad 轉換成 transformer 版本的萬靈藥; 每一種 transformer 的實現都和基 monad 的行為有關.

Lifting

我們將仔細研究 lift 函數: 它是應用 monad transformers 的關鍵. 首先, 我們需要對它的名字 "lift" 做一些澄清. 在理解_Monad中, 我們已經學習過一個名字類似的函數 liftM. 我們了解到, 它實際上是 monad 版本的 fmap:

liftM :: Monad m => (a -> b) -> m a -> m b

liftM 將一個類型為 (a -> b) 的函數應用到一個 m monad 內的值上. 我們也可以將它視為只有一個參數:

liftM :: Monad m => (a -> b) -> (m a -> m b)

liftM 將一個普通的函數轉換為在 m monad 上運作的函數. 我們用"提升(lifting)"表示將一樣東西帶至另一樣東西中 — 在前例中, 我們將一個函數提升到了 m monad 中.

有了 liftM, 我們不需要用 do 代碼塊或類似的技巧就能夠把尋常的函數應用在 monad 上了:

do notation liftM
do x <- monadicValue
   return (f x)
liftM f monadicValue

類似的, lift 函數在 transformer 上起到了一個相似的作用. 它將內層 monad 中的計算帶至複合的 monad (即 transformer monad) 中. 這使得我們能夠輕易地在複合 monad 中插入一個內層 monad 的運算.

liftMonadTrans 類型類的唯一一個函數, 參見 Template:Haskell lib. 所有的 transformer 都有 MonadTrans 的 instance, 因此我們能夠在任何一個 transformer 上使用 lift.

class MonadTrans t where
    lift :: (Monad m) => m a -> t m a

lift 存在一個 IO 的變種, 名叫 liftIO; 這是 MonadIO 類型類的唯一一個函數, 參見 Template:Haskell lib.

class (Monad m) => MonadIO m where
   liftIO :: IO a -> m a

當多個 transformer 被組合在一起時, liftIO 能夠帶來一些便利. 在這種情況下, IO 永遠是最內層的 monad (因為不存在 IOT transformer), 因此一般來說我們需要多次使用 lift 以將 IO 中的值從底層提升至複合 monad 中. 定義了 liftIO instance 的類型被設計成能夠使用 liftIOIO 從任意深的內層一次性提升到 transformer monad 中.

實現 lift

lift 並不是很複雜. 以 MaybeT transformer 為例:

instance MonadTrans MaybeT where
    lift m = MaybeT (liftM Just m)

我們從接收到一個內層 monad 中的值的參數開始. 我們使用 liftM (或者 fmap, 因為所有Monad都首先是Functor) 和 Just 值構造函數來將基 monad 插入內層 monad 中, 以從 m a 轉化為 m (Maybe a)). 最後, 我們使用 MaybeT 值構造函數將三明治包裹起來. 值得注意的是, 此例中 liftM 工作於內層 monad 中, 如同我們之前看到的 MaybeT(>>=) 實現中的 do 代碼塊一樣.

練習
  1. 為什麼 lift 必須為每一個 monad transformer 單獨定義, 但 liftM 卻可以只實現一次呢?
  2. Identity 是一個定義於 Data.Functor.Identity 中實際意義不大的 functor:
    newtype Identity a = Identity { runIdentity :: a }
    它有着如下的 Monad instance:
    instance Monad Identity where
        return a = Identity a
        m >>= k  = k (runIdentity m)
    
    實現一個 monad transformer IdentityT, 這個 transformer 和 Identity 類似, 但是將值包裹在 m a 而不是 a 類型的值中. 請你至少寫出它的 MonadMonadTrans instances.

實現 transformers

State transformer

作為一個額外的例子, 我們將試着實現 StateT. 請確認自己了解 State 再繼續. [3]

正如同 State monad 有着 newtype State s a = State { runState :: (s -> (a,s)) } 的定義一樣, StateT transformer 的定義為:

newtype StateT s m a = StateT { runStateT :: (s -> m (a,s)) }

StateT s m 有着如下的 Monad instance, 旁邊用基 monad 作為對比:

State StateT
newtype State s a =
  State { runState :: (s -> (a,s)) }

instance Monad (State s) where
  return a        = State $ \s -> (a,s)
  (State x) >>= f = State $ \s ->
    let (v,s') = x s
    in runState (f v) s'
newtype StateT s m a =
  StateT { runStateT :: (s -> m (a,s)) }

instance (Monad m) => Monad (StateT s m) where
  return a         = StateT $ \s -> return (a,s)
  (StateT x) >>= f = StateT $ \s -> do
    (v,s') <- x s          -- 取得新的值和状态
    runStateT (f v) s'     -- 将它们传递给 f

我們的 return 實現使用了內層 monad 的 return 函數. (>>=) 則使用一個 do 代碼塊來在內層 monad 中進行計算.

註解

現在我們能夠解釋, 為什麼在 State monad 中存在手工定義的 state 卻沒有與類型一同定義的 State 值構造函數了. 在 transformersmtl 包中, State s 被定義為 StateT s Identity 的類型別名, 其中 Identity 是在本章練習中出現的沒有特別效果的 monad. 這個定義和我們迄今為止所見的使用 newtype 的定義是等價的.

為了將 StateT s m monad 同 State monad 一般使用, 我們自然需要核心的 getput 函數. 這裏我們將使用 mtl 的代碼風格. mtl 不僅僅提供了 monad transformers 的定義, 還提供了定義了常見 monad 的關鍵操作的類型類. 例如, Template:Haskell lib 包所提供的 MonadState 類型類, 定義了 getput 函數:

instance (Monad m) => MonadState s (StateT s m) where
  get   = StateT $ \s -> return (s,s)
  put s = StateT $ \_ -> return ((),s)
註解

instance (Monad m) => MonadState s (StateT s m) 的意思是: "對於任何類型 s 以及任何是 Monad instance 的類型 m, sStateT s m 共同組成了一個 MonadState 的 instance". sm 分別對應了 state monad 和內層 monad. 類型參數 s 是 instance 聲明的一個獨立部分, 因此函數能夠訪問到 s: 舉個例子, put 的類型為 s -> StateT s m ().

存在為其他 transformer 包裝着的 state monad 所定義的 MonadState instance, 例如 MonadState s m => MonadState s (MaybeT m). 這些 instance 使得我們不再需要寫出 lift 來使用 get and put, 因為複合 monad 的 MonadState instance 為我們代勞了.

我們還可以為複合 monad 實現內層 monad 所擁有的一些類型類 instance. 例如, 所有包裝了 StateT (其擁有 MonadPlus instance) 的複合 monad 也同樣能夠擁有 MonadPlus 的 instance:

instance (MonadPlus m) => MonadPlus (StateT s m) where
  mzero = StateT $ \_ -> mzero
  (StateT x1) `mplus` (StateT x2) = StateT $ \s -> (x1 s) `mplus` (x2 s)

mzeromplus 的實現符合我們的直覺; 它們將實際的操作下推給內層 monad 來完成.

最後, monad transformer 必須有 MonadTrans 的 instance, 不然我們無法使用 lift:

instance MonadTrans (StateT s) where
  lift c = StateT $ \s -> c >>= (\x -> return (x,s))

lift 函數返回一個包裝在 StateT 中的函數, 其接受一個表示狀態的值 s 作為參數, 返回一個函數, 這個函數接受一個內層 monad 中的值, 並將它通過 (>>=) 傳遞給一個將其和狀態打包成一個在內層 monad 中的二元組的函數. 舉個例子, 當我們在 StateT transformer 中使用列表時, 一個返回列表的函數 (即一個在列表 monad 中的計算) 在被提升為 StateT s []後, 將變成一個返回 StateT (s -> [(a,s)]) 的函數. 換句話說, 這個函數用初始狀態產生了多個 (值, 新狀態) 的二元組. 我們將 StateT 中的計算 "fork" 了, 為被提升的函數返回的列表中的每一個值創建了一個計算分支. 當然了, 將 StateT 和不同的 monad 組合將產生不同效果的 lift 函數.

練習
  1. 使用 getput 來實現 state :: MonadState s m => (s -> (a, s)) -> m a.
  2. MaybeT (State s)StateT s Maybe 等價嗎? (提示: 比較兩個 run...T 函數的返回值.

致謝

本章摘取了 All About Monads, 已取得作者 Jeff Newbern 的授權.

Template:Haskell/NotesSection



可打印版本
習題解答
Monads

理解 Monad  >> 高級 Monad  >> Monad 進階  >> MonadPlus  >> Monadic parser combinators  >> Monad transformers  >> Monad 實務


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務

monads實務

Haskell/monads實務


高級Haskell


Arrows

Haskell/Arrows

Understanding arrows

Haskell/Understanding arrows

Continuation passing style

Haskell/Continuation passing style

Mutable objects

Haskell/Mutable objects

Zippers

Haskell/Zippers


類型的樂趣


Existentially quantified types

Haskell/Existentially quantified types

Polymorphism

Haskell/Polymorphism

Advanced type classes

Haskell/Advanced type classes

Phantom types

Haskell/Phantom types

GADT

Haskell/GADT


理論提升


Denotational semantics

Haskell/Denotational semantics

Equational reasoning

Haskell/Equational reasoning

Program derivation

Haskell/Program derivation

Category theory

Haskell/Category theory


Haskell性能


Graph reduction

Haskell/Graph reduction

Laziness

Haskell/Laziness

Strictness

Haskell/Strictness

Algorithm complexity

Haskell/Algorithm complexity

Concurrency

Haskell/Concurrency

Choosing data structures

Haskell/Choosing data structures


程序庫參考


Hierarchical libraries

Haskell/Hierarchical libraries

Hierarchical libraries/Lists

Haskell/Hierarchical libraries/Lists

Hierarchical libraries/Randoms

Haskell/Hierarchical libraries/Randoms


普通實務


Applications

Haskell/Applications

Debugging/

Haskell/Debugging/

Testing

Haskell/Testing

Packaging

Haskell/Packaging


專門任務


GUI

Haskell/GUI

Database

Haskell/Database

Web programming

Haskell/Web programming

XML

Haskell/XML

  1. 譯者並沒有看懂這個比喻, 請批判性地閱讀. 看得懂的人希望能夠幫忙確認或修改.
  2. 嚴格意義上, 這個解釋只在大於 2.0.0.0 版本的 mtl 包中成立.
  3. 譯註: 此處作者引用了 理解_Monad 中的內容, 然而譯時此章節並沒有翻譯完成.