Haskell学习笔记(一)

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

搭建环境

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

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

然后我用的编辑器是Atom,装了language-haskellautocomplete-haskellhaskell-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对参数是惰性求值的,只有真正用到,才会求值,可能导致的结果是即便用了尾递归,也可能发生扩展递归的大量展开的情况。这时就需要$!来强制参数求值。这一点在这里记录下。

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