转载

Haskell学习笔记（一）

这周开始把空余的时间花了在学时间Haskell上，因为想学一门纯FP语言，拓展思路，体会另一种编程思想。其实学FP在几个月前就开始了，但是主要在看 JS函数式编程指南，感觉有点抽象，没有特别理解其中的一些概念。所以现在从一门纯FP语言入手，顺便之后可以玩玩Elm。

搭建环境

最开始首先是要搭一个环境，Haskell的代码需要通过编译器编译执行，它最常用的编译器叫 ghc 。不过它还提供了一个解释器 ghci ，充当一个REPL的角色。

直接去官网选择对应平台下载即可，我下的是 Minimal installers ，包含 ghc 以及包管理工具 Cabel 。

然后我用的编辑器是Atom，装了 language-haskell 、 autocomplete-haskell 、 haskell-ghc-mod 以及 ide-haskell 这几个工具来辅助开发。

编译了一个HelloWord的程序出来，发现生成的文件比用C写的要大些。

类型系统

Haskell是一门强类型语言，先看看它的基本类型：布尔类型（Bool），字符型（Char），有符号整数（Int），无符号整数（Word），任意精度整数（Integer），字符串（String），小数（Float，Double），有理数（Rational），元组，列表。

给人一种很『数学』的感觉。比较重要的应该是元组和列表结构了。元组的的特点是可以放任意类型的数据，但不可伸缩，表示为： (Int, Char, Bool) 。列表正好相反，它要求数据类型需要相同，并可以用 (:) 或者 (++) 来伸缩列表，表示为： [Int] 。另外String类型其实就是字符列表 [Char] 类型。

声明一个变量类型的例子：

a :: [Int]   a = [1, 2, 3]

既然是FP，那么函数其实和其他数据没什么区别，它可以声明类型的，比如以加法为例：

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

类型的声明语法，使用的是 Hindley–Milner type system ，具体的语法可以点击链接或者search下，这里不展开了。

在Javascript中，实现函数柯里化需要额外实现一个帮助函数，而在Haskell中，柯里化则是函数的基本特性，也就是说柯里化是自动的。比如在ghci中查看类型：

Prelude > :t (+1)   (+1) :: Num a => a -> a

由于 (+1) 仅提供了一个参数，于是它自动柯里化返回了一个函数。同时我们也发现， 在Haskell中运算符也是函数 。

注意到上面的例子中还涉及到了类型限定符 => ，限定参数的类型类，类型类（type class）是用来表示类型的类别的。这在同为强类型的java或C#等OO语言中是没有的。比如说Eq类型类表示数据是否可以比较相等，Num类型类表示数字类型的数据。

类型可以看作是类型类的一个实现，比如Ord类型类的数据类型都可以通过 < 或者 > 来比较，而没有实现Ord类型的数据类型就无法使用 < 或者 > ，这在一定程度上充当了OO语言中接口的角色，而在Haskell中其实并没有Interface的概念。

常见类型类：

Eq 相等类型类
Ord 有序类型类
Enum 枚举类型类
Bounded 有界类型类
Num 数字类型类
Show 可显示类型类

没有类型限定的函数叫 多态函数 。

不过在定义函数的时候，函数的类型也是可以省去的， Haskell自带类型推断系统会给出一个合理的类型 。不过还是建议加上类型声明，有助于日后对于自己和他人的理解。

函数

首先是这两个应该已经非常熟悉的概念，这里再啰嗦下：

纯函数：对某个特定的输入总是返回相同的输出，且不包含副作用。

高阶函数：以其他函数为输入，或者以函数作为输出结果的的函数。

lambda表达式在Haskell中的语法是以反斜杠开头代表参数的，感觉没有C#的lambda表达式语法那样优雅，不过无所谓了，来看个简单的例子：

> (/x -> /y -> x y)(abs)(-5) 5

记录几个概念，比较好理解的：

alpha替换：不出现命名冲突的情况下可以给函数的参数重新命名。
beta化简：参数到函数体的替换。比如 (/x -> /y -> x y)(abs) 可以直接替换成 (/y -> abs y) 。或者就是理解为参数的代入。
gamma化简：消去冗余的lambda表达式。比如 (/y -> /x -> (+) x y 可以直接用 (+) ，不需要其他冗余的表达式。

单一同态限定（Monomorphism Restriction），引入的目的有二：避免重复计算和消除类型歧义。留个坑在这里，我完全没有理解这个东西。

运算符

在Haskell中，运算符号有0——9，共十个优先级。结合性又分为左结合性、右结合性、无结合性。又可以根据位置分为前缀、中缀和后缀运算符， 一般的函数可以理解为前缀运算符 ，且拥有最高优先级，比9还高。

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

模块化

最基本的模块导出：

module Test where   ...

这样写的话，相当于将这个文件里定义的所有内容都导出了。也可以在导出时做限定：

module Test (f1, f2) where   f1 = ...   f2 = ...   f3 = ...

这样的话，就仅导出f1，f2。

接下来是模块导入：

import Test -- 导入全部函数   import Test (f1) -- 只导入f1   import Prelude hiding (catch) -- 导入Prelude除了catch函数   import qualified Test as T -- 避免命名冲突，Test模块中的所有函数需要通过T.xxx访问

其中Prelude表示的Haskell预加载库。

递归

定义一个递归在Haskell中是相对比较直观的。递归函数定义可分为两部分：

递归的基本条件
递归步骤

通过模式匹配，可以比较直观的写出递归，如下是一个插入排序的例子：

insertSort :: Ord a => [a] -> [a]   insertSort [] = []   insertSort (x:xs) = insert x $ insertSort xs     where     insert n [] = [n]     insert n (y:ys) | n < y = n:y:ys       | otherwise = y:insert n ys

这边相对陌生的概念就是 不动点 了，它的概念是：当参数应用到这个函数时，结果是这个参数本身，即 x = f(x) 。立马想到了冒泡排序：

-- 不动点 x = f(x) fix :: Eq a => (a -> a) -> a -> a   fix fn x | x' == x = x     | otherwise = fix fn x'   where     x' = fn x  -- 冒泡排序 bubbleSort :: Ord a => [a] -> [a]   bubbleSort = fix swaps     where     swaps [] = []     swaps [x] = [x]     swaps (x:y:xs) | x > y = y: swaps(x:xs)       |otherwise = x: swaps(y:xs)

最后要提一下尾递归。Haskell是支持尾递归的，不过有个坑，就是 Haskell对参数是惰性求值的 ，只有真正用到，才会求值，可能导致的结果是即便用了尾递归，也可能发生扩展递归的大量展开的情况。 这时就需要 $! 来强制参数求值 。这一点在这里记录下。

结束了，我只学到这个地方。

正文到此结束