Haskell

Table of Contents

1 Haskell简介

Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. The first version of Haskell ("Haskell 1.0") was defined in 1990.

参考:
Haskell Website: https://www.haskell.org/
Haskell 2010 Language Report: https://www.haskell.org/onlinereport/haskell2010/
Haskell 2010 Language Report (pdf): https://www.haskell.org/definition/haskell2010.pdf
Haskell Documentation: https://www.haskell.org/documentation
Programming in Haskell(较好的入门书籍,本文很多内容摘自于此书)
Real World Haskell: http://book.realworldhaskell.org/read/
Real World Haskell 中文版:http://cnhaskell.com/
Learn You a Haskell for Great Good!: http://learnyouahaskell.com/chapters

1.1 Haskell编译器GHC

GHC (Glasgow Haskell Compiler) 是开源的Haskell编译器。GHC起源于英国的格拉斯哥大学(University of Glasgow)。

GHC主要包含下面命令行工具:

Table 1: Glasgow Haskell Compiler主要包含的命令行工具
命令行工具 描述
ghc An optimizing compiler that generates fast native code
ghci An interactive interpreter and debugger
runghc (runhaskell) A program for running Haskell programs as scripts, without needing to compile them first

1.1.1 初次使用ghci

ghci 是个交互式的Haskell环境。下面是一些简单测试:

$ ghci
GHCi, version 7.8.4: http://www.haskell.org/ghc/  :? for help
Prelude> 1+2
3
Prelude> 4*5
20
Prelude> (2+3)*4
20
Prelude> 7 / 2
3.5
Prelude> 7 `div` 2       -- same as “div 7 2”
3
Prelude> 7 `mod` 2       -- same as “mod 7 2”
1
Prelude> sum [1, 2, 3, 4]
10
Prelude> sqrt 2
1.4142135623730951
Prelude> "Hello" ++ " Haskell"
"Hello Haskell"
Prelude> print "Hello Haskell"
"Hello Haskell"

1.1.2 GHCi提示符中常用命令

下面是GHCi提示符中常用命令,更多命令可输入 :? 或者参考 GHCi commands

Table 2: ghci提示符中常用命令
Command Meaning
:load file1 load script file1
:reload reload current script
:set editor name set editor to name
:edit file1 edit script file1
:edit edit current script
:type expr show type of expr
:info name display information about the given name
:? show all commands
:quit :quit GHCi

注:上面命令可以使用简写,如 :l file1 相当于 :load file1 ,其它类似。

1.2 Hello world程序

Haskell程序的入口程序是Main模块的main函数。

下面是Hello world程序(假设文件名为hello-world.hs):

main = putStrLn "Hello world"

执行方式一:使用 ghc 把它编译为二进制可执行程序后,再执行。

$ ghc hello-world.hs -o hello-world
[1 of 1] Compiling Main             ( hello-world.hs, hello-world.o )
Linking hello-world ...
$ ./hello-world
Hello world

执行方式二:使用 runghc 直接执行它。

$ runghc hello-world.hs
Hello world

1.3 程序文件结构

Haskell程序可保存到文件(一般使用.hs后缀)中。

假设文件test.hs的内容为:

double x = x + x              -- 定义了名为double的函数

ghci 后接文件名,可以加载文件内容到Haskell交互式环境中(也可以启动交互式环境后使用 :load 命令加载文件)。如:

$ ghci test.hs
GHCi, version 7.8.4: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, modules loaded: Main.
*Main> double 3
6

如果文件test.hs修改了,可以通过在GHCi提示符中输入 :reload 命令来重新加载文件。

1.3.1 Program Structure

The abstract syntactic and semantic structure of Haskell:
(1) At the topmost level a Haskell program is a set of modules. Modules provide a way to control namespaces and to re-use software in large programs.
(2) The top level of a module consists of a collection of declarations, of which there are several kinds. Declarations define things such as ordinary values, datatypes, type classes, and fixity information.
(3) At the next lower level are expressions. An expression denotes a value and has a static type; expressions are at the heart of Haskell programming “in the small.”
(4) At the bottom level is Haskell’s lexical structure. The lexical structure captures the concrete representation of Haskell programs in text files.

参考:https://www.haskell.org/onlinereport/haskell2010/haskellch1.html

1.3.2 注释

-- 开始的内容是单行注释。不过,如果 -- 是一个合法词法token的一部分,则不是注释。比如 --foo 是注释,而 --> 或者 |-- 都不是注释。
{--} 之间的内容是多行注释。

1.3.3 标识符

An identifier consists of a letter followed by zero or more letters, digits, underscores, and single quotes.

Identifiers are lexically distinguished into two namespaces: those that begin with a lowercase letter (variable identifiers) and those that begin with an upper-case letter (constructor identifiers).

标记符首字母为小写时称为“variable identifiers”,首字母为大写时称为“constructor identifiers”。如:

fun1 x = 2 * x           -- 定义函数,函数名必须是小写字母开头
type Pos = (Int, Int)    -- 定义类型,类型名必须是大写字母开头

参考:https://www.haskell.org/onlinereport/haskell2010/haskellch2.html#x7-180002.4

1.3.3.1 Reserved Identifiers
reservedid  →	case | class | data | default | deriving | do | else
            |	foreign | if | import | in | infix | infixl
            |	infixr | instance | let | module | newtype | of
            |	then | type | where | _

1.3.4 缩进

在Haskell中,缩进是重要的,同一层次的东西必须要有相同的缩进。图 1 是一些例子,演示了错误和正确的缩进。

haskell_indent.jpg

Figure 1: Haskell中一些错误和正确的缩进

可以用大括号把把一组语句括起来,语句之间用分号 ; 隔开,这时缩进无关紧要(不推荐这么做,因为这样代码很难看)。
比如:

a = b + c
    where
       b = 1
       c = 2
d = a * 2

又可以写为:

a = b + c
    where
       {b = 1;
        c = 2}
d = a * 2

还可以写为一行:

a = b + c where {b = 1; c = 2}; d = a * 2

参考:https://en.wikibooks.org/wiki/Haskell/Indentation

1.4 函数调用风格

Haskell是函数式语言。函数在Haskell中占据非常重要的位置,不过,函数调用的风格和数学中函数的调用是有差异的。见表 3 所示。

Table 3: 数学中和Haskell中函数调用风格的差异
Mathematics Haskell
\(f(x)\) f x
\(f(x, y)\) f x y
\(f(g(x))\) f (g x)
\(f(x, g(x))\) f x (g y)
\(f(x) g(y)\) f x * g y

2 Types and classes

2.1 Types基本概念

A type is a collection of related values.

Haskell是“静态类型”的语言,表达式的类型在编译阶段就已经确定了。 这使得代码更加安全,比如你尝试对字符串进行除法运算时,编译器会拒绝这样的代码。
Haskell具有强大的“类型推导”系统,你往往可以省略类型的声明,编译器自己会推导出具体类型。

2.1.1 查看类型(:type)

在GHCi中,使用 :type expr 可以查看表达式的类型。如:

Prelude> :type True
True :: Bool
Prelude> :type False
False :: Bool
Prelude> :type 'a'
'a' :: Char
Prelude> :type "abc"
"abc" :: [Char]
Prelude> :type 123
123 :: Num t => t

注:记号 v :: T 表示v具有类型T。
注:在程序中,可以使用模块 Data.Typeable 中的 typeOf 来得到表达式类型。

2.1.1.1 Type Signature (::)

符号 :: (后文将大量出现)表示Type Signature。如 v :: T 表示v具有类型T。

由于Haskell有类型推导系统,有时我们不用明确指定Type Signature。不过,指定Type Signature会使程序更加容易理解。

参考:https://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-800004.4

2.2 Basic types(Bool, Char, etc.)

4 是Haskell中的基本类型。

Table 4: Haskell中基本类型
类型 说明
Bool 包含逻辑值False和Ture
Char 单个字符,使用单引号包围,如'a', '3'
String 字符序列,使用双引号包围,如"abcd"
Int 整数,范围为 \(-2^{63}\) 到 \(2^{63}-1\)
Integer 可表示任意范围的整数
Float 单精度浮点数
Double 双精度浮点数

2.3 List types(元素类型相同)

Haskell中,List是“相同类型”元素组成的序列。List的格式为元素之间使用逗号分隔,所有元素用方括号包围。如 [False, False, True]

如果List的元素类型是T,则使用 [T] 表示该List的类型。如:

Prelude> :type [False, False, True]
[False, False, True] :: [Bool]
Prelude> :type ['a', 'b', 'c']
['a', 'b', 'c'] :: [Char]
Prelude> :type ["one", "two", "three"]
["one", "two", "three"] :: [[Char]]

List的长度可以是无限的。

2.4 Tuple types(元素类型可以不同)

Tuple是长度有限的元素序列,它的元素类型可以不相同。Tuple的格式为元素之间使用逗号分隔,所有元素用小括号包围。如 (False, 'a', True)

如果Tuple的元素类型分别为T1, T2, …, Tn,则使用 (T1, T2, ..., Tn) 表示该Tuple的类型。如:

Prelude> :type (False, 'a', True)
(False, 'a', True) :: (Bool, Char, Bool)
Prelude> :type (False, "Hello")
(False, "Hello") :: (Bool, [Char])

注:Tuple的长度必须是有限的,这样才可能推导出Tuple的具体类型。

2.5 Function types

函数是从参数到返回值的映射。

如果函数的参数类型为T1,返回值类型为T2,则使用 T1 -> T2 表示该函数的类型。如:

Prelude> :type not
not :: Bool -> Bool         -- 函数not的参数类型是Bool,返回值类型也是Bool

下面是接受Tuple为参数的函数的例子。

add       :: (Int, Int) -> Int   -- 声明函数类型
add (x,y) = x+y                  -- 定义函数add,它的参数是一个Tuple,返回值是Int

在交互环境中声明函数类型比较麻烦,你可以先保存到文件中,再使用 :load file1.hs 命令加载到交互环境中,再用 :type add 来查看其函数add的类型。
函数add的类型为 (Int,Int) -> Int ,表明它接收一个类型为 (Int, Int) 的参数(Tuple类型),返回值类型为Int。

上面介绍的函数类型,其参数个数都为1,下节将介绍参数个数大于1的函数的类型。

2.6 Curried functions

把接受多个参数的函数转换为接受单个参数的函数的过程,称为柯里化。Haskell支持自动柯里化。比如,你定义了一个函数 add' ,它接受2个参数。如:

add' x y = x + y     -- 这个函数(接受两个参数)和前面介绍的函数add(接受一个类型为Tuple的参数)不同

我们可以这样调用它: add' 1 2 (函数 add' 接受两个参数)。其实,我们还可以这样调用它: (add' 1) 2 ,这表明 (add' 1) 返回另外一个函数,这个函数接受一个参数。这就是Haskell的自动柯里化。

如何表示函数 add' 的类型呢?可以这样 Int -> Int -> Int ,它等同于 Int -> (Int -> Int)

下面是一个接受3个参数的函数的例子。

mult       :: Int -> Int -> Int -> Int    -- same as Int -> (Int -> (Int -> Int))
mult x y z = x*y*z

2.7 Polymorphic types

库函数 head 可以得到任何类型List的首个元素。如:

Prelude> head [1, 3, 5]
1
Prelude> head [True, False]
True

head 可接受任意类型的List,那如何表示它的类型呢?常用 [a] -> a 来表示 head 的类型,其中小写字母 a (也可使用其它小写字母,如 b, c 等等)表示“多种类型”,函数 head 称为Polymorphic function,其类型 [a] -> a 称为Polymorphic type.

又如, take 也是一个Polymorphic function,它的类型 Int -> [a] -> [a] 是Polymorphic type.

Prelude> take 4 [1, 3, 5, 7, 9]
[1,3,5,7]
Prelude> :type take
take :: Int -> [a] -> [a]

2.8 Overloaded types (=>)

我们知道,函数 abs 可以对数字类型求绝对值,其中数字类型可以是整数,还可以是单精度浮点数,双精度浮点数等等。

Prelude> abs (-1)
1
Prelude> abs (-2.5)
2.5

怎么表示函数 abs 的类型呢?写为Polymorphic类型 a -> a 是不够准确的,因为 abs 接受的类型仅仅是数字类型。

函数 abs 的类型可记为 Num a => a -> a (可以通过 :type abs 来验证)。 符号 => 前面的内容 Num a 被称为class constraint,它的含义是“type a is an instance of the class Num”。 关于class Num ,下节将介绍。

函数 abs 称为Overloaded function,其类型 Num a => a -> a 称为Overloaded type.

下面是其它一些Overloaded function:

Prelude> :type abs
abs :: Num a => a -> a
Prelude> :type negate
negate :: Num a => a -> a
Prelude> :type (*)
(*) :: Num a => a -> a -> a
Prelude> :type (+)
(+) :: Num a => a -> a -> a

2.9 Basic classes


上一节介绍了Class constraint,这里将介绍Class的概念。

Recall that a type is a collection of related values. Building upon this notion, a class is a collection of types that support certain overloaded operations called methods.

Table 5: Haskell basic classes
Class name Description Contains methods Instances
Eq equality types (==) :: a -> a -> Bool Bool, Char, String, Int, Integer, Float, Double, and List, Tuple
    (/=) :: a -> a -> Bool  
Ord ordered types (<) :: a -> a -> Bool Bool, Char, String, Int, Integer, Float, Double, adn List, Tuple
    (<=) :: a -> a -> Bool  
    (>) :: a -> a -> Bool  
    (>=) :: a -> a -> Bool  
    min :: a -> a -> a  
    max :: a -> a -> a  
Show showable types show :: a -> String Bool, Char, String, Int, Integer, Float, Double, and List, Tuple
Read readable types read :: String -> a Bool, Char, String, Int, Integer, Float, Double, and List, Tuple
Num numeric types (+) :: a -> a -> a Int, Integer, Float, Double
    (-) :: a -> a -> a  
    (*) :: a -> a -> a  
    negate :: a -> a  
    abs :: a -> a  
    signum :: a -> a  
Integral integral types (+) :: a -> a -> a Int, Integer
    (-) :: a -> a -> a  
    (*) :: a -> a -> a  
    negate :: a -> a  
    abs :: a -> a  
    signum :: a -> a  
    div :: a -> a -> a  
    mod :: a -> a -> a  
Fractional fractional types (+) :: a -> a -> a Float, Double
    (-) :: a -> a -> a  
    (*) :: a -> a -> a  
    negate :: a -> a  
    abs :: a -> a  
    signum :: a -> a  
    (/) :: a -> a -> a  
    recip :: a -> a  

测试method类型时,会显示对应的class名字。如:

Prelude> :type (==)
(==) :: Eq a => a -> a -> Bool
Prelude> :type (<)
(<) :: Ord a => a -> a -> Bool
Prelude> :type show
show :: Show a => a -> String
Prelude> :type read
read :: Read a => String -> a
Prelude> :type negate
negate :: Num a => a -> a
Prelude> :type div
div :: Integral a => a -> a -> a
Prelude> :type (/)
(/) :: Fractional a => a -> a -> a

下面是使用method的一些测试:

Prelude> [1, 2] == [1, 2]       -- 判断是否相等
True
Prelude> 1 /= 2                 -- 判断是否不相等,Haskell中“不等于”用 /= 表示
True
Prelude> show False
"False"
Prelude> show 123
"123"
Prelude> read "False" :: Bool
False
Prelude> recip 3                -- 取倒数
0.3333333333333333

3 Defining functions

Haskell中有很多方式可以定义函数,后文将介绍各种定义函数的方式。

3.1 New from old

定义函数最直接的办法是借助于已经存在的函数。

例如,定义测试偶数的函数:

even   :: Integral a => a -> Bool
even n = n `mod` 2 == 0

3.2 Conditional expressions (if … then .. else …)

通过 if ... then .. else ... 是定义函数的常用方式。

例如,内置函数 abs 可以像下面这样定义:

abs   :: Int -> Int
abs n = if n >= 0 then n else -n

if ... then .. else ... 可以嵌套使用。例如,内置函数 signum 可以像下面这样定义:

signum   :: Int -> Int
signum n = if n < 0 then -1 else
               if n == 0 then 0 else 1

注:和其它语言不同, if ... then .. else ... 中的 else 部分是不可以省略了,这样避免了“dangling else”问题。

3.3 Guarded equations (|)

Haskell中函数还可以通过“一系列逻辑表达式”来定义(这些逻辑表达式被称为Guards)。如果第一个逻辑表达式成立,则采用第一个逻辑表达式后面关联的定义;如果第二个逻辑表达式成立,则采用第二个逻辑表达式后面关联的定义;依此类推。

例如,内置函数 abs 可以像下面这样定义:

abs n | n ≥ 0 = n
      | otherwise = −n         -- 也可写为 True = -n ,不过 otherwise 更容易阅读

其中,符号 | 可理解为“such that”, otherwise 在内置库中被定义为 True

内置函数 signum 可以像下面这样定义:

signum n | n < 0 = −1
         | n == 0 = 0
         | otherwise = 1

3.4 Pattern matching

定义函数时,我们可以拆分函数主体为几个pattern,然后分别对pattern进行定义。

比如,使用Pattern matching,函数 not 可以这样定义:

not :: Bool -> Bool
not False = True
not True  = False

又如,使用Pattern matching,我们可以这样定义函数 intToWeekdayName ,它把数字转换为星期:

intToWeekdayName :: (Integral a) => a -> String
intToWeekdayName 1 = "Monday"
intToWeekdayName 2 = "Tuesday"
intToWeekdayName 3 = "Wednesday"
intToWeekdayName 4 = "Thursday"
intToWeekdayName 5 = "Friday"
intToWeekdayName 6 = "Friday"
intToWeekdayName 7 = "Sunday"

又如,使用Pattern matching,函数 factorial 可以这样定义:

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

下面的例子演示了使用Pathern matching来定义操作符 &&

(&&) :: Bool -> Bool -> Bool
True && True   = True
True && False  = False
False && True  = False
False && False = False

不过,上面 && 的定义可以简化为:

(&&) :: Bool -> Bool -> Bool
True && True   = True
_ && _         = False

其中,下划线 _ 称为“wildcard pattern”,它能匹配任意值。 && 还可以定义为下面形式:

(&&) :: Bool -> Bool -> Bool
True && b   = b         -- if the first argument is True, then the result is the value of the second argument
False && _  = False     -- if the first argument is False, then the result is False

3.4.1 Tuple patterns

下面是Tuple pattern的几个例子:

first :: (a, b, c) -> a
first (x, _, _) = x

second :: (a, b, c) -> b
second (_, y, _) = y

third :: (a, b, c) -> c
third (_, _, z) = z

3.4.2 List patterns (cons operator :)

下面是List patterns的例子,当函数 startWithA 的参数是长度为3的字符串,且首字符为'a'时返回 True ,其它情况返回 False

startWithA :: [Char] -> Bool
startWithA ['a', _, _] = True
startWithA _           = False

怎么增强函数 startWithA ,使它接受任意长度字符串为参数,且仅当其以'a'开头时返回 True 呢?

首先,我们介绍一下cons operator : 的概念。
Haskell中,List是由cons操作符 : 构造出来的。 : 的左操作符为一个元素,右操作符为List。比如: [1] 由数字1和空列表经 : 操作后构成,即有 [1] == 1:[] ,类似地,有 [1, 2, 3] == 1 : [2, 3] == 1 : (2 : [3]) == 1 : (2 : (3 : []))

了解了cons操作符 : 的概念后,容易增强函数 startWithA 以满足前面的要求了。

startWithA :: [Char] -> Bool
startWithA ('a':_) = True
startWithA _       = False

3.5 Case expressions (case … of …)

Case表达式语法如下:

case expression of pattern -> result
                   pattern -> result
                   pattern -> result
                   ...

用Case表达式可以定义函数。如:

head' :: [a] -> a
head' xs = case xs of []    -> error "No head for empty lists!"
                      (x:_) -> x

上面的定义也可用“Pattern matching”来实现:

head' :: [a] -> a
head' []    = error "No head for empty lists!"
head' (x:_) = x

可以认为“Pattern matching”是“Case expressions”的语法糖。

3.6 Lambda expressions (\)

Lambda expressions就是匿名函数。

比如,接受一个数字 x 为参数,返回 x + x 的匿名函数可表示为: \x -> x + x 。测试如下:

Prelude> (\x -> x + x) 3
6

我们知道,函数 add 可定义为:

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

如果使用Lambda表达式,则又可定义为:

add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)

仅被引用一次的函数很多时间没必要给它取名字,这时往往改写为匿名函数。比如:

odds :: Int -> [Int]
odds n = map f [0..n-1]             -- map 是内置库函数,它的第一个参数是函数,第二个参数是列表。函数 f 的定义在下一行
             where f x = x*2 + 1    -- where 表示后面的函数 f 是局部定义的

上面函数 odds 中定义的局部函数 f 仅被引用了一次,可以直接把它改写为Lambda expressions(匿名函数)。

odds :: Int -> [Int]
odds n = map (\x -> x*2 + 1) [0..n-1]

3.7 Operator sections

如果一个函数(如 + )在调用时,函数名写在它的两个参数之间,则把它称为“操作符”。

任何具有两个参数的函数,其调用形式都可以转换为“操作符”调用形式。转换方法是把函数名用一对反引用括起来(如 `funName` )。 例如:

Prelude> div 5 2       -- 函数调用形式
2
Prelude> 5 `div` 2     -- 操作符调用形式
2

相反地,任何操作符也可以转换为函数的调用形式。转换方法是把操作符用一对小括号括起来。 例如:

Prelude> 3 + 4         -- 操作符调用形式
7
Prelude> (+) 3 4       -- 函数调用形式
7

在Haskell中, (+) 3 4 还可以写为 (3+) 4 或者 (+4) 3 的形式。它们的前部分,即 (3+)(+4) 都被称为section。

一般地,如果 # 是操作符,下面三个形式被称为operator section:

(#)          -- 等同于 \x -> (\y -> x # y)
(x #)        -- 这称为left section,等同于 \y -> x # y
(# y)        -- 这称为right section,等同于 \x -> x # y

下面是section的一些例子:

Table 6: Section examples
section equivalent to
(+) \x -> (\y -> x+y)
(1+) \x -> 1 + x
(+1) \x -> x + 1
(2^) \x -> 2 ^ x
(^2) \x -> x ^ 2
('\t':) \x -> '\t' : x

4 List comrehensions (<-)

在数学的集合理论中,Comrehension可以用来基于存在的集合构造新的集合。比如 Comrehension \(\{ x^2 \mid x \in \{1..5\}\}\) 可以用来产生集合 \(\{1, 4, 9, 16, 25 \}\) 。

类似地,在Haskell中,List comrehensions可以用来基于存在的List构造新的List,其语法和数学中的Comrehension很相似。比如:

Prelude> [ x^2 | x <- [1..5]]
[1,4,9,16,25]

其中,符号 | 可以读做“such that”,符号 <- 可以读做“is drawn from”,而表达式 x <- [1..5] 被称为“generator”。

在一个List comrehension中可以使用多个“generator”。比如:

Prelude> [(x,y) | x <- [1,2,3], y <- [4,5]]          -- two generators
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]                -- 后面的(第二个)generator在结果中变化更快

注意,如果存在多个“generator”,则“generator”的顺序不同会得到不同的新列表。比如:

Prelude> [(x,y) | y <- [4,5], x <- [1,2,3]]          -- 顺序和前面不同,得到的列表也不同
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]                -- 后面的(第二个)generator在结果中变化更快

后面的generator可以引用了前面generator中的变量。比如:

Prelude> [(x,y) | x <- [1..3], y <- [x..3]]          -- 后面的(第二个)generator引用了前面(第一个)generator中的变量(x)
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]

下面是内置函数 concat 的一个实现:

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]                -- 第二个generator引用了第一个generator中的变量

concat 的使用实例:

Prelude> concat [ [1, 2, 3], [4, 5], [6, 7] ]
[1,2,3,4,5,6,7]

wildcard pattern _ 可以用在generator中。比如下面是内置函数 length 的一个实现:

length :: [a] -> Int
length xs = sum [1 | _ <- xs]

4.1 Guards

可以使用逻辑表达式(被称为Guards)对生成的结果进行过滤。比如:List comrehension [x | x <- [1..10], even x] 得到的结果为 [2,4,6,8,10]

4.2 String comprehensions

字符串其实就是字符列表。比如 "abc"['a','b','c'] 是一回事。前面介绍的List comprehensions也适应于字符串。比如:

Prelude> [x | x <- "abc123XYZd", x >= 'a' && x <= 'z']      -- 用Guards过滤了非小写字母
"abcd"

下面是利用String comprehensions定义函数的两个例子:

lowers :: String -> Int
lowers xs = length [x | x <- xs, x >= 'a' && x <= 'z']     -- 返回字符串中小写字母的数量

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']               -- 返回字符串中包含指定字符的数量

5 Higher-order functions

由于Haskell支持自动柯里化。接收多个参数的函数,都可以返回另外一个函数。

假设有下面定义:

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

如, (add 2) 返回另外一个函数。可以这样调用这个函数: (add 2) 3 ,它的结果为 5

函数不仅可以返回另一个函数,还可以接收另一个函数为参数。

当一个函数接收另一个函数作为参数,或者返回另外一个函数作为结果时,这个函数可以称为“高阶函数”。

5.1 一些列表处理高阶函数

内置函数 map 是一个常用的高阶函数。它的第一个参数是另一个函数,第二个参数是一个列表,返回的结果是对列表(第二个参数指定)中每个元素应用函数(第一个参数指定)后组成的新列表。

下面是 map 的一个实现:

map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]

下面是 map 的一个使用实例:

Prelude> map (+1) [1,3,5,7]
[2,4,6,8]
Prelude> map even [1,2,3,4]
[False,True,False,True]
Prelude> map reverse ["abc","def","ghi"]
["cba","fed","ihg"]

下面是函数 map 的另外一个实现(利用递归调用):

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

7 是一些内置的列表处理高阶函数。

Table 7: 一些内置的列表处理高阶函数
函数名 实例
map map even [1..4] 得到 [False, True, False, True]
filter filter even [1..10] 得到 [2, 4, 6, 8, 10]
all all even [2,4,6,8] 得到 True
any any even [2,3,4] 得到 True,any odd [2,3,4] 也得到 True
takeWhile takeWhile even [2,4,7,8,10] 得到 [2,4]
dropWhile dropWhile odd [1,3,5,6,7,8] 得到 [6,7,8]

5.2 函数 foldr

先观察几个函数的定义:

sum [] = 0
sum (x:xs) = x + sum xs

or [] = False
or (x:xs) = x || or xs

and [] = True
and (x:xs) = x && and xs

下面是 sum [1, 2, 3, 4] 的计算过程:

sum [1, 2, 3, 4]
= sum 1 + (2 + (3 + (4 + 0)))
= sum 1 + (2 + (3 + 4))
= sum 1 + (2 + 7)
= sum 1 + 9
= 10

前面这些函数都有共同的处理模式,可以抽象为下面的形式:

f [] = 0
f (x:xs) = x # f xs

内置的高阶函数 foldr (是“fold right”的缩写)封装了上面的模式。使用 foldr 可以更方便地定义 sum/or/and 等函数。如:

sum :: Num a => [a] -> a
sum = foldr (+) 0

or :: [Bool] -> Bool
or = foldr (||) False

and :: [Bool] -> Bool
and = foldr (&&) True

下面是函数 foldr 的一个实现:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

foldr (+) 0 [1,2,3] 可以得到 1 + (2 + (3 + 0)) 。下面总结了 foldr 的行为:

foldr (#) v [x0, x1, ..., xn] = x0 # (x1 # (... (xn # v) ...))

5.3 函数 foldl

高阶函数 foldlfoldr 类似,不过它是左结合性的。下面是 foldl 的行为:

foldl (#) v [x0,x1,...,xn] = (... ((v # x0) # x1) ...) # xn

下面是函数 foldl 的一个实现:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

sum/or/and 等函数除了用 foldr 定义外,还可以使用 foldl 定义。如:

sum :: Num a => [a] -> a
sum = foldl (+) 0

or :: [Bool] -> Bool
or = foldl (||) False

and :: [Bool] -> Bool
and = foldl (&&) True

采用上面定义时, sum [1, 2, 3, 4] 的计算过程如下:

sum [1, 2, 3, 4]
= sum ((((0 + 1) + 2) + 3) + 4)
= sum (((1 + 2) + 3) + 4)
= sum ((3 + 3) + 4)
= sum (6+ 4)
= 10

5.4 操作符 $

操作符 $ 被称为“function application operator”,它的定义如下:

($) :: (a -> b) -> a -> b
f $ x = f x

从定义上看,操作符 $ 仅仅是应用一个函数。那它有什么用呢?

由于操作符 $ 具有最低优先级,我们往往使用操作符 $ 来去掉代码中的一些括号。 比如: sqrt (3 + 4 + 9) 可以写为 sqrt $ 3 + 4 + 9 ,又如 sum (map sqrt [1..130]) 可以写为 sum $ map sqrt [1..130]

此外,操作符 $ 具有右结合性,也就是说 f $ g $ xf $ (g $ x) 相等。所以下面三行代码是相同的:

sum (filter (> 10) (map (*2) [2..10]))
sum $ filter (> 10) (map (*2) [2..10])      -- 利用 $ 去掉了一对括号
sum $ filter (> 10) $ map (*2) [2..10]      -- 利用 $ 去掉了两对括号

5.5 The composition operator (.)

内置高阶操作符 . 的左/右操作数都是函数,其返回的结果也是函数。下面是它的一个实现:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

f . g 读作“f composed with g”,它是接收一个参数的函数。首先把 g 应用它的参数,然后把 f 应用于上一步的结果。也就是说,它还可以定义为 (f . g) x = f (g x) 不过,之前的定义 f . g = \x -> f (g x) 更易理解,因为它明确地表示了 f . g 的结果是一个函数。

操作符 . 具备结合性,即有: f . (g . h) = (f . g) . h

利用 . 可以简化一些函数的定义。如:

odd n = not (even n)
twice f x = f (f x)
sumsqreven ns = sum (map (^2) (filter even ns))

利用 . 可以把上面的定义简化为:

odd = not . even
twice f = f . f
sumsqreven = sum . map (^2) . filter even

6 Declaring types and classes

6.1 Type declarations (type)

定义type最简单的办法是基于已有的type。比如:

type String = [Char]               -- type名(String)必须以大写字母开头

又如:

type Pos = (Int,Int)
type Trans = Pos -> Pos

6.2 Data declarations (data)

A type is a collection of related values. 可以使用 data 为type指定相关的值。如:

data Bool = False | True           -- type的值(False或True)也必须以大写字母开头

6.3 Newtype declarations (newtype)

使用 newtype 可以定义全新的type。如定义一个非负数:

newtype Nat = N Int

当然,我们可以这样定义非负数 Nat

type Nat = Int
data Nat = N Int

不过,“采用 newtype 定义非负数 Nat ”比“采用 type 基于已有type定义非负数 Nat ”要更加安全。因为,如果采用 newtype 定义非负数 Nat ,则当程序期待非负数 Nat 时,你不能传递一个 Int

6.4 Class and instance declarations (class, instance)

2.9 介绍了一些基本的class,这节介绍如何定义新的class。

一个新的class可以使用 class 来定义。如内置class Eq 可以这样定义:

class Eq a  where
    (==), (/=)       :: a -> a -> Bool   -- 这里说明 class Eq 必须定义两个方法: == 和 /=
    x /= y           =  not (x == y)     -- 这里是 default definition,这样Eq的实例只需要定义 == ,而无需定义 /= 了

使用 instance 可以定义class的实例。如type Bool 可以这样定义:

instance Eq Bool where
    False == False = True
    True  == True  = True
    _     == _     = False

参考:https://www.haskell.org/tutorial/classes.html

6.4.1 Extend to new class (=>)

class可以扩展为一个新class。比如,内置class Ord 可看作是class Eq 的扩展。

内置class Ord 可以这样定义:

class Eq a => Ord a where
    (<), (<=), (>), (>=) :: a -> a -> Bool
    min, max             :: a -> a -> a

    min x y | x <= y     = x        -- default definition
            | otherwise  = y

    max x y | x <= y     = y        -- default definition
            | otherwise  = x

class Ord 的实例必须实现上面6个方法,不过 minmax 已经存在于default definition中,所以class Ord 的实例只需定义其它4个方法。

下面演示了如何定义type Bool 为class Ord 实例:

instance Ord Bool where
    False < True = True
    _ < _        = False
    b <= c       = (b < c) || (b == c)
    b > c        = c < b
    b >= c       = c <= b

6.4.2 Derived instances (deriving)

在创建type时,可以在值构造子后面加上 deriving (Eq,Ord,Show,...) ,来给创建的type添加接口。如:

data Bool = False | True
            deriving (Eq, Ord, Show, Read)

7 Input and Output

Haskell是一个纯粹函数式语言。函数唯一可以做的事是根据我们给定的参数来算出结果。函数是无副作用的,如果我们用同样的参数调用两次同一个函数,它会返回相同的结果。不过,事情没有这么完美。真实世界中,我们不得不接触“外部世界”,比如键盘、屏幕、文件等等,这些I/O相关操作。

下面是一个简单的I/O相关程序:

main = do
    putStrLn "Greetings!  What is your name?"
    inpStr <- getLine
    putStrLn ("Welcome to Haskell, " ++ inpStr ++ "!")

函数 getLine 从标准输入读取一行。 运算符 <- 是用来从I/O action中抽出结果,并且保存到一个变量中(这里是inpStr)。

上面程序测试运行如下:

$ runghc test.hs
Greetings!  What is your name?
John
Welcome to Haskell, John!

我们来看一下 getLineputStrLn 的类型:

Prelude> :type getLine
getLine :: IO String
Prelude> :type putStrLn
putStrLn :: String -> IO ()

8 是一些有用的I/O函数。

Table 8: 一些有用的I/O函数
I/O函数 描述
putStr 打印字符串到终端
putStrLn 打印字符串到终端,外加一个换行符
putChar 打印一个字符到终端
print 相当于 putStrLn . show ,任何 Show 类型的实例都可以通过它打印出来

8 Monoids

模块 Data.Monoid 中定义了 Monoid class,代码如下:

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty     -- default definition/implementation,所以这个方法用户可不实现

下面一一介绍 Monoid 实例所必须实现的3个方法。
(1) mempty ,它不接受任何参数,所以它并不是一个函数,而是一个polymorphic的常数, mempty 表示特定monoid的“identity value”。后面会介绍 List 是一种Monoid,它的 mempty 为空列表 []
(2) mappend ,它是接受两个相同类型参数的函数,且会返回同样的类型。名字“mappend”取得不好,单从名字上看,应该是添加两个东西到一起变成同类型的另一个东西。不过,你不要被这个函数的名字误导,只要满足这个函数的Type Signature(即 m -> m -> m )都可以是 mappend 。后面会介绍 Listmappend 为操作符 ++
(3) mconcat ,它有默认的实现,一般情况下,你不用重新实现它。

8.1 The Monoid Laws

下面三个要求称为Monoid Laws:
(1) mempty `mappend` x = x
(2) x `mappend` mempty = x
(3) (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z) ,即 mappend 遵守结合律。

注1:Haskell不会强制检查这些定律是否被遵守。我们在定义Monoid的实例时必须自己遵守它们。
注2:Monoid来源于抽象代数中的 幺半群(Monoid)

8.2 Lists Are Monoids

ListMonoid 的实例,其代码如下:

instance Monoid [a] where
    mempty = []
    mappend = (++)

下面是一些基本测试:

Prelude> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
Prelude> mconcat [[1,2],[3,6],[9]]
[1,2,3,6,9]
Prelude> mempty :: [a]
[]

9 Monads

Monad class的定义如下:

class Monad m where
    return :: a -> m a

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

    (>>) :: m a -> m b -> m b
    x >> y = x >>= \_ -> y         -- 这是 >> 的默认实现

    fail :: String -> m a
    fail msg = error msg           -- 这是 fail 的默认实现

Monad class的实例需要实现4个方法,不过,其中两个方法(即 >>fail )已有默认实现。

参考:
https://wiki.haskell.org/Monad
https://www.haskell.org/tutorial/monads.html

10 Appendix

10.1 内置操作符的优先级和结合性

下表是Haskell中内置操作符的优先级和结合性。

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

参考:https://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-820004.4.2


Author: cig01

Created: <2016-01-01 Fri 00:00>

Last updated: <2017-12-25 Mon 12:14>

Creator: Emacs 25.3.1 (Org mode 9.1.4)