Programming in Haskell Second Edition. Graham Hutton, 2016
https://www.haskell.org/documentation/
纯靠个人归纳理解，可能有理解错误或理解未到位的地方
Haskell发展较快。有些内容，尤其是附加库如数据类型定义等可能会过时，学习时注意结合实际操作
- 1 Haskell简介以及使用方法
- 2 语法
- 3 进阶
- 4 Prelude
- 5 补充
仓库在 https://gitlab.haskell.org/ghc/ghc
目前最为常用的编译器是ghc，诞生于University of Glasgow。ArchLinux下通过以下命令安装
sudo pacman -S ghc生成可执行文件
ghc -dynamic -o main main.hs # Arch下默认配置需要使用动态链接可以添加
-fglasgow-exts使能扩展，否则仅兼容Haskell 98
ghci # ghc --interactive交互模式下使用命令
:q退出，命令:?获取帮助
在正式讲解之前，先看几个实例，对Haskell代码形成一个初步理解
-- main.hs
module Main where -- 定义Main模块
import System.Environment -- 引用模块
main :: IO () -- 显式函数类型声明。函数`main`为类型`IO ()`
sumMe :: Num a => [a] -> a -- 显式函数类型声明。箭头`->`表示sumMe是一个函数。该函数输入一个元素类型为`Num`的列表`[a]`作为参数，返回一个类型为`Num`的数字`a`
testList :: Num a => [a] -- 显式列表类型声明
-- 到以上为止的代码在这个程序里面可以省略，编译器会自动推断
sumMe [] = 0 -- 接受空列表时的特殊情况
sumMe (x:xs) = x + sumMe xs -- `(x:xs)`表示将输入的列表分为第1个元素`x`以及后续元素列表`xs`。Haskell中`:`运算符表示将一个元素连接到列表开头
testList = [2,1,3,8]
main = print(show(sumMe testList)) -- 最终输出结果14。通常情况下Haskell中函数参数可以不加括号，但是遇到多个函数嵌套调用的时候为区分所以要加括号-- main.hs
-- 只需5行代码的快排。省略了模块以及函数定义
qsortMe [] = []
qsortMe (x:xs) = qsortMe smallList ++ [x] ++ qsortMe bigList -- `++`运算符表示连接两个列表
where -- `where`关键字用于描述本地的符号定义
smallList = [a | a <- xs, a <= x] -- `|`运算符和数学语言相同，这种语句被称为List comprehension，是Haskell中强大的语法糖。在该上下文中，`<-`用于将右侧列表中的元素依次复制给左边的符号或表达式。`<=`为小于等于符
bigList = [b | b <- xs, b > x]
main = print(show(qsortMe [1782,2,109805,7336096,6509,143]))Haskell中函数是一等公民。函数名可以作为其他函数的参数输入，其优先级也要高于例如+ - * / ^ !! ++ /= == < > >= <=等运算符。这和目前大部分语言不同
Haskell中的函数只有一个返回值，且不同的返回值必须为同一类型（例如Bool类型的True和False）。所以如果想要返回多个变量，就需要使用元组()或列表[]
Haskell一大特性就是规避了side effects。广义上讲，Haskell认为一个函数只要对外界产生影响（例如在终端输出，或读写一个全局内存，或依赖于输入参数以外的数据产生返回结果，或更改了输入的参数），那它就有side effects。如果一个函数功能仅依赖于参数输入，且只产生返回结果，那么它就是pure的。Haskell隔离了一般的函数与外界打交道的功能
Haskell同样不会改变输入的参数。例如使用变量a作为函数f的输入，多次相同的调用只会得到相同的结果
Haskell中没有循环，所有需要循环迭代实现的算法需要使用函数嵌套以及递归实现
注：除示例以外可以先跳过
Haskell是大小写敏感语言，且代码对于每一行开头的空格敏感
Haskell中单行注释使用--格式如下
comment = 1.223 -- An ordinary comment多行注释使用{- -}格式如下
{-
-
- Nested comment
- that extends over multiple lines
-
-}Haskell和C较为类似，在大型工程中也是以模块module为基本单元，最终链接到一起的。Haskell源文件使用以下格式定义该文件所属模块，例如Main模块
module Main在module的下一层就是声明declaration，一般会定义常量，datatype，type class以及fixity information
declaration的下一层是表达式expressions。函数式编程中每个表达式都是一个变量value，且类型为静态static
Haskell中有6种符号名称。变量variables以及构造体constructors都是属于变量；type variables，type constructors以及type classes和类型系统有关；module names表示大型工程中一个模块的名称
Haskell要求所有变量名（包括variables以及type variables）都以小写字母或下划线_开头，而其他所有名称（包括模块名以及类型名等）以大写字母开头
Haskell中下划线_作为小写字母看待。但是以_开头的变量名有特殊含义，一般用于命名没有使用到的参数，不常用
Haskell拥有以下保留关键字，作用会在之后讲解
| 关键字 | 目录 |
|---|---|
case |
|
class |
|
data |
|
default |
|
deriving |
|
do |
|
else |
|
foreign |
|
if |
|
import |
|
in |
|
infix |
|
infixl |
|
infixr |
|
instance |
|
let |
|
module |
|
newtype |
|
of |
|
then |
|
type |
|
where |
|
_ |
此外还有以下保留运算符
注意其他运算符如
+ - * ^ ++ !! /= == >= <= > <等本质是函数，在库中定义，不属于语言本身的特性，所以不在以下列表出现
| 运算符 | 目录 |
|---|---|
.. |
2.3.2 |
: |
|
:: |
2.3.1 |
= |
2.4.1 |
\ |
2.4.6 |
| |
2.4.4 |
<- |
|
-> |
2.3.5 2.4.3 2.4.6 |
@ |
|
~ |
|
=> |
2.3.8 |
数字格式和C基本一致
a = 15 -- Decimal
b = 0o172 -- Octal
c = 0x312d1f -- Hexadecimal
d = -23.00 -- Float
e = 2.3e-6 -- Float字符以及字符串如下
a = 'c' -- Char
b = "Texas" -- String
c = '\ACK' -- ASCII
d = '\x37' -- ASCII
e = '\r' -- Escape
f = "Multiple \
\Lines" -- StringHaskell虽然可以算静态语言，但是它的类型系统支持自动的类型推导，可以不对数据类型进行显式的声明。这和一些传统的静态语言是不同的
类型系统很重要。建议先熟悉类型系统再进行后续的学习
Haskell中使用双冒号运算符::进行显式的类型指定
Haskell中的类型系统分为两层，分别对应保留关键字中的class以及type。上层的是class（也可以说是typeclass），它是一系列type的集合。而type是一系列相关的值的集合（划重点）
以
Int为例，在ghc中该type为64bit（8Byte）长度的整型数据，代表 $ -2^{63} $ 到 $ 2^{63} - 1 $ 的一系列二进制整数的集合。同时Int又属于Num，Integral，Eq，Ord，Show以及Read等基本class。class和type是多对多的关系
class是较为高层、抽象的，它一般会规定type支持的运算操作等，例如比较大小，加减运算等。而type是较为底层、具象的，它决定了最终的字面值集合，也会重载（overload）class定义的抽象操作，对这些操作进行具体的定义。class作用类似于模板
在Haskell中万物皆表达式（expressions），且程序中每一个表达式都拥有自己的类型type或class（class最终会被解析为具体的type）。包括字面量（例如Bool类型的字面量False，其本身就是一个表达式），函数定义等
每一个表达式的
type会在该表达式被解析之前就被确定，这个过程称为type inference。正是因为事先检查并确定了type，Haskell可以提前发现type的不对应错误。所以说Haskell程序是类型安全（type safe）的但是
Haskell的这种特性并不会解决例如Divide by zero这样的错误。这样的错误只有到表达式被解析时才会被发现
ghci中触发Divide by zero异常示例：
ghci> div (134 :: Int) (0 :: Int)
*** Exception: divide by zero
列表List和元组Tuple是Haskell中两种基本的复合数据类型，分别使用[]以及()表示，元素之间使用,隔开。函数同样可以使用它们作为参数输入或输出
List可以使用下标引用其中的元素（运算符!!，下标0起始，示例 [1,1,2,3,5,8] !! 4 返回5），其中所有数据类型必须一致，不同长度List算作相同类型。可以定义无限长度的List。且List本身不会包含自身的长度信息，这点和C中的数组较为类似，长度需要通过特殊设计的函数获得
可以使用..运算符表示连续序列
emptyList = []
intList1 = [35, 14, 27, 308]
intList2 = [15..18] -- [15, 16, 17, 18]
charList1 = ['U', 't', 'a', 'h'] -- charList1类型为[Char]
charList2 = "Utah" -- charList2类型为String，与[Char]等价
charList3 = ['W'..'Z'] -- ASCII ['W', 'X', 'Y', 'Z']
stringList = ["Alaska", "San Francisco", "Ohio", "New Jersey"]此外，List的常用运算符还有:，表示将一个元素连接到List开头
1 : [3, 2, 5] -- 该表达式返回[1, 3, 2, 5]在之后的内容中我们会遇到很多:的应用，例如用于函数的输入参数中，用于分隔List的开头1个元素以及后续元素组成的列表
myTail :: [a] -> [a]
myTail (x:xs) = xs -- 去除List的开头元素后返回，这里的括号不是表示元组，只是将`x:xs`括起来而已Tuple不能使用下标，其中数据类型可以不同，包含了不同类型数据、不同长度的Tuple算作不同类型。Tuple是有限长度的，且长度（这里称为arity）不能为1，例如(False)就是非法的。因为()圆括号兼具调整表达式解析次序的功能，如果一个元组的arity为1那么将会产生冲突
emptyTuple = ()
pairTuple = ("Helsinki", 97)
tripleTuple = (True, 19.584, [1, 5, 3])习惯上将
arity为2的称为Pair，arity为3的称为Triple，依次类推
Haskell定义了以下常用的基本数据type
| 名称 | 类型 | 字面值 |
|---|---|---|
Bool |
布尔 | True或False |
Char |
Unicode字符（兼容ASCII） | 使用''括起来的任意单字符 |
String |
Unicode字符串[Char] |
使用""括起来的任意字符串，包含空串 |
Int |
二进制整型 | -2^63到2^63-1的任意整数 |
Integer |
无限精度整形 | 任意整数（使用高精度算法） |
Float |
二进制单精度浮点 | IEEE754 |
Double |
二进制双精度浮点 | IEEE754 |
class会规定在type中被重载的操作，称为methods
class并不是最小的类型划分单位，最小的划分单位为type
涉及到某类class的函数声明通常需要使用class constraint以及重载类型（关键符号=>），见2.3.8
Haskell定义了以下常用的基本数据class
| 名称 | 类型 | 包含的运算操作（函数） | 包含的type |
|---|---|---|---|
Eq |
equality types，可以比较是否相等的类型 |
== /=，返回Bool |
Bool Char String Int Integer Float Double 以及 List Tuple |
Ord |
ordered types，属于Eq同时有顺序可以比较大小的类型 |
> < >= <= 返回 Bool， min max 返回对应最小最大元素 |
同上 |
Show |
showable types，可以转换为字符串显示的类型 |
show :: Show a => a -> String |
同上 |
Read |
readable types，可以从字符串转换来的类型 |
read :: Read a => String -> a |
同上 |
Num |
numberic types，数字 |
(+) (-) (*)算术运算，negate取负，abs绝对值，signum符号（正1，负-1） |
Int Integer Float Double |
Integral |
integral types，整型 |
div除法，mod模（余） |
Int Integer |
Fractional |
fractional types，非整型 |
(/)除法，recip倒数 |
Float Double |
一定注意
Integer（type）和Integral（class）的区分。单词Integer为名词，Integral为形容词
Ord的一个反例就是，我们定义一个名为Fruit的type，其中包含Apple Pear Peach几个字面值，我们认为这些字面值无法比较大小所以也就不能将Fruit归入Ord。但是Fruit可以归入Eq
Ord中，Bool类型规定True > False，True >= False为真。而字符大小遵循ASCII顺序可以使用
read "123" :: Float强制read转换为指定type（通常不需要，编译器会自动推断）要注意负数作为函数的参数输入时一定要加括号，如
abs (-13)。不加括号Haskell会将其解析为(-)减运算，会变成abs - 13
函数有两个数据要素，一个是输入参数，一个是返回
Haskell函数中输入参数和返回也可以是函数
函数的类型声明中一定会有->符号，符号前面放置输入的参数类型，后面放置返回的类型
-- myFunc1接受1个Int参数，返回Bool类型变量
myFunc1 :: Int -> Bool
-- myFunc2接受1个Float列表，返回Int列表
myFunc2 :: [Float] -> [Int]
-- myFunc3可以接受类似myFunc1的函数作为输入，返回Bool类型变量
myFunc3 :: (Int -> Bool) -> Bool所谓高阶函数就是拥有多个输入参数的函数。这些函数可以看成是逐个提取输入参数，并依次返回一个部分符号被替换后的函数。可以观察以下示例
triMult :: Int -> Int -> Int -> Int
triMult x y z = x*y*z等价于
triMult :: Int -> (Int -> (Int -> Int))
triMult x y z = x*y*z
Haskell中的所有函数事实上都可以看作Lambda表达式。Haskell会将语法树最终按照Lambda来处理以上的代码将
x y z三个变量相乘后返回。类型Int -> (Int -> (Int -> Int))可以这样理解：函数triMult接受一个Int类型的变量x=4(假设)后返回一个Int -> (Int -> Int)类型的函数，表达式为4*y*z；该函数接受y=5后再返回一个Int -> Int类型的函数，表达式为4*5*z，依次类推
可以理解为依次将已知的输入参数注入到函数表达式后将函数以及表达式本身返回。在Lambda表达式中，未被注入的符号我们称之为Free Variable
也是由于自由变量特性，我们在调用一个函数时可以不传入每一个参数。如此调用函数将会返回一个已知参数变量被替换的匿名函数，而不是函数最终的执行结果
上述代码示例中，
triMult x y z可以添加括号成为(((triMult x) y) z)（左相联）。如果我们调用triMult 13 2，那么我们将会得到一个匿名函数\z -> 13*2*z（为这个Lambda表达式起一个函数名func，func z = 13*2*z）
很多复合数据类型如List和Tuple的操作是通用的（例如计算它的长度length函数），但是我们无法精确的在类型声明中表述该List中元素的类型type。由此我们使用一个type variable来进行函数的类型声明，格式示例如下
-- 取一个List的头
head :: [a] -> a
-- 取Pair中第一个元素
fst :: (a, b) -> a
-- 计算长度
length :: Foldable t => t a -> Int这里的
a相当于一个我们给List中元素的type定义的变量，它可以是Int Integer String Float Bool等具体的type
和多态类型适用于所有class不同，我们在设计某类class适用的函数时，需要使用类型限制class constraints，将函数声明为重载类型overloaded types，典型的如(+)加法运算
-- 加法
(+) :: Num a => a -> a -> a加法需要将两个相同类型的数字
Num相加，返回一个同样类型的Num。这里的a同样是type variable。class constraints就是示例中的Num a。我们在定义重载类型时就使用Class a的格式进行类型限制。而以上这个type定义本身就是一个overloaded type
出现class constraints的地方就会出现运算符=>
myFunc1 :: Class a => a -> a -> a
myFunc2 :: (Class1 a, Class2 b) => a -> b -> a以下为一些变量的显式类型声明示例
type
myVar :: Int
myList :: [Int]
myTuple :: (Int, Int, Bool)class
myVar :: Fractional p => p
myList :: Integral p => [p]
myTuple :: (Integral a, Num b) => (a, b, Int, Bool)以下为一些函数的显式类型声明示例。注意，只要是出现了运算符->（用于顺序连接各个输入参数类型名以及唯一的返回结果类型名），就表示该声明为一个函数类型声明
type
-- 输入1个Int型变量，返回1个Int型结果
myFunc1 :: Int -> Int
-- 输入2个参数，1个Int型List，1个Int型变量，返回1个Int型结果
myFunc2 :: [Int] -> Int -> Int
-- Haskell中一个函数可以作为另一个函数的输入参数
-- 输入2个参数。例如myFunc3之后接受myFunc1作为函数参数，外加一个Int型变量。返回一个Bool型结果
-- myFunc1的type为(Int -> Int)
myFunc3 :: (Int -> Int) -> Int -> Bool
myFunc4 :: [a] -> aclass
myFunc1 :: Num a => [a] -> Int -> Bool
myFunc2 :: (Integral a, Fractional b) => a -> b -> Bool我们可以在ghci进行以下尝试对默认的字面数据类型进行大致的理解（使用:t命令查询一个表达式的类型）：
示例1，默认声明为Num（class）
ghci> myIntNum = 1987
ghci> :t myIntNum
myIntNum :: Num p => p
示例2，括号可以省略，显式声明为Int（type）
ghci> myIntNum = (1987 :: Int)
ghci> :t myIntNum
myIntNum :: Int
示例3，显式声明为Integer（type）
ghci> myIntNum = 1987 :: Integer
ghci> :t myIntNum
myIntNum :: Integer
示例4，显式声明为Integral（class）（注意和Integer进行区分）
ghci> myIntNum = 1987 :: Integral p => p
ghci> :t myIntNum
myIntNum :: Integral p => p
示例5，显式声明为Fractional（class）。显示时以小数形式
ghci> myIntNum = 1987 :: Fractional p => p
ghci> :t myIntNum
myIntNum :: Fractional p => p
ghci> myIntNum
1987.0
示例6，默认声明为Fractional（class）(从该示例开始常量为小数1987.875)
ghci> myFloatNum = 1987.875
ghci> :t myFloatNum
myFloatNum :: Fractional p => p
示例7，显式声明为Double（type）
ghci> myFloatNum = 1987.875 :: Double
ghci> :t myFloatNum
myFloatNum :: Double
示例8，报错
ghci> myFloatNum = 1987.875 :: Integral p => p
<interactive>:41:15: error:
• Could not deduce (Fractional p1)
...
示例9，报错
ghci> myFloatNum = 1987.875 :: Num p => p
<interactive>:47:15: error:
• Could not deduce (Fractional p1)
...
不是函数类型声明
函数本质由输入参数以及函数体表达式组成，函数只产生一个返回。函数的输入参数以及返回可以是函数或普通变量（包括列表和元组）。如果想要返回多个元素只能使用元组()或列表[]
函数的定义中，输入参数和函数体表达式之间使用=隔开
myFunc1 :: Integral a => a -> a -> a
myFunc1 x y = x `div` ymyFunc2 :: Int -> Int -> Int
myFunc2 x y = x + y同一个函数可以有多条定义语句对应，可以定义不同输入情况下的不同输出。这实际上是case语句的语法糖，需要注意判断条件有顺序要求，见2.4.3
myFunc3 [] = []
myFunc3 (x:xs) = xs可以使用do语句块规定该函数被调用时需要执行的多个语句，这些语句会依次执行
myAction x = do
inputNum <- getLine
putStrLn "Got it"Haskell中函数体表达式支持和其他语言类似的if else语句，区别是Haskell要求else分支不可省略
myAbs :: Int -> Int
myAbs n = if n > 0 then n else (-n)可以嵌套。和其他表达式一样，if else语句也可以放在括号内
myFunc x = if x > 0 then x else
if x == 0 then 1 else -x Haskell中有类似C中的switch结构，就是case语句（不是switch）。和C的switch语句只能使用非复合变量作为判断依据不同，由于Haskell中万物皆表达式，case同样可以输入表达式。语句中每一行都是真值以及对应的返回值（返回语句），两者使用->隔开。Haskell的case语句不存在break的概念，而是和if else一样，然而如果各条件之间有包含或交集关系，需要将范围较小或我们偏好的匹配条目放在前面。如下例中匹配条件_事实上包含了14与15，依照程序本意需要放在最后
myFunc x = case (x - 1) of
14 -> x - 1
15 -> 0
_ -> 2
Haskell的case语句可以看作就是嵌套if else的变种，程序会依次匹配。而以C为代表的一些较贴近底层的语言中，switch语句和嵌套if else并不是等价的，C的switch基于跳转表，它只能接受非复合变量为判断跳转依据，且大部分已有的ISA都为C的switch语句提供专用的指令支持，如ARM的TBB和TBH指令。因此C的switch在遇到较多分支时可以达到优于嵌套if else的平均表现。也是因为非复式变量的原子性，C中的switch语句除default以外其余case条件不会出现交集
另一种条件格式，使用|分隔。本质和case与if else是相同的，更易阅读。otherwise用于匹配所有的其他情况，放在最后
myAbs x | x >= 0 = x
| otherwise = -x上面我们讲述过Haskell中同一函数的多条定义语句，用以针对不同的输入，此时我们就需要针对所有可能的输入进行处理，防止程序异常。但是有些特定情况下，函数的输入输出对应关系无法使用一个或数个特定表达式表述，只能使用逐个列举的方法，这有可能会非常繁琐。由此Haskell定义了通配符_，用以匹配同一type的任意值。例如逻辑与函数(&&)可以使用如下定义：
(&&) :: Bool -> Bool -> Bool
True && True = True
_ && _ = False实际上在库中(&&)是如下定义的：
True && b = b
False && _ = False以上使用了变量
b。然而Haskell不允许一个变量在函数的参数列表中多次出现。遇到这种情况只能使用前面讲述的条件语句
在Tuple中使用通配符_，传入函数的元组必须有对应的长度，例如fst以及snd的定义。我们可以将不想要（不会在函数体表达式中出现）的输入参数写成_
fst :: (a,b) -> a
snd :: (a,b) -> b
fst (x,_) = x
snd (_,y) = y也可以在List中使用_，结合构造符:可以有许多巧妙的应用
-- 判断是否为长度为3且以字符'a'开头的字符串
myFunc1 ['a',_,_] = True
myFunc1 _ = False
-- 判断是否为'a'开头的字符串
myFunc2 ('a':_) = True
myFunc2 _ = False
-- 取List头
myHead (x:_) = x -- 写成(x:xs)作用是一样的Haskell将函数和数据（变量）同等看待。Lambda表达式即匿名函数，是Haskell的核心，本质和函数相同，都是数据处理方式的表达。它具备函数的参数输入以及函数体，但是没有名字。事实上Haskell中所有的函数最终都会转换到Lambda表达式的语法树处理方法。处理Lambda表达式的理论都属于Lambda Calculus，美国逻辑学家Haskell Brooks Curry（1900-1982）对这个领域作出了突出贡献，这也是Haskell名称的由来。之前的Curried Functions（咖喱函数）概念也是起源于此
Haskell中使用反斜杠\代替希腊字母
\x -> x * 2
单独的Lambda表达式无法构成完整的运算，在程序中不被允许
和有名函数一样，调用Lambda表达式的实参写在表达式后，使用空格 分隔
Lambda表达式的用法有多种形式：
直接将Lambda表达式写到其他有名函数体中
或者什么也不添加，直接为该表达式起一个函数名，之后该函数名可以作为其他函数的参数传入
将Lambda表达式应用（apply）到输入变量上，返回一个数据结果后赋一个变量名
...
简单示例
-- 3^2，myVar1等于9
myVar1 = (\x -> x ^ 2) 3
-- 2^6，myVar2等于64。->右结合，里层的括号可以不加，但是外层括号必须加
myVar2 = (\x -> (\y -> x ^ y)) 2 6
-- myFunc1将两个输入相加后返回
-- 相当于 myFunc1 x y = x + y
myFunc1 = \x -> \y -> x + y
-- 结果等于9
myVar3 = myFunc1 5 4
-- myFunc2将输入加4
-- 相当于 myFunc2 a = (\x -> \y -> x + y) 4 a
myFunc2 = (\x -> \y -> x + y) 4
-- 结果等于11
myVar4 = myFunc2 7
-- myFunc3输入x，返回2^x。这里由于x属于最外层Lambda的输入，x可以省略
myFunc3 x = (\a -> \b -> a ^ b) 2 x
-- Lambda中符号的作用域仅限于表达式内且独立。myFunc3和myFunc4相同，myFunc4传入的参数x和Lambda表达式中的x不是同一个，不会冲突
myFunc4 x = (\x -> \y -> x ^ y) 2 x
-- 甚至可以将一个表达式应用到另一个表达式上面，因为Haskell中数据和函数两者地位相同
-- myFunc5相当于myFunc5 a = 2 ^ (a + 1)，这里的a属于内层Lambda输入，不能省略
myFunc5 a = (\x -> \y -> x ^ y) 2 ((\x -> x + 1) a)
-- 也可以应用函数名，abc不可省略
myFunc6 a b c = (\x -> \y -> x ^ y) (myFunc1 a b) ((\x -> x + 1) c)
-- 结果(-3 + 5) ^ (4 + 1) = 32
myVar5 = myFunc6 (-3) 5 4这里再次回到
Haskell中函数本质的理解方法在
Haskell中我们调用一个函数a向它传参（显式定义的有名函数或Lambda表达式都可以，但是a必须是函数。其实显式定义的有名函数最终也可以转化为匿名函数处理），就相当于将一个函数体f或数据d注入（也可以理解为替换）到这个函数a里面，之后将注入后的运算结果或函数体返回，这个过程的官方称呼就是应用（apply），也即我们将函数a应用到函数f或数据d
关于Lambda Calculus的更多内容可以参见5.1
Haskell中除保留符号以外的运算符号不属于语言本身的特性，需要进行定义
我们可以在一个拥有2个参数输入的函数名外部加上``括起来，作为中置运算符使用，如下示例
va = 32 `div` 4 -- 相当于 div 32 4相反的，我们可以在+ - * ^等运算符外部加上()括起来，这样可以作为前置运算符使用，这就是Operator section，它相当于一个Lambda表达式
va = (+) 3 14 -- va为17。(+)相当于表达式\x -> (\y -> x + y)还可以在()内的中置运算符任意一边加上一个表达式
addTwo = (+2) -- 相当于\x -> x + 2
va = addTwo 13 -- 结果为15
Operator section一般有以下作用：以简化的方式定义表达式用于简单的运算，例如加1操作可以定义为
(+1)用于定义新的运算符或重载运算符（函数名不能含有下划线以外的特殊符号）
将该运算符定义的函数运算作为参数传入到其他函数中，例如
sum = foldl (+) 0
List comprehension类似于数学语言中对于一个集合中数据的描述信息（Comprehension notation）。我们定义3到12的自然数，数学语言写作 $ {x | x \in \mathbb{N}, 3 \leq x \leq 12 } $ 。在Haskell中，定义一个这样的List，只需要[x | x <- [3..12]]即可
我们讲到过Haskell中Lambda表达式的基本格式。下式相当于3 * 2
\a -> (a * 2) 3
本小节我们规定为以下格式，apply依然为空格，将->替换为.，\依然代表$ \lambda $，表示binder绑定操作
\a.(a*2) 3
在Lambda表达式中apply操作的运算符就是一个空格 ，写作a f或a d，且apply操作是左相联的。a b c等于((a b) c)而不是(a (b c))。apply操作的本质就是将 运算符后面的函数或数据带入到前面的函数中（这里的函数是匿名函数也即Lambda表达式）
在实际应用中，我们一般认为apply表达式中左侧的符号是一个函数，右侧符号（即被apply的符号）可以是函数或变量，例如a (b c)中，a和b一般是一个函数名，而c是一个数据。我们可以将一个函数apply到另一个函数或数据上，而将一个数据apply到其他函数或数据上是无意义的
\即绑定符binder，后面紧接匿名函数的形参（即bound variable），如\x，这个形参x的作用域局限于该匿名函数内。按照上面规定的格式，\x后面必定会接一个.，成为\x.M的形式
\操作的本意是将符号x规定为该表达式内需要替换的参数。所谓替换即apply
在Lambda表达式中基本的操作只有bind和apply两种，apply优先级高于bind。可以使用括号()规定运算顺序
完整的Lambda表达式简单示例：
\x.\y.x y x
相当于
\x.(\y.((x y) x))
运算顺序遵照括号层次
我们在这里引入一种Lambda表达式二叉语法树的构造方法，在语法树中我们将apply运算定义为分支节点@，其下左分支节点将会被apply到右分支节点；而bind运算定义为\。观察以下示例
\x.((\z.z x) ((\r.\s.s r) y f))
构建语法树结果
\的左支永远都是叶子节点bound variable
所谓自由变量，就是在一个Lambda表达式中未被bind的变量。Free variable的存在往往意味着表达式的不完全替换，该表达式在被apply后返回的结果是一个表达式而不是最终的数据
示例
\x.\y.x x -- 无FV
\y.x x -- FV为x
\x.\x.x -- 无FV
我们使用 M的自由变量
Reduction就是依照Lambda表达式定义的apply以及bind规则进行的一系列代入替换操作，准确来说是 (\x.M) N，称为
此外还有
$\alpha -$ Equivalence等基础概念不再讲述
以上例
\x.((\z.z x) ((\r.\s.s r) y f))
Reduction步骤如下
-> \x.((\z.z x) ((\s.s y) f))
-> \x.((\z.z x) (f y))
-> \x.((f y) x)
-> \x.(f y x)
到语法树中，看到如下结构就表示可以进行1步Reduction替换。替换后产生新的类似结构需要继续进行处理。建议遍历替换操作依照从下层向上层，先右支后左枝的顺序
Y Combinator是一种解决Lambda Calculus中无法实现函数递归的方案。实际编程当中很少会涉及到Y Combinator。Haskell中使用了lazy evaluation来应对函数递归的问题，而不是Y Combinator
在讲Y Combinator之前先要引入一个Fixpoint的概念。例如函数
$f(x) = x^2$ ，我们都知道$f(0) = 0, f(1) = 1$ ，也就是说对于$0$ 和$1$ 来说，$f(x) = x^2$ 将它们映射到了自身，那么我们就认为$0$ 和$1$ 就是$f(x)$ 的Fixpoint，$fix (f) = {0,1}$ ，同时我们可以推导出$f(f(f(f(0)))) = 0$ ，$f(f(f(f(1)))) = 1$
Lambda Calculus中一个函数的输入可以是另一个函数。Y Combinator定义如下
Y = \f.(\x.f(xx))(\x.f(xx))
假设我们将
$$ \begin{align*} Yg &= (\lambda f.(\lambda x.f(x x))(\lambda x.f(x x))) g\ &={\beta} (\lambda x.g(x x))(\lambda x.g(x x)) \ &={\beta} g((\lambda x.g(x x))(\lambda x.g(x x))) \ &={\beta} g(Yg) \ &={\beta} g(g((\lambda x.g(x x))(\lambda x.g(x x)))) \ &={\beta} g(g(Yg)) \ &={\beta} g(g(g(Yg))) \ &=_{\beta} ... \end{align*} $$
也就是说，
下面假设我们有一个add函数，它是一个有名函数，定义如下：
add a b = if b == 0
then a
else add (a+1) (b-1)
这个有名函数无法转换为有限长度的Lambda表达式，如果我们对它的语法树进行构建，会陷入死循环
这里说明的是Lambda Calculus计算系统对于递归实现的先天不足。能否递归和函数有无名无关
接下来我们对add稍加更改。我们在add函数名后紧接着添加一个参数f，这样add的函数体表达式内就不会出现add这个名称，语法树不再是无限大。当然这样单独的add也就不再表示递归的含义，失去了本义
add f a b = if b == 0
then a
else f (a+1) (b-1)
改进后的add可以使用Lambda表示如下
\f.\a.\b.(if b == 0 then a else f (a+1) (b-1))
接下来我们将Y=\f.(\x.f(xx))(\x.f(xx))应用到更改后的add，那么此时一定有
Y add
= add (Y add)
= add (add (Y add))
= add (add (add (Y add)))
...
上式第二行，我们就相当于给
add f a b的f传入了一个参数(Y add)，返回的表达式相当于\a.\b.(if b == 0 then a else (Y add) (a+1) (b-1))
我们设Y add为一个新的函数add'。那么我们计算add' 3 2可以得到以下推导过程
add' 3 2
= (Y add) 3 2
= add (Y add) 3 2
= (\a.\b.(if b == 0 then a else (Y add) (a+1) (b-1))) 3 2
= (Y add) 4 1
= (Y add) 5 0
= 5