Haskell 函数式编程初探

一直以来对函数式编程非常好奇，但是没有用到的机会。上次去图书馆还书，记起二哥写过Haskell的博客，刚好自己这学期有时间，就借了一本Haskell的书，开始了我的Haskell之旅。

函数式的特点

函数式编程与之前用到的面向过程编程、面向对象编程都有很大不同。尤其是Haskell这样的纯函数式语言。

引用维基上的话：

In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data.

就是说，函数式编程作为一种编程范式，主要的思想就是将电脑运算视为函数计算，把运算过程写成一系列嵌套的函数调用。

函数式编程有以下几个特点：

1. stateless

函数不维护任何状态。函数式编程的核心精神是 stateless，简而言之就是它不能存在状态，你给我数据我处理完扔出来，里面的数据是不变的。

1. immutable

输入数据是不可能的，动了输入数据就有危险，所以要返回新的数据集。

这几个特点带来的好处是：

1. 没有状态就没有伤害
2. 并行执行无伤害
3. Copy-Paste重构代码无伤害
4. 函数的执行上没有顺序问题

Haskell作为函数式编程语言的特点

Haskell是一门纯函数式语言，它编写的函数是完全没有状态的函数。

除此之外，Haskell还具有惰性求值的特性，就是说所有的值只有在用到的时候才会进行计算，用不到就不会计算。它的优点是：

• 避免了不需要的运算，从而提高的性能。

• 使创建无限的数据结构成为可能

另外值得一提的是，Haskell是静态的。

基本数据类型

Haskell的数据类型与C的大同小异。

• Int
• Integer： 无界的整型
• Float
• Double
• Bool
• Char
• Tuple

基本运算

Haskell拥有与C不太一样的符号体系。基本来说也是大同小异。

+ - * / || && == 与C完全一样。

取反要用not 。

模数运算要显式调用mod 函数。

调用函数

要区分Haskell与C调用函数的区别

--已知函数f,g
f x --这就是计算f(x)了
g x y --这就是计算g(x,y)
--上面提到的模数运算
mod 3 2 --计算3除以2的余数
--如果想改用中缀表达，需要加上反引号
3 `mod` 2 --任何接受两个参数的函数理论上都可以用这种方法改写为中缀表达

列表

在Haskell中，列表是一种特别常用的单类型的数据结构。

[4,8,15,16,3,22]

列表可以被拼接

[1,2]++[3,4]++[5,6]
-- [1,2,3,4,5,6]
"hello" ++ "" ++ "world"
--"hello world"

这里有一件很有意思的事要提一下，Haskell中的字符串实际上是一组字符组成的列表。也就是说字符串实际上是列表的语法糖而已。Cool! 所以呢，我们可以用所有处理字符串的方法处理列表。

列表前插一个元素的成本几乎为0：

5:[1,2,3,4,5]
--[5,1,2,3,4,5]

后接元素只能用列表拼接：

[1,2,3,4] ++ [5]
--[1,2,3,4,5]

更有趣的是，[1,2,3,4,5] 实际上是1:2:3:4:5:[] 的语法糖而已。[] 表示一个空列表，从前面插入5，就变成了[5] ，以此类推。

对列表的操作

• 构造列表

  --使用区间
  [1..5]
  --[1,2,3,4,5]
  
  --等差推导
  [2,4..10]
  --[2,4,6,8,10]
  
  --无限大的数组
  [1..] --惰性求值特性
  
  
  --列表推导式
  [x*2 | x <- [1..10], x >= 12]
  
  --运用这个特点我们能做一些很酷的事情，比如求前10个7的倍数或末尾含7的数：
  take 10 [x | x <- [1..], x `mod` 7 ==0 || x `mod` 10 == 7]

• 访问列表

  --按照索引取得列表元素：！！
  "hello world" !! 2
  -- l
  
  --返回列表的头：head
  head [1,2,3,4,5]
  --1
  
  --返回列表的尾：tail
  tail [1,2,3,4,5]
  --[2,3,4,5]
  
  --返回列表的最后一个元素
  last [1,2,3,4,5]
  -- 5
  
  --返回除去头外的列表
  init [1,2,3,4,5]
  -- [2,3,4,5]
  
  --取一个数字和一个列表作为参数，返回列表中指定的前几个元素
  take 3 [1,2,3,4]
  --[1,2,3]
  take 0 [1,2,3]
  --[]

• 比较列表

只要列表内的元素是可以比较的，那就可以使用> < <= >= 来比较两个列表的大小，它会按照字典顺序。非空列表总认为比空列表更大。

• 其他操作

  --返回列表的长度
  length [1,2,3,4,5]
  --5
  
  --检查列表是否为空
  null []
  --true
  
  --删除一个列表中指定的前几个元素
  drop 2 [1,2,3,4]
  --[3,4]
  drop 0 [1,2,3,4]
  --[1,2,3,4]
  drop 100 [1,2,3,4]
  --[]
  
  --返回列表最大元素
  maximum [1,2,3,4,5]
  --5
  
  --sum返回一个列表的和，product函数返回一个列表的积、、
  sum [2,3,1,5,4]
  product [1,2,3,4,5]
  
  --判断一个元素是否包含于一个列表，常用中缀形式
  3 `elem` [1,3,4,5]
  --True

编写函数

  --定义一个函数triple，返回输入参数的三倍。
  triple x = 3 * x
  
  --拥有多个参数的函数
  length x y = sqrt (x * x + y * y)

### 模式匹配（pattern matching）

如果考虑对函数的参数分类，检查参数的结构是否为真，可以采用模式匹配。

  --识别1-3数字并转换为对应的单词，其他的对应输出为”not between 1 and 3"
  toWord 1 = "one"
  toWord 2 = "two"
  toWord 3 = "three"
  toWord x = "noot between 1 and 3"

模式匹配的顺序是自上而下的。

哨卫（guard）用来检查参数的性质是否为真：

  bmiTell bmi
     | bmi <= 18.5 = "underweight"
     | bmi <= 25.0 = "normal"
     | bmi <= 30.0 = "overweight"
     | otherwise = "go die"

递归

模式匹配可以帮助我们实现很多事情，比如下面的求阶乘的例子。

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

上面的函数就是使用了模式匹配的阶乘函数。我们可以在C语言里使用循环，但是Haskell没有循环，但是依旧可以用递归实现。理论上来说所有的循环都能转换为递归。

下面再给出一个递归的例子，求了列表元素的最大值：

maxInList [] = error "the list is empty"
maxInList [x] = x
maxInList (x:xs) = max x (maxInList xs)

如果一个列表里只有一个元素，那么这个元素就是最大的。否则，就应该是这个列表第一个值和其余部分中的最大值中比较大的那个。

总结一下上面几个例子，不难得出Haskell递归的固定模式。首先定义基准条件，也就是对应特殊输入的简单非递归解。然后将问题分解为一个或者多个子问题，并递归的调用自身，最后基于子问题里得到的结果，组合成为最终解。

最后看一下快速排序的实现：

quicksort [] = []
quicksort (x:xs) = (quicksort [y | y <- xs, y < x]) ++ [x] ++ (quicksort [y | y <- xs, y >= x])

高阶函数

可以接受函数作为参数，也可以将函数用作返回值，这样的函数称为高阶函数。

柯里化函数与Hindley-Milner类型签名

在计算机科学中，柯里化（Currying）是把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数，并且返回接受余下的参数且返回结果的新函数的技术。

看一个例子：

max 4 5
--5
f = max 4
f 5
--5

我们先看看这个函数的类型：（在GHCI中使用`:t max)

max :: (Ord a) => a -> a -> a

看起来的确复杂，实际上这是一个叫Hindley-Milner类型签名的东西，Haskell主要使用这种东西来标记一个函数的类型。

深入学习可以参考：

Hindley-Milner类型系统(1)

可以理解为这里有两个函数：

一个使max本身，它接受一个a 类型参数，返回一个Ord a => a -> a 的函数，这个新函数接受一个a 类型的参数，返回一个a 类型的参数。

上面的声明也可以写成下面的样子：

max :: (Ord a) => (a -> (a -> (a)))

这样的好处是：我们只要以部分的参数来调用某函数，就可以得到一个部分应用函数，部分应用函数所接收的参数的数量，和之前少传入的参数的数量一致。部分应用使得构造新函数快捷简便，随时可以为传递给其他函数而构造出新函数。

类型类

类型类（typeclass）是定义行为的接口（interface），也就是“一种类型的能力。说的简单一些，typeclass就要求一个类型能被放在某个函数的参数里做运算。

有以下一些常见的typeclass：

• Eq类型类

可判断相等性的类型，要求类型实现了==和/=两个函数。

• Ord类型类

可比较大小的类型，要求类型实现了compare。

• Show类型类

可以转成字符串，也就可以被显示出来的类型，实现show。

• Read类型类

可以从字符转出来的类型，实现read。

• Enum类型类

可以求其前驱和后继的类型，实现pred和succ。

• Bounded类型类

有界的类型，实现minBound和maxBound。

• Num类型类

表示数值的类型类，基本上就是Int、Integer、Float、Double。

• Floating类型类

表示浮点数的类型类，基本上就是Float和Double。

• Integeral类型类

表示整数的类型类，基本上就是Int（会溢出的整数）和Integer（大整数）。

玄学

俗话说得好，一入 FP 深似海，从此 Monad 皆是自函子范畴上的幺半群。这句话说的是什么呢，详细解释起来就是一堆玄学玩意儿。

所以这里挖个坑，以后会补上详细的范畴和函子、自然变换以及单子的学习博客。这里先长话短说。

什么是范畴呢，从某种意义上来讲，范畴是集合论中集合在某种概念上的推广。推广的关键就是考虑集合中的元素到另外一个元素的映射关系。

范畴包括一类对象组成的集合，所有对象之间的态射组成的集合，任一对对象间的态射组成集合。态射可以组合起来，态射的组合操作满足结合律。每个对象都存在一个单位态射id，该态射对任意其他态射的组合都是其他态射本身。

在 Haskell 中，对应的是：

• object对应着某个具体的函数
• 态射对应着函数之间的映射，这种映射产生新的函数。比如f::(a→b)→a→b
• 态射的复合运算代表着函数的复合（复合函数），比如 h = f . g

如果我们把范畴看成是一个更高层的范畴的对象，两个范畴之间的态射就是函子（Functor）。

Functor

看看函子的类型类怎样用代码表示

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Functor是一个类型类，它要求实现了它的类型实现fmap函数。

fmap 函数接收两个参数，第一个参数是以a 为参数，b 为返回值的函数；第二个参数类型为f a ，fmap 的返回值类型为f b 。

更通俗的讲，函子值就是可以被map-over（即通过map向对象中的子对象应用一个函数）的对象。

可以从下面两个角度思考fmap: 1. 接受函数和函子值，返回在函子值上映射函数的结果（返回也是函子值）。 2. 接受函数，把该函数从操作普通类型的函数提升(lift)为操作函子值的函数。

Haskell的列表就是一个Functor。

map :: (a -> b) -> [a] -> [b]

instance Functor [] where
　　fmap = map

Haskell中的Set和Maybe（可空值）也是Functor。

Maybe 在后面讲Monad的时候会用到，现在这里介绍一下：

instance Functor Maybe where
    fmap func (Just x) = Just (func x)  -- 有东西写作 Just xxx, map上去就是Just f(xxx)
    fmap func Nothing  = Nothing		-- 没东西写作 Nothing, map上去还是Nothing

Applicative

Applicative是Functor的升级版本（也称Applicative Functor）,俗称加强版函子。先看代码：

class (Functor f) => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

Applicative类型类定义了两个函数：pure和<*>(其实还有一个fmap ， 因为Applicative实例肯定是Functor的实例，所以fmap免费提供了)。

pure是一个很简单的函数，接收任意类型的值为参数，返回包裹了该值的Applicative值。

<*>函数看起来和fmap有些像，唯一的区别是fmap的第一个参数接收一个普通函数(a -> b)，而<*>的第一个参数为f(a -> b)， 即把普通的函数用Applicative包裹。

下面看以下列表作为Applicative实例的实现：

pure x = [x]
(<*>) fs xs = [f x | f <- fs, x <- xs]

总结一下，Applicative主要定义了两个行为，第一个行为是接收一个任意值为参数，返回一个函子值， 第二个行为是从一个函子值里取出函数，应用到第二个函子里面的值。

网上找到的例子：

[(*0), (+100), (+200)] <*> [1, 2, 3]
-- 输出结果: 0,0,0,101,102,103,201,202,203

(*0)是对*函数的部分应用，*是一个二元函数，接收两个参数，返回这两个参数的乘积。(*0)是一个一元函数，接收一个参数， 返回这个参数与0的乘积。第一个列表里面是三个一元函数，分别应用到第二个列表的元素。 这种把<*>串起来用的用法叫做Applicative风格。

Monad

终于出现前文提到的自函子范畴上的一个幺半群了。

相比Functor和Applicative，Monad的应用更加广泛，Monad可以看作加强版的Applicative。上代码：

class Applicative m => Monad m where    
	return :: a -> m a     
	(>>=) :: m a -> (a -> m b) -> m b

Monad相对于普通函子多出来的约束就是多了两个自然变换(return, bind)，这两个函数满足以下公理：

• return 与 >>= 互为逆操作

  (return x) >>= f == f x
  m >>= return == m

• >>= 满足结合律

  (m >>= f) >>= g == m >>= (\x -> (f x >>= g))

前面说的Maybe就是一个Monad:

class Applicative Maybe => Monad Maybe where
    return :: a -> Maybe a
    (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b

half x = if even x
    then Just (x `div` 2)
    else Nothing

Prelude> Just 20 >>= half						-- 把Just 20塞进half函数里
Just 10
Prelude> Just 20 >>= half >>= half				-- 把Just 20的结果塞进half函数里
Just 5
Prelude> Just 20 >>= half >>= half >>= half
Nothing

Monad接受一个上下文中的值和一个(接受普通值返回上下文中的值)的函数，返回一个上下文中的值。

纯函数的优点是安全可靠。函数输出完全取决于输入，不存在任何隐式依赖。它的存在如同数学公式般完美无缺。但是因为隔绝了外部环境，纯函数连基本的输入输出都做不了。

以IO Monad为例子。Monad 将带有副作用的 IO 操作以一种可控的方式引入到 Haskell 中，让纯函数与 IO 操作能够和平相处，共同组织出既安全又有用的程序。

return 的作用是将某个类型为 A 的值 a 以最自然的方式提升（装箱）为类型为 IO A 的值 Char -> IO Char 。有了这个函数后，纯函数就可以通过与 return 复合变成返回值为 IO 带副作用的函数了，当然，实际的 IO 动作是 Haskell 内建的，return 的主要意义在于类型提升。

有了提升可没有下降操作，怎么复合 putChar :: Char -> IO() 与 getChar :: IO Char 呢。 getChar 从 IO 读取一个字符， putChar 把字符写入 IO。但 getChar 返回的是 IO Char 类型，而 putChar 需要的是普通的 Char 类型，两者不匹配怎么办？ >>= 函数出马了！ >>= 的类型是

IO a -> (a -> IO b) -> IO b

这样 >>= 就可以连接 getChar 与 putChar ，把输入复写到输出中

echo = (getChar >>= putChar)

可以看到 >>= 操作实际上是受限的类型下降（或拆箱）操作，只有当后面的函数返回值也是 IO 类型时才进行下降操作。这样既充分隔离纯函数与副作用函数，又能让函数相互复用。

//写不动了，先写这些吧