Haskell

GHC (Glasgow Haskell Compiler) 是开源的 Haskell 编译器。GHC 起源于英国的格拉斯哥大学（University of Glasgow）。

GHC 主要包含下面命令行工具：

Haskell 程序的入口程序是 Main 模块的 main 函数。

下面是 Hello world 程序（假设文件名为 hello-world.hs）：

main = putStrLn "Hello world"

执行方式一：使用 ghc 把它编译为二进制可执行程序后，再执行。

$ ghc hello-world.hs -o hello-world
[1 of 1] Compiling Main             ( hello-world.hs, hello-world.o )
Linking hello-world ...
$ ./hello-world
Hello world

执行方式二：使用 runghc 直接执行它。

$ runghc hello-world.hs
Hello world

Haskell 程序可保存到文件（一般使用.hs 后缀）中。

假设文件 test.hs 的内容为：

double x = x + x              -- 定义了名为double的函数

ghci 后接文件名，可以加载文件内容到 Haskell 交互式环境中（也可以启动交互式环境后使用 :load 命令加载文件）。如：

$ ghci test.hs
GHCi, version 7.8.4: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> double 3
6

如果文件 test.hs 修改了，可以通过在 GHCi 提示符中输入 :reload 命令来重新加载文件。

Haskell 是函数式语言。函数在 Haskell 中占据非常重要的位置，不过，函数调用的风格和数学中函数的调用是有差异的。见表 3 所示。

A type is a collection of related values.

Haskell 是“静态类型”的语言，表达式的类型在编译阶段就已经确定了。 这使得代码更加安全，比如你尝试对字符串进行除法运算时，编译器会拒绝这样的代码。
Haskell 具有强大的“类型推导”系统，你往往可以省略类型的声明，编译器自己会推导出具体类型。

表 4 是 Haskell 中的基本类型。

Haskell 中，List 是“相同类型”元素组成的序列。List 的格式为元素之间使用逗号分隔，所有元素用方括号包围。如 [False, False, True] 。

如果 List 的元素类型是 T，则使用 [T] 表示该 List 的类型。如：

Prelude> :type [False, False, True]
[False, False, True] :: [Bool]
Prelude> :type ['a', 'b', 'c']
['a', 'b', 'c'] :: [Char]
Prelude> :type ["one", "two", "three"]
["one", "two", "three"] :: [[Char]]

List 的长度可以是无限的。

Tuple 是长度有限的元素序列，它的元素类型可以不相同。Tuple 的格式为元素之间使用逗号分隔，所有元素用小括号包围。如 (False, 'a', True) 。

如果 Tuple 的元素类型分别为 T1, T2, ..., Tn，则使用 (T1, T2, ..., Tn) 表示该 Tuple 的类型。如：

Prelude> :type (False, 'a', True)
(False, 'a', True) :: (Bool, Char, Bool)
Prelude> :type (False, "Hello")
(False, "Hello") :: (Bool, [Char])

注：Tuple 的长度必须是有限的，这样才可能推导出 Tuple 的具体类型。

函数是从参数到返回值的映射。

如果函数的参数类型为 T1，返回值类型为 T2，则使用 T1 -> T2 表示该函数的类型。如：

Prelude> :type not
not :: Bool -> Bool         -- 函数not的参数类型是Bool，返回值类型也是Bool

下面是接受 Tuple 为参数的函数的例子。

add       :: (Int, Int) -> Int   -- 声明函数类型
add (x,y) = x+y                  -- 定义函数add，它的参数是一个Tuple，返回值是Int

在交互环境中声明函数类型比较麻烦，你可以先保存到文件中，再使用 :load file1.hs 命令加载到交互环境中，再用 :type add 来查看其函数 add 的类型。
函数 add 的类型为 (Int,Int) -> Int ，表明它接收一个类型为 (Int, Int) 的参数（Tuple 类型），返回值类型为 Int。

上面介绍的函数类型，其参数个数都为 1，下节将介绍参数个数大于 1 的函数的类型。

把接受多个参数的函数转换为接受单个参数的函数的过程，称为柯里化。Haskell 支持自动柯里化。比如，你定义了一个函数 add' ，它接受 2 个参数。如：

add' x y = x + y     -- 这个函数（接受两个参数）和前面介绍的函数add（接受一个类型为Tuple的参数）不同

我们可以这样调用它： add' 1 2 （函数 add' 接受两个参数）。其实，我们还可以这样调用它： (add' 1) 2 ，这表明 (add' 1) 返回另外一个函数，这个函数接受一个参数。这就是 Haskell 的自动柯里化。

如何表示函数 add' 的类型呢？可以这样 Int -> Int -> Int ，它等同于 Int -> (Int -> Int) 。

下面是一个接受 3 个参数的函数的例子。

mult       :: Int -> Int -> Int -> Int    -- same as Int -> (Int -> (Int -> Int))
mult x y z = x*y*z

库函数 head 可以得到任何类型 List 的首个元素。如：

Prelude> head [1, 3, 5]
1
Prelude> head [True, False]
True

head 可接受任意类型的 List，那如何表示它的类型呢？常用 [a] -> a 来表示 head 的类型，其中小写字母 a （也可使用其它小写字母，如 b, c 等等）表示“多种类型”，函数 head 称为 Polymorphic function，其类型 [a] -> a 称为 Polymorphic type.

又如， take 也是一个 Polymorphic function，它的类型 Int -> [a] -> [a] 是 Polymorphic type.

Prelude> take 4 [1, 3, 5, 7, 9]
[1,3,5,7]
Prelude> :type take
take :: Int -> [a] -> [a]

我们知道，函数 abs 可以对数字类型求绝对值，其中数字类型可以是整数，还可以是单精度浮点数，双精度浮点数等等。

Prelude> abs (-1)
1
Prelude> abs (-2.5)
2.5

怎么表示函数 abs 的类型呢？写为 Polymorphic 类型 a -> a 是不够准确的，因为 abs 接受的类型仅仅是数字类型。

函数 abs 的类型可记为 Num a => a -> a （可以通过 :type abs 来验证）。 符号 => 前面的内容 Num a 被称为 class constraint，它的含义是“type a is an instance of the class Num”。 关于 class Num ，下节将介绍。

函数 abs 称为 Overloaded function，其类型 Num a => a -> a 称为 Overloaded type.

下面是其它一些 Overloaded function:

Prelude> :type abs
abs :: Num a => a -> a
Prelude> :type negate
negate :: Num a => a -> a
Prelude> :type (*)
(*) :: Num a => a -> a -> a
Prelude> :type (+)
(+) :: Num a => a -> a -> a

上一节介绍了 Class constraint，这里将介绍 Class 的概念。

Recall that a type is a collection of related values. Building upon this notion, a class is a collection of types that support certain overloaded operations called methods.

测试 method 类型时，会显示对应的 class 名字。如：

Prelude> :type (==)
(==) :: Eq a => a -> a -> Bool
Prelude> :type (<)
(<) :: Ord a => a -> a -> Bool
Prelude> :type show
show :: Show a => a -> String
Prelude> :type read
read :: Read a => String -> a
Prelude> :type negate
negate :: Num a => a -> a
Prelude> :type div
div :: Integral a => a -> a -> a
Prelude> :type (/)
(/) :: Fractional a => a -> a -> a

下面是使用 method 的一些测试：

Prelude> [1, 2] == [1, 2]       -- 判断是否相等
True
Prelude> 1 /= 2                 -- 判断是否不相等，Haskell中“不等于”用 /= 表示
True
Prelude> show False
"False"
Prelude> show 123
"123"
Prelude> read "False" :: Bool
False
Prelude> recip 3                -- 取倒数
0.3333333333333333

定义函数最直接的办法是借助于已经存在的函数。

例如，定义测试偶数的函数：

even   :: Integral a => a -> Bool
even n = n `mod` 2 == 0

通过 if ... then .. else ... 是定义函数的常用方式。

例如，内置函数 abs 可以像下面这样定义：

abs   :: Int -> Int
abs n = if n >= 0 then n else -n

if ... then .. else ... 可以嵌套使用。例如，内置函数 signum 可以像下面这样定义：

signum   :: Int -> Int
signum n = if n < 0 then -1 else
               if n == 0 then 0 else 1

注：和其它语言不同， if ... then .. else ... 中的 else 部分是不可以省略了，这样避免了“dangling else”问题。

Haskell 中函数还可以通过“一系列逻辑表达式”来定义（这些逻辑表达式被称为 Guards）。如果第一个逻辑表达式成立，则采用第一个逻辑表达式后面关联的定义；如果第二个逻辑表达式成立，则采用第二个逻辑表达式后面关联的定义；依此类推。

例如，内置函数 abs 可以像下面这样定义：

abs n | n ≥ 0 = n
      | otherwise = −n         -- 也可写为 True = -n ，不过 otherwise 更容易阅读

其中，符号 | 可理解为“such that”， otherwise 在内置库中被定义为 True 。

内置函数 signum 可以像下面这样定义：

signum n | n < 0 = −1
         | n == 0 = 0
         | otherwise = 1

定义函数时，我们可以拆分函数主体为几个 pattern，然后分别对 pattern 进行定义。

比如，使用 Pattern matching，函数 not 可以这样定义：

not :: Bool -> Bool
not False = True
not True  = False

又如，使用 Pattern matching，我们可以这样定义函数 intToWeekdayName ，它把数字转换为星期：

intToWeekdayName :: (Integral a) => a -> String
intToWeekdayName 1 = "Monday"
intToWeekdayName 2 = "Tuesday"
intToWeekdayName 3 = "Wednesday"
intToWeekdayName 4 = "Thursday"
intToWeekdayName 5 = "Friday"
intToWeekdayName 6 = "Friday"
intToWeekdayName 7 = "Sunday"

又如，使用 Pattern matching，函数 factorial 可以这样定义：

factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)

下面的例子演示了使用 Pathern matching 来定义操作符 && ：

(&&) :: Bool -> Bool -> Bool
True && True   = True
True && False  = False
False && True  = False
False && False = False

不过，上面 && 的定义可以简化为：

(&&) :: Bool -> Bool -> Bool
True && True   = True
_ && _         = False

其中，下划线 _ 称为“wildcard pattern”，它能匹配任意值。 && 还可以定义为下面形式：

(&&) :: Bool -> Bool -> Bool
True && b   = b         -- if the first argument is True, then the result is the value of the second argument
False && _  = False     -- if the first argument is False, then the result is False

Case 表达式语法如下：

case expression of pattern -> result
                   pattern -> result
                   pattern -> result
                   ...

用 Case 表达式可以定义函数。如：

head' :: [a] -> a
head' xs = case xs of []    -> error "No head for empty lists!"
                      (x:_) -> x

上面的定义也可用“Pattern matching”来实现：

head' :: [a] -> a
head' []    = error "No head for empty lists!"
head' (x:_) = x

可以认为“Pattern matching”是“Case expressions”的语法糖。

Lambda expressions 就是匿名函数。

比如，接受一个数字 x 为参数，返回 x + x 的匿名函数可表示为： \x -> x + x 。测试如下：

Prelude> (\x -> x + x) 3
6

我们知道，函数 add 可定义为：

add :: Int -> Int -> Int
add x y = x + y

如果使用 Lambda 表达式，则又可定义为：

add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)

仅被引用一次的函数很多时间没必要给它取名字，这时往往改写为匿名函数。比如：

odds :: Int -> [Int]
odds n = map f [0..n-1]             -- map 是内置库函数，它的第一个参数是函数，第二个参数是列表。函数 f 的定义在下一行
             where f x = x*2 + 1    -- where 表示后面的函数 f 是局部定义的

上面函数 odds 中定义的局部函数 f 仅被引用了一次，可以直接把它改写为 Lambda expressions（匿名函数）。

odds :: Int -> [Int]
odds n = map (\x -> x*2 + 1) [0..n-1]

如果一个函数（如 + ）在调用时，函数名写在它的两个参数之间，则把它称为“操作符”。

任何具有两个参数的函数，其调用形式都可以转换为“操作符”调用形式。转换方法是把函数名用一对反引用括起来（如 `funName` ）。 例如：

Prelude> div 5 2       -- 函数调用形式
2
Prelude> 5 `div` 2     -- 操作符调用形式
2

相反地，任何操作符也可以转换为函数的调用形式。转换方法是把操作符用一对小括号括起来。 例如：

Prelude> 3 + 4         -- 操作符调用形式
7
Prelude> (+) 3 4       -- 函数调用形式
7

在 Haskell 中， (+) 3 4 还可以写为 (3+) 4 或者 (+4) 3 的形式。它们的前部分，即 (3+) 和 (+4) 都被称为 section。

一般地，如果 # 是操作符，下面三个形式被称为 operator section：

(#)          -- 等同于 \x -> (\y -> x # y)
(x #)        -- 这称为left section，等同于 \y -> x # y
(# y)        -- 这称为right section，等同于 \x -> x # y

下面是 section 的一些例子：

可以使用逻辑表达式（被称为 Guards）对生成的结果进行过滤。比如：List comrehension [x | x <- [1..10], even x] 得到的结果为 [2,4,6,8,10] 。

字符串其实就是字符列表。比如 "abc" 和 ['a','b','c'] 是一回事。前面介绍的 List comprehensions 也适应于字符串。比如：

Prelude> [x | x <- "abc123XYZd", x >= 'a' && x <= 'z']      -- 用Guards过滤了非小写字母
"abcd"

下面是利用 String comprehensions 定义函数的两个例子：

lowers :: String -> Int
lowers xs = length [x | x <- xs, x >= 'a' && x <= 'z']     -- 返回字符串中小写字母的数量

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']               -- 返回字符串中包含指定字符的数量

内置函数 map 是一个常用的高阶函数。它的第一个参数是另一个函数，第二个参数是一个列表，返回的结果是对列表（第二个参数指定）中每个元素应用函数（第一个参数指定）后组成的新列表。

下面是 map 的一个实现：

map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]

下面是 map 的一个使用实例：

Prelude> map (+1) [1,3,5,7]
[2,4,6,8]
Prelude> map even [1,2,3,4]
[False,True,False,True]
Prelude> map reverse ["abc","def","ghi"]
["cba","fed","ihg"]

下面是函数 map 的另外一个实现（利用递归调用）：

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

表 7 是一些内置的列表处理高阶函数。

先观察几个函数的定义：

sum [] = 0
sum (x:xs) = x + sum xs

or [] = False
or (x:xs) = x || or xs

and [] = True
and (x:xs) = x && and xs

下面是 sum [1, 2, 3, 4] 的计算过程：

sum [1, 2, 3, 4]
= sum 1 + (2 + (3 + (4 + 0)))
= sum 1 + (2 + (3 + 4))
= sum 1 + (2 + 7)
= sum 1 + 9
= 10

前面这些函数都有共同的处理模式，可以抽象为下面的形式：

f [] = 0
f (x:xs) = x # f xs

内置的高阶函数 foldr （是“fold right”的缩写）封装了上面的模式。使用 foldr 可以更方便地定义 sum/or/and 等函数。如：

sum :: Num a => [a] -> a
sum = foldr (+) 0

or :: [Bool] -> Bool
or = foldr (||) False

and :: [Bool] -> Bool
and = foldr (&&) True

下面是函数 foldr 的一个实现：

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

如 foldr (+) 0 [1,2,3] 可以得到 1 + (2 + (3 + 0)) 。下面总结了 foldr 的行为：

foldr (#) v [x0, x1, ..., xn] = x0 # (x1 # (... (xn # v) ...))

高阶函数 foldl 和 foldr 类似，不过它是左结合性的。下面是 foldl 的行为：

foldl (#) v [x0,x1,...,xn] = (... ((v # x0) # x1) ...) # xn

下面是函数 foldl 的一个实现：

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

sum/or/and 等函数除了用 foldr 定义外，还可以使用 foldl 定义。如：

sum :: Num a => [a] -> a
sum = foldl (+) 0

or :: [Bool] -> Bool
or = foldl (||) False

and :: [Bool] -> Bool
and = foldl (&&) True

采用上面定义时， sum [1, 2, 3, 4] 的计算过程如下：

sum [1, 2, 3, 4]
= sum ((((0 + 1) + 2) + 3) + 4)
= sum (((1 + 2) + 3) + 4)
= sum ((3 + 3) + 4)
= sum (6+ 4)
= 10

操作符 $ 被称为“function application operator”，它的定义如下：

($) :: (a -> b) -> a -> b
f $ x = f x

从定义上看，操作符 $ 仅仅是应用一个函数。那它有什么用呢？

由于操作符 $ 具有最低优先级，我们往往使用操作符 $ 来去掉代码中的一些括号。 比如： sqrt (3 + 4 + 9) 可以写为 sqrt $ 3 + 4 + 9 ，又如 sum (map sqrt [1..130]) 可以写为 sum $ map sqrt [1..130] 。

此外，操作符 $ 具有右结合性，也就是说 f $ g $ x 和 f $ (g $ x) 相等。所以下面三行代码是相同的：

sum (filter (> 10) (map (*2) [2..10]))
sum $ filter (> 10) (map (*2) [2..10])      -- 利用 $ 去掉了一对括号
sum $ filter (> 10) $ map (*2) [2..10]      -- 利用 $ 去掉了两对括号

内置高阶操作符 . 的左/右操作数都是函数，其返回的结果也是函数。下面是它的一个实现：

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

把 f . g 读作“f composed with g”，它是接收一个参数的函数。首先把 g 应用它的参数，然后把 f 应用于上一步的结果。也就是说，它还可以定义为 (f . g) x = f (g x) 。 不过，之前的定义 f . g = \x -> f (g x) 更易理解，因为它明确地表示了 f . g 的结果是一个函数。

操作符 . 具备结合性，即有： f . (g . h) = (f . g) . h

利用 . 可以简化一些函数的定义。如：

odd n = not (even n)
twice f x = f (f x)
sumsqreven ns = sum (map (^2) (filter even ns))

利用 . 可以把上面的定义简化为：

odd = not . even
twice f = f . f
sumsqreven = sum . map (^2) . filter even

定义 type 最简单的办法是基于已有的 type。比如：

type String = [Char]               -- type名（String）必须以大写字母开头

又如：

type Pos = (Int,Int)
type Trans = Pos -> Pos

A type is a collection of related values. 可以使用 data 为 type 指定相关的值。如：

data Bool = False | True           -- type的值（False或True）也必须以大写字母开头

使用 newtype 可以定义全新的 type。如定义一个非负数：

newtype Nat = N Int

当然，我们可以这样定义非负数 Nat ：

type Nat = Int
data Nat = N Int

不过，“采用 newtype 定义非负数 Nat ”比“采用 type 基于已有 type 定义非负数 Nat ”要更加安全。因为，如果采用 newtype 定义非负数 Nat ，则当程序期待非负数 Nat 时，你不能传递一个 Int 。

节 2.9 介绍了一些基本的 class，这节介绍如何定义新的 class。

一个新的 class 可以使用 class 来定义。如内置 class Eq 可以这样定义：

class Eq a  where
    (==), (/=)       :: a -> a -> Bool   -- 这里说明 class Eq 必须定义两个方法： == 和 /=
    x /= y           =  not (x == y)     -- 这里是 default definition，这样Eq的实例只需要定义 == ，而无需定义 /= 了

使用 instance 可以定义 class 的实例。如 type Bool 可以这样定义：

instance Eq Bool where
    False == False = True
    True  == True  = True
    _     == _     = False

参考：https://www.haskell.org/tutorial/classes.html

下面三个要求称为 Monoid Laws：
(1) mempty `mappend` x = x
(2) x `mappend` mempty = x
(3) (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z) ，即 mappend 遵守结合律。

注 1：Haskell 不会强制检查这些定律是否被遵守。我们在定义 Monoid 的实例时必须自己遵守它们。
注 2：Monoid 来源于抽象代数中的 幺半群(Monoid) 。

List 是 Monoid 的实例，其代码如下：

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

下面是一些基本测试：

Prelude> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
Prelude> mconcat [[1,2],[3,6],[9]]
[1,2,3,6,9]
Prelude> mempty :: [a]
[]

下表是 Haskell 中内置操作符的优先级和结合性。

+--------+----------------------+-----------------------+-------------------+
| Prec-  |   Left associative   |    Non-associative    | Right associative |
| edence |      operators       |       operators       |    operators      |
+--------+----------------------+-----------------------+-------------------+
| 9      | !!                   |                       | .                 |
+--------+----------------------+-----------------------+-------------------+
| 8      |                      |                       | ^, ^^, **         |
+--------+----------------------+-----------------------+-------------------+
| 7      | *, /, `div`,         |                       |                   |
|        | `mod`, `rem`, `quot` |                       |                   |
+--------+----------------------+-----------------------+-------------------+
| 6      | +, -                 |                       |                   |
+--------+----------------------+-----------------------+-------------------+
| 5      |                      |                       | :, ++             |
+--------+----------------------+-----------------------+-------------------+
| 4      |                      | ==, /=, <, <=, >, >=, |                   |
|        |                      | `elem`, `notElem`     |                   |
+--------+----------------------+-----------------------+-------------------+
| 3      |                      |                       | &&                |
+--------+----------------------+-----------------------+-------------------+
| 2      |                      |                       | ||                |
+--------+----------------------+-----------------------+-------------------+
| 1      | >>, >>=              |                       |                   |
+--------+----------------------+-----------------------+-------------------+
| 0      |                      |                       | $, $!, `seq`      |
+--------+----------------------+-----------------------+-------------------+

参考：https://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-820004.4.2