Simple Introduction to Haskell

写在前面

简单介绍一下函数式编程和 Haskell 的特性以及一些简单的使用经验，需要有一定的编程经验。 最好准备一个可以使用的 GHCi。

Homebrew 用户可以使用 brew install haskell-stack 安装 Haskell Stack 后使用 stack new helloworld new-template 创建 helloworld 工程， 通过 stack ghci 打开 GHCi。 (请参考 Haskell Stack 文档)

大量材料来自 @cafe2code 在清华 Haskell 线下会上的分享内容。

Programming Language

什么是函数式编程

许多现代语言诸如 C#、Scala 引入了函数式特性，C++11 也引入了 Lambda 语法支持函数式特性。

Lambda 表达式

Java 8 的 Lambda 表达式:

				Runnable r = () -> System.out.println("Java 8.")
				Runnable r = new Runnable() { // In Java 7
				    public void run() {
				        System.out.println("Too verbose!");
				    }
				}
			

Mutable vs. Immutable State

                class State {
                    int a;
                    int b;
                }
              

                class State {
                   final int a;
                   final int b;
                }
              

Mutable vs. Immutable State

                State setAto1(State s) {
                    s.a = 1;
                    return s;
                }
              

                (State s) ->
                    new State(1, s.b)
              

函数式编程的特性

• 一等函数 (First-class functions)
• 引用透明 (Referential Transparency)
• 非严求值 (Non-strict evaluation)
• ...

使用常用的术语解释：函数可以作为参数传递、函数不产生副作用以及惰性求值。

函数式语言

• 数学基础: λ-演算
• 动态类型: Lisp、APL
• 静态类型: ML、Haskell

函数式语言的应用

• 类型系统/特性的研究
• 领域特定语言
• 形式化证明
• ...

λ-演算

• 由阿隆佐·邱奇和他的学生斯蒂芬·科尔·克莱尼在20世纪30年代引入
• 最小的通用程序设计语言 (图灵完备)
• 各种函数式语言理论基础

λ-演算

				<expression> ::=   <variable>
				               | λ <variable> . <expression>
				               |   <expression> <expression>
			

作用域规则

• 绑定变量 (Bound variable) vs. 自由变量 (free variable)
• 单个变量构成的表达式，变量是自由变量
• λ表达式中，变量被最近的λ绑定
• 应用表达式中，两条子表达式分开考虑

β-归约

将 (λx.<left>) <right> 形式的表达式 <left>中自由出现的 x 重写为 <right> (规约顺序不定)

求值策略

• 严格求值: 在函数调用时对函数调用的所有参数求值后传入函数
• 非严求值: 在函数调用时不对参数进行求值

柯里化 (Currying)

我们需要函数接受多个参数的时候……

				var add = (a, b) => a + b
			

					var add = (a) => (b) => a + b
				

Haskell

• 纯函数式语言
• 默认惰性求值
• 支持函数重载
• 函数式编程研究前沿
• 生态系统

GHCi

Haskell 的 REPL 界面

类型系统

Haskell 是静态类型的函数式语言。那有什么好处呢？

使用 GHCi :type 命令:

• \x -> x
• \x -> (\y -> x)
• (\x y -> x) (\x -> x)
• (\x -> x x) (\y -> y y)

基本类型

• 函数 \x -> x :: r -> r
• 整数 10 :: Num a => a
• 浮点数 1.1 :: Fractional a => a
• 字符串 "string" :: [Char]
• 元组 ("elem", 1) :: Num t => ([Char], t)
• 列表 [1, 2, 3, 5, 7, 11] :: Num t => [t]

:: 读作「has type of」，=> 表示 class constraint

List

列表是十分重要的数据结构。Haskell 中可以这样构造一个列表:

				let l = [ 1, 2, 3, 4, 5 ]
				let l = [ 2, 1..20 ]
				let l = [ 2.. ]
				let l = 1:2:3:5:7:[]
				let l = [ x*2 | x <- [1..100], x `mod` 3 == 0 ]
			

let 是 GHCi 的语法糖，在 hs 模块中直接使用 x = ? 即可。

List 运算

• map :: (a -> b) -> [a] -> [b]
• filter :: (a -> Bool) -> [a] -> [a]
• (++) :: [a] -> [a] -> [a]
• concat :: [[a]] -> [a]
• foldr :: (a -> b -> b) -> b -> [a] -> b

这些运算同样也可以应用在字符串上，还记得字符串是什么类型么？

模式匹配

Haskell 的模式匹配可不知比 Python/C#/ES6 高到哪里去了。

				factorial :: (Integral a) => a -> a
				factorial 0 = 1
				factorial n = n * factorial (n - 1)
			

匹配顺序从上往下。

模式匹配

列表和元组当然也可以

				let xs = [(1,3), (4,3), (2,4), (5,3), (5,6), (3,1)] 
				let xs = [a+b | (a,b) <- xs]
				let x:xs = [1,2,3,5,7] 
			

素数

一个无限长的素数数列

				primes = filterPrime [2..]
				  where filterPrime (p:xs) =
				    p : filterPrime [x | x <- xs, x `mod` p /= 0]
			

takeWhile (<100) primes 取出小于 100 的素数

素数

				primes = filterPrime [2..]
				  where filterPrime (p:xs) =
				    p : filterPrime [x | x <- xs, x `mod` p /= 0]
			

• filterPrime [ x | x <- [3..], x `mod` 2 /= 0 ]
• filterPrime [ x | x <- [4..], x `mod` 3 /= 0 ]
• filterPrime [ x | x <- [ x | x <- [3..], x `mod` 2 /= 0 ], x `mod` 3 /= 0 ]

递归

• 许多问题都适用递归定义
• 注意函数绑定的变量
• 注意惰性求值

Monad (单子)

Monad

• 在纯函数语言上实现副作用所进行的抽象

				class Applicative m => Monad (m :: * -> *) where
				  (>>=) :: m a -> (a -> m b) -> m b
				  (>>) :: m a -> m b -> m b
				  return :: a -> m a
				  fail :: String -> m a
				  	-- Defined in ‘GHC.Base’
			

Continuation-passing Style

对 CPS 代码进行 Currying 我们可以得到与 (>>=) 操作符等价的定义。 不难发现 Monad 和 CPS 变换是同构的。

(>>=) :: m a -> (a -> m b) -> m b

Monad 语法糖 — Do Notation

				readFile :: FilePath -> IO [Char]
				writeFile :: FilePath -> String -> IO ()
				main = do
				    s <- readFile "test.txt"
				    writeFile "test.txt" ("23333" ++ s)
			

缺了什么

• 高阶类型系统和类型类
• Kind 系统
• IO 系统
• Applicative/Functor
• STM/Semaphore
• ...

学习资料

• Learn You a Haskell for Great Good!
• Functors, Applicatives, And Monads In Pictures
• A Tutorial Introduction to the Lambda Calculus