Haskell(一)入门
Haskell(二)函数式编程
Haskell(三) Monad
Haskell(四)总结和工具链
Haskell(五) 总结和展望
Haskell(六) Project Euler 练习1-26

前言

这个系列主要介绍典型的函数式程序设计语言（Functional programming languages，FP）和逻辑式程序设计语言（Logic programming languages，LP），将会分别以 Haskell 和 datalog（主要是 souffle）作为例子，简单的入门和理解。

理解典型的 FP 对于深入学习程序设计语言挺好处的。我们先从 haskell 开始

参考资料：

haskell 官网
Haskell 趣学指南，英文原版也很不错。
快速查阅库文档
最推荐的查阅手册，能够直接点击 Quick Jump 搜索关键词，这也是我最常用的文档
官方 WiKi如果有不懂的术语，那么很推荐先在 wiki 上查找。
可以参考的入门课程
资源汇总
交流学习群、交流学习群 2
在线交互解释器，适合不配置环境就开始学习。
视频教程和对应练习答案

Haskell 的设计思路和普通命令式语言不同，读者将会遇到思维上的转变，从类 C 语言的变量、指针、内存、控制流的基本思想，到递归、表达式、变量替换和绑定的基本思想。我粗浅的理解里，印象最深的是无处不在的递归思维，递归贯穿了整个设计理念。并且放弃变量控制状态+控制流的传统命令式语言方式，彻底的用函数表现所有流程。

为了与 lambda 演算匹配，Functor 的思想也贯穿着整个表达式替换的过程，函数柯里化的过程让表达式嵌套变得更加自然，这些语法糖的支持，使得 Haskell 能够完成一般的任务。

然而，表达式嵌套的过程，各种新奇的语法糖，增大了从 C 系语言迁移到函数式语言的难度，而且函子(functor)的引入使得初学者难以把握抽象表达式的嵌套。学习新的语言设计范式可能理论价值高于实际价值。

我从这些天的学习中，提升的能力大致是：

初步从编程的角度理解 lambda 演算，有利于后续可能的深入学习。
自然而然地养成了递归思想，写程序往往会优先考虑递归。对于有规律地过程，递归和模式匹配的表现力很强。但是对于描述流程来说，可能 C 系语言更加自然。
这是程序设计语言的三大范式之一，有利于深入学习程序设计语言和程序分析方向。

安装和下载

Haskell 式函数式编程语言，安装教程详情见官网。除了官网推荐的安装方式，还可以使用包管理工具，尽量避免自行下载安装。

之后建议使用 VScode 编辑，如果已经完全安装了 Haskell 后，直接下载插件，即可有代码智能提示。其他 IDE 可见 wiki。

haskell 简介

官网就写的很好

Statically typed——强静态类型

Every expression in Haskell has a type which is determined at compile time. All the types composed together by function application have to match up. If they don’t, the program will be rejected by the compiler. Types become not only a form of guarantee, but a language for expressing the construction of programs.

也就是说静态的强类型系统。
Purely functional——纯函数式

Every function in Haskell is a function in the mathematical sense (i.e., “pure”). Even side-effecting IO operations are but a description of what to do, produced by pure code. There are no statements or instructions, only expressions which cannot mutate variables (local or global) nor access state like time or random numbers.

函数不存在“状态”，只有“如何处理”的逻辑，基础是λ 演算
Type inference——一定的类型推断

You don’t have to explicitly write out every type in a Haskell program. Types will be inferred by unifying every type bidirectionally. However, you can write out types if you choose, or ask the compiler to write them for you for handy documentation.
Concurrent

Haskell lends itself well to concurrent programming due to its explicit handling of effects. Its flagship compiler, GHC, comes with a high-performance parallel garbage collector and light-weight concurrency library containing a number of useful concurrency primitives and abstractions.

运算符

主要来自 Real World Haskell 中文版，也是写的不错的书。

ghci 程序是 GHC 的交互式解析器。它可以让用户输入 Haskell 表达式并对其求值，浏览模块以及调试代码。如果你熟悉 Python 或是 Ruby，那么 ghci 一定程度上和 python，irb 很像，这两者分别是 Python 和 Ruby 的交互式解析器。

+ - * / 都是常见的二元运算符，基本和其他语言一致。- 作为负号时，这个一元运算符需要添加括号。注意 / jie’gu

Prelude> 2+-3

<interactive>:2:2: error:
    • Variable not in scope: (+-) :: t0 -> t1 -> t
    • Perhaps you meant one of these:
        ‘+’ (imported from Prelude), ‘-’ (imported from Prelude),
        ‘++’ (imported from Prelude)
Prelude> 2+(-3)
-1

总而言之，符号在 Haskell 中非常重要。

Haskell 中表示布尔逻辑的值有这么两个：True和False。名字中的大写很重要。作用于布尔值得操作符类似于 C 语言的情况：(&&)表示“逻辑与”，(||)表示“逻辑或”。需要注意，0 /= False，这是强类型的语言，非 0 值也不是 True
!= 在这里的写法不同，而是/=
++ 表示为列表连接。Prelude> [1,2,3]++[4,5,6] 结果是 [1,2,3,4,5,6]
: 是二元操作符，用于增加一个元素到列表的头部，第一个操数是元素，第二个操作数是列表，Prelude> 0:[1,2,3]++[4,5,6] 结果是 [0,1,2,3,4,5,6]

更多的，建议读者多阅读文档，官方的文档永远是最好的参考手册。

数据类型

在 Haskell 里，所有类型名字都以大写字母开头，而所有变量名字都以小写字母开头。它不会自动地将值从一个类型转换到另一个类型（转换有时又称为强制或变换）

列表：[1,2,3]，和 python 类似，但是列表的元素类型需要一致。

列表可以使用枚举符号，也就是说 [1,2..6] 会自动补全为[1,2,3,4,5,6]。[1,4..15] 补全为[1,4,7,10,13]

新建列表也可以写成集合的形式，例如

字符和字符串和 C 语言类似。 'a' 是字符， "a" 是字符串。字符串也是列表，可以当作字符的列表，是等价的。

ghci> let a = ['l', 'o', 't', 's', ' ', 'o', 'f', ' ', 'w', 'o', 'r', 'k']
ghci> a
"lots of work"
ghci> a == "lots of work"
True

所以可以得到类似的结论

Prelude> "123"++"abc"
"123abc"
Prelude> 'x':"123"++"abc"
"x123abc"

元组的长度是固定的，但可以包含不同类型的值。

1 2	Prelude> (1964, "Labyrinths") (1964,"Labyrinths")

元组是有顺序的，比较的时候是对应元素比较

Prelude> :type (False, 'a')
(False, 'a') :: (Bool, Char)
Prelude> :type ('a',False)
('a',False) :: (Char, Bool)
Prelude> (False, 'a') == (False, 'a')
True
Prelude> (False, 'a') == ('a',False)

<interactive>:10:18: error:
• Couldn't match expected type ‘Bool’ with actual type ‘Char’
• In the expression: 'a'
In the second argument of ‘(==)’, namely ‘('a', False)’
In the expression: (False, 'a') == ('a', False)

<interactive>:10:22: error:
• Couldn't match expected type ‘Char’ with actual type ‘Bool’
• In the expression: False
In the second argument of ‘(==)’, namely ‘('a', False)’
In the expression: (False, 'a') == ('a', False)

分数表示比较特殊，1/2 表示为 1%2，它实际上是比较精确的比例，:m +Data.Ratio 表示引入 Data.Ratio module。相应的，也可以撤销引入的模块 :m -Data.Ratio
1
2
3
4
Prelude> :m +Data.Ratio
Prelude Data.Ratio> 11%29
11 % 29
it :: Integral a => Ratio a
Char：单个 Unicode 字符。
Bool表示一个布尔逻辑值。这个类型只有两个值： True 和 False 。
Int 带符号的定长（fixed-width）整数。这个值的准确范围由机器决定：在 32 位机器里， Int 为 32 位宽，在 64 位机器里， Int 为 64 位宽。Haskell 保证 Int 的宽度不少于 28 位。（数值类型还可以是 8 位、16 位，等等，也可以是带符号和无符号的，以后会介绍。）
Integer 不限长度的带符号整数。 Integer 并不像 Int 那么常用，因为它们需要更多的内存和更大的计算量。另一方面，对 Integer 的计算不会造成溢出，因此使用 Integer 的计算结果更可靠。
Double 用于表示浮点数。长度由机器决定，通常是 64 位。（Haskell 也有 Float 类型，但是并不推荐使用，因为编译器都是针对 Double 来进行优化的，而 Float 类型值的计算要慢得多。）

还有一类是容器类型，最常见的容器类型是列表（List），它可以包含任何类型的元素，例如[Int]表示整数列表，[Char]表示字符列表（也就是 String）。Haskell 中的其他常见容器类型包括：

Maybe：一个可能包含元素也可能为空的容器。Maybe Int可以包含一个Int或者什么都不包含。
Either：一个可以包含两种类型之一的元素的容器。Either String Int可以包含一个String或一个Int。
Set：一个包含不重复元素的容器。
Map：一个键值对的容器，你可以根据键找到对应的值。
Tree：一个树形结构的容器，每个节点都可以包含一个值。

ghci 也可以设置命令行的参数，可以执行 :set +t 让打印变量时也打印类型

Prelude> :set +t
Prelude> 'c'
'c'
it :: Char

Prelude> [1,2,3]
[1,2,3]
it :: Num a => [a]

Prelude> "abc"
"abc"
it :: [Char]

Prelude> 1
1
it :: Num p => p

Prelude> 0.5
0.5
it :: Fractional p => p

Prelude> :m +Data.Ratio
Prelude Data.Ratio> 11%29
11 % 29
it :: Integral a => Ratio a

x :: y 表示表达式 x 的类型为 y
[Char] 表示由 char 类型的元素构成的数组。
=> 左边表示·变量的类型约束，比如 Num 是类型类，它约束了 p 必须是 Num 类型的变量。右边是表示函数类型。我们看一个复杂的例子

1 2	squareSum :: Num a => a -> a -> a squareSum x y = (x + y) * (x + y)

这里 => 规定 a 是 Num 类型的变量，函数类型是 a -> a -> a。其中函数类型是由 -> 构成的，它表示可以接受一个参数，然后返回一个函数。当接受到 2 个参数后，它就会返回 a。-> 的作用就是将参数和函数返回类型链接在一起。

另外的命令行参数 :type 可以直接地看到变量的类型。

1 2	Prelude Data.Ratio> :type 1 1 :: Num p => p

显式指定类型

:: 可以显式指定类型，叫做类型签名。'a' :: Char

变量

如果你曾经用过命令式语言（如 C、C++、Java 等），就会发现 Haskell 的变量和命令式语言的变量很不同：在命令式语言里，一个变量通常用于标识一个内存位置（或者其他类似的东西），并且在任何时候，都可以随意修改这个变量的值。因此在不同时间点上，访问这个变量得出的值可能是完全不同的。

在 Haskell 里，可以使用变量来赋予表达式名字：一旦变量绑定了（也即是，关联起）某个表达式，那么这个变量的值就不会改变。文件 assign.hs 内容是

1
2

x=1
x=2

结果如下

(base) ➜  vim assign.hs
(base) ➜  ghci
Prelude> :load assign.hs
[1 of 1] Compiling Main             ( assign.hs, interpreted )

assign.hs:2:1: error:
    Multiple declarations of ‘x’
    Declared at: assign.hs:1:1
                 assign.hs:2:1
  |
2 | x=2
  | ^
Failed, no modules loaded.

函数调用

基本格式是函数名和参数，如下：

Prelude> odd 3
True

Prelude> odd 6
False

Prelude> compare 2 3
LT

Prelude> compare 3 3
EQ

Prelude> compare 3 2
GT

函数的优先级比操作符要高

函数也具有类型，表示输入到输出的映射

Prelude> add a b = a+b
Prelude> add 2 3
5
Prelude> :type add
add :: Num a => a -> a -> a

这里很多的箭头表示，一个数 a 映射到 a -> (a -> a) 函数，也就是返回了 a -> (a -> a) 函数，接着根据 a 的值返回 a -> a 函数，直到最后返回一个数。

函数定义

add a b = a + b 中， add 是函数名，后面是参数，= 之后是函数体。可以加载定义好的函数，也就是加载模块。

add.hs 里是上述代码，然后

(base) ➜  vim add.hs
(base) ➜  ghci
Prelude> :load add.hs
[1 of 1] Compiling Main             ( add.hs, interpreted )
Ok, one module loaded.
*Main> add 4.1 5
9.1

在 Haskell 里，代码的缩进非常重要：它会延续（continue）一个已存在的定义，而不是新创建一个。所以，不要省略缩进！

Haskell 也是使用缩进来表示一个表达式或者块延伸的范围的，这点与 Python 类似。Haskell 的缩进规则简单总结起来只用下面三条：

源文件中第一个顶级的定义或者声明的缩进，定义了该文件中所有顶级定义或者声明的缩进；
空白行（只有注释的行也认为是空白行）和比前面某一行更加向右的缩进都表示对前面那一行所在块或者表达式的继续；
由 let 和 where 开始的一个块，在 let 或者 where 关键字后第一个定义或者声明的缩进，定义了该块中所有定义或者声明应该具有的缩进。

定义函数如下：

myDrop n xs = if n<= 0 || null xs
    then xs
    else myDrop (n-1) (tail xs)
-- null 判断是否是空值，这里是列表是否为空
-- 这里是递归的形式，实际上还是很清楚的

上述代码也支持写成一行：

1	myDropX n xs = if n <= 0 \|\| null xs then xs else myDropX (n - 1) (tail xs)

操作列表的函数

head 函数取出列表的第一个元素：

Prelude> head [1, 2, 3, 4]
1

Prelude> head ['a', 'b', 'c']
'a'

tail 取出列表里除了第一个元素之外的其他元素：

Prelude> tail [1, 2, 3, 4]
[2,3,4]

Prelude> tail [2, 3, 4]
[3,4]

Prelude> tail [True, False]
[False]

take 返回一个包含 l 前 n 个元素的列表：

1 2	Prelude> take 2 [1, 2, 3, 4, 5] [1,2]

drop 则返回一个包含 l 丢弃了前 n 个元素之后，剩余元素的列表：

1 2	Prelude> drop 2 [1, 2, 3, 4, 5] [3,4,5]

操作元组的函数

函数 fst 和 snd 接受一个元组作为参数，返回该元组的第一个元素和第二个元素：

Prelude> fst (1, 'a')
1

Prelude> snd (1, 'a')
'a'

惰性求值

1 2	-- file: ch02/isOdd.hs isOdd n = mod n 2 == 1

这是 Haskell 很重要的特性。先说一般的编程语言（命令式编程语言），他们采用严格求值的方法，也就是：函数的参数总是在应用函数之前被求值。以 isOdd 为例子：子表达式 (1 + 2) 会首先被求值，得出结果 3 。接着，将 3 绑定到变量 n ，应用到函数 isOdd 。最后， mod 3 2 返回 1 ，而 1 == 1 返回 True 。

但是 Haskell 采用非严格求值，求值 isOdd (1 + 2) 并不会即刻使得子表达式 1 + 2 被求值为 3 ，相反，编译器做出了一个“承诺”，说，“当真正有需要的时候，我有办法计算出 isOdd (1 + 2) 的值”。

面向表达式编程

记住，Haskell 是一门以表达式为主导（expression-oriented）的语言，所有分支都是表达式，所有逻辑都是表达式嵌套表达式。在命令式语言中，代码由陈述（statement）而不是表达式组成，因此在省略 if 语句的 else 分支的情况下，程序仍是有意义的。但是，当代码由表达式组成时，一个缺少 else 分支的 if 语句，在条件部分为 False 时，是没有办法给出一个结果的，当然这个 else 分支也不会有任何类型，因此，省略 else 分支对于 Haskell 是无意义的，编译器也不会允许这么做。

1	myDropX n xs = if n <= 0 \|\| null xs then xs else myDropX (n - 1) (tail xs)

当执行表达式 myDrop 2 "abcd" 时，函数 myDrop 应用于值 2 和 "abcd" ，变量 n 被绑定为 2 ，而变量 xs 被绑定为 "abcd" 。将这两个变量代换到 myDrop 的条件判断部分，就得出了以下表达式：

1 2	*Main> :type 2 <= 0 \|\| null "abcd" 2 <= 0 \|\| null "abcd" :: Bool

编译器需要对表达式 2 <= 0 || null "abcd" 进行求值，从而决定 if 该执行哪一个分支。这需要对 (||) 表达式进行求值，而要求值这个表达式，又需要对它的左操作符进行求值：

1 2	*Main> 2 <= 0 False

将值 False 代换到 (||) 表达式当中，得出以下表达式：

1 2	*Main> :type False \|\| null "abcd" False \|\| null "abcd" :: Bool

如果 (||) 左操作符的值为 True ，那么 (||) 就不需要对右操作符进行求值，因为整个 (||) 表达式的值已经由左操作符决定了。[译注：在逻辑或计算中，只要有一个变量的值为真，那么结果就为真。]另一方面，因为这里左操作符的值为 False ，那么 (||) 表达式的值由右操作符的值来决定：

1 2	*Main> null "abcd" False

最后，将左右两个操作对象的值分别替换回 (||) 表达式，得出以下表达式：

1 2	*Main> False \|\| False False

这个结果表明，下一步要求值的应该是 if 表达式的 else 分支，而这个分支包含一个对 myDrop 函数自身的递归调用： myDrop (2 - 1) (tail "abcd") 。

自定义类型

基本语法结构

以一个在线书店为例子，展示如何去进行类型定义。

使用 data 关键字可以定义新的数据类型：

-- file: BookStore.hs
data BookInfo = Book Int String [String] deriving(Show)
myInfo = Book 9780135072455 "Algebra of Programming"
              ["Richard Bird", "Oege de Moor"]

跟在 data 关键字之后的 BookInfo 就是新类型的名字，我们称 BookInfo 为类型构造器。类型构造器用于指代（refer）类型。正如前面提到过的，类型名字的首字母必须大写，因此，类型构造器的首字母也必须大写。

接下来的 Book 是值构造器（有时候也称为数据构造器）的名字，也就是声明变量时用的名字。类型的值就是由值构造器创建的。值构造器名字的首字母也必须大写。

在 Haskell 里，类型的名字（类型构造器）和值构造器的名字是相互独立的。类型构造器只能出现在类型的定义，或者类型签名当中。而值构造器只能出现在实际的代码中。值构造器既可以是一般意义上的值，也可以是函数。

在 Book 之后的 Int ， String 和 [String] 是类型的组成部分。组成部分的作用，和面向对象语言的类中的域作用一致：它是一个储存值的槽。（为了方便起见，我们通常也将组成部分称为域。）

在这个例子中， Int 表示一本书的 ID ，而 String 表示书名，而 [String] 则代表作者。deriving (Show) 表示继承了 Show 的属性，可以被打印出来。

Prelude> :load BookStore.hs
[1 of 1] Compiling Main             ( BookStore.hs, interpreted )
Ok, one module loaded.
*Main> myInfo
Book 9780135072455 "Algebra of Programming" ["Richard Bird","Oege de Moor"]

*Main> a = Book 0 "The Book of Imaginary Beings" ["Jorge Luis Borges"]
*Main> a
Book 0 "The Book of Imaginary Beings" ["Jorge Luis Borges"]

可以获取相关信息：

*Main> :info BookInfo
type BookInfo :: *
data BookInfo = Book Int String [String]
        -- Defined at BookStore.hs:1:1
instance [safe] Show BookInfo -- Defined at BookStore.hs:1:51

*Main> :t Book
Book :: Int -> String -> [String] -> BookInfo

在函数中的用法也比较类似，需要声明值选择器

*Main> data Coord = Coord Int Int deriving (Show)

*Main> x = Coord 3 4

*Main> x
Coord 3 4

*Main> add (Coord x y) = x+y
*Main> add x
7

多个自定义类型的用法也是类似的，理解表达式绑定到变量对应的位置即可。

*Main> add (Coord x y) (Coord a b) = x+y+a+b
*Main> x = Coord 1 2
*Main> y = Coord 10 20
*Main> add x y
33

类型别名

和 C 语言非常类似，type 关键字用于设置类型别名，其中新的类型名字放在 = 号的左边，而已有的类型名字放在 = 号的右边。这两个名字都标识同一个类型，因此，类型别名完全是为了提高可读性而存在的。

type CustomerID = Int
type ReviewBody = String

data BetterReview = BetterReview BookInfo CustomerID ReviewBody

多个值构造器

当一个类型拥有一个以上的值构造器时，这些值构造器通常被称为“备选”（alternatives）或“分支”（case）。同一类型的所有备选，创建出的的值的类型都是相同的。这相当于实现了「枚举类型」或者反映了「多态性」，但是又比较特殊，因为每个分支都是一个表达式，既是类型也可以是函数其实函数和值都是表达式。值构造器相当于构造函数。

枚举类型

代数数据类型的各个值构造器都可以接受任意个数的参数。[译注：不同备选之间接受的参数个数不必相同，参数的类型也可以不一样。]以下是一个账单数据的例子：

-- file: BookStore.hs
type CardHolder = String
type CardNumber = String
type Address = [String]
data BillingInfo = CreditCard CardNumber CardHolder Address
                 | CashOnDelivery
                 | Invoice CustomerID
                   deriving (Show)

这个程序提供了三种付款的方式。如果使用信用卡付款，就要使用 CreditCard 作为值构造器，并输入信用卡卡号、信用卡持有人和地址作为参数。如果即时支付现金，就不用接受任何参数。最后，可以通过货到付款的方式来收款，在这种情况下，只需要填写客户的 ID 就可以了。

也就是说，先设置了类型别名，类似于 C 语言的 typedef，让类型的可读性更好。然后 BillingInfo 类型有三个枚举类型，通过模式匹配确定选择哪两个。

Just 和 Maybe

对于自定义的类型，往往会出现无意义的情况或者不需要返回值的情况，或者是错误处理的情况，这相当于其他语言里的 null 和 nil。所以，就出现了内置的 Nothing 类型。

data BillingInfo = CreditCard CardNumber CardHolder Address
                 | CashOnDelivery
                 | Invoice CustomerID
                 | Nothing
                   deriving (Show)

更进一步，为了处理存在 Nothing 的模式匹配，加入了新的关键字 Maybe 和 Just。Maybe 表示变量可以表示空值。比如上面的代码，可以定义一个 Maybe 变量。Just 必须和 Maybe 配合使用，当不为空值是必须要有 Just，没有 Just 的 Maybe 变量就只能赋值 billingInfo=Nothing。

1 2	billingInfo :: Maybe BillingInfo billingInfo = Just (CreditCard "1234" "John" "123 main St.")

具体来说，如果是使用了 Maybe ，表示可以匹配值构造器或者 Nothing，在错误处理中很有用。

多态性

Haskell 是强类型的语言，所以参数的类型都是有明确的规定的，也存在对应其他语言中「泛型」或者「模板」的语法。这也是通过枚举类型实现的。

比如我们需要打印 JSON 的某个值，但是 JSON 类型有 String、Number、Boolean、Object (JSON object)、Array、null，难道每种类型都要写非常类似的函数吗？我们可以通过多态简化。

-- 多态
data JValue
  = JString String
  | JNumber Double
  | JBool Bool
  | JNull
  | JObject [(String, JValue)]
  | JArray [JValue]
  deriving (Eq, Ord, Show)

-- 类型名字
getValue (JValue) |

getString :: JValue -> Maybe String
getString (JString s) = Just s
getString _ = Nothing

getInt (JNumber n) = Just (truncate n)
getInt _ = Nothing

getDouble (JNumber n) = Just n
getDouble _ = Nothing

getBool (JBool b) = Just b
getBool _ = Nothing

getObject (JObject o) = Just o
getObject _ = Nothing

getArray (JArray a) = Just a
getArray _ = Nothing

isNull v = v == JNull

递归类型

列表举例

上一小节提到了多个值构造器形成多态的特性，我们可以利用这一点实现非常简洁的递归类型。**本质上，列表就是递归类型。**后面将会提到，列表 [1, 2] 实际上只是 (1:(2:[])) 的一种简单的表示方式。具体的表达式如下：

1
2
3

data List a = Cons a (List a)
            | Nil
              deriving (Show)

具体使用方法如下，Cons 需要两个参数，第一个参数可以是任何可以的类型，第二个参数必须是我们定义的 List 类型。怎么判断是否是 List 类型呢，这需要观察变量的表达式。例如 Nil 就是一个 List a 类型。当匹配不到 Cons 值构造器的时候，就会选择 Nil

注意 it 是特殊的变量，表示交互式解释器里，输出的上一个变量。

初始的 List 变量是 Nil，然后添加 1
Prelude> Cons 1 Nil
Cons 1 Nil

Prelude> it
Cons 1 Nil

Prelude> Cons 2 it
Cons 2 (Cons 1 Nil)

Prelude> Cons 2 it
Cons 2 (Cons 2 (Cons 1 Nil))

如果我们把 Cons 替换成 : 实际上就和列表在结构上相同了。

二叉树举例

1
2
3

data Tree a = Node a (Tree a) (Tree a)
            | Empty
              deriving (Show)

当匹配到是 Node 的值就选择 Node，否则选择 Empty。如果熟悉二叉树的话，这是很容易理解的。

和其他语言类比

以下是一个 C 结构，它等同于我们前面定义的 BookInfo 类型：

struct book_info {
    int id;
    char *name;
    char *authors;
};

目前来说， C 结构和 Haskell 的代数数据类型最大的差别是，Haskell 代数数据类型的成分是匿名且按位置排序的，也就是说位置才决定了绑定的那个类型，而不是通过名字。

1 2	data BookInfo = Book Int String [String] deriving (Show)

C 和 C++ 里的 enum 通常用于表示一系列符号值排列。代数数据类型里面也有相似的东西，一般称之为枚举类型。

以下是一个 enum 例子：

enum roygbiv {
    red,
    orange,
    yellow,
    green,
    blue,
    indigo,
    violet,
};

以下是等价的 Haskell 代码：

-- file: Roygbiv.hs
data Roygbiv = Red
             | Orange
             | Yellow
             | Green
             | Blue
             | Indigo
             | Violet
               deriving (Eq, Show)

在 ghci 里面测试：

Prelude> :load Roygbiv.hs
[1 of 1] Compiling Main             ( Roygbiv.hs, interpreted )
Ok, modules loaded: Main.

*Main> :type Yellow
Yellow :: Roygbiv

*Main> :type Red
Red :: Roygbiv

*Main> Red == Yellow
False

*Main> Green == Green
True

模式匹配

简单地说，记住表达式在 Haskell 中很重要，只要对应的输入有对应的输出，那么就是正确的，所以如下的函数也是正确的

1
2
3

-- file: myNot.hs
myNot True = False
myNot False = True

初看上去，代码似乎同时定义了两个 myNot 函数，但实际情况并不是这样 —— Haskell 允许将函数定义为一系列等式： myNot 的两个等式分别定义了函数对于输入参数在不同模式之下的行为。对于每行等式，模式定义放在函数名之后， = 符号之前。

首先调用 myNot ， Haskell 运行时检查输入参数 False 是否和第一个模式的值构造器匹配 —— 答案是不匹配，于是它继续尝试匹配第二个模式 —— 这次匹配成功了，于是第二个等式右边的值被作为结果返回。

再看一个例子，在 Haskell 里，列表 [1, 2] 实际上只是 (1:(2:[])) 的一种简单的表示方式，其中 (:) 用于构造列表。

1 2	sumList (x:xs) = x + sumList xs sumList [] = 0

通配符

比较特殊的是通配符，如果一些值无所谓，那么直接用 _ 代替即可，避免函数参数不匹配匹配。比如获取坐标中横坐标的值

*Main> x = Coord 1 2
*Main> xcoord (Coord x y)=x
*Main> xcoord x
1

也可以写成

*Main> xcoord (Coord x _)=x
*Main> x
Coord 1 2
*Main> xcoord x
1

形式匹配

在 Haskell 中，形式匹配通常使用 case 表达式、函数定义、let 语句、where 子句等方式来实现。在 Haskell 中，case 表达式可以用于将一个表达式与一组模式进行匹配，并执行相应的代码。case 表达式的基本形式如下：

case expression of
  pattern1 -> code1
  pattern2 -> code2
  ...
  patternN -> codeN

expression 是要匹配的表达式，``pattern1到patternN 是不同的模式，code1到codeN` 是对应的代码块。当匹配成功时，对应的代码块将被执行，并返回结果。如果所有的模式都无法匹配，则 case 表达式将返回一个错误或空值。

1	case e of { xs@(x:rest) -> if x==0 then rest else xs }

xs@(x:rest) 表示将 e 表达式的值绑定到 xs 变量，并将它分解为两部分：头部 x 和尾部 rest。在这个模式中，xs 是整个 e 表达式的值，x 是 e 表达式的第一个元素，rest 是 e 表达式的剩余部分。如果 e 的头部元素等于 0，则返回 e 的剩余部分rest。否则，返回整个 e 表达式的值 xs。

为了方便起见，也可以在定义的时候就指定新类型的元素的名字。请读者仔细观察语法。

*Main> data Coord = Coord {getx::Int,gety::Int} deriving (Show)

*Main> x = Coord 1 2
*Main> getx x
1

定义变量的时候也可以更加清楚一些

1
2
3

*Main> x = Coord {getx = 10,gety =20}
*Main> getx x
10