Haskell学习笔记

Channel 9上有个非常好的介绍Haskell和函数式编程的视频,这个视频是根据Programming in Haskell这本书讲述的。Slides和Codes可以在http://www.cs.nott.ac.uk/~pszgmh/上下载,不过后面几章会和实际的课程内容有出入。此外Learn You a Haskell上的教程,以及Wikipedia上有关Haskell的词条也是非常有用的。
相对于其他的一些Haskell的教程,通过这本书/视频进行学习能够了解Haskell的好处以及设计原理

Ch0

先吐槽一下教授的口音。。。

配置Haskell环境

使用sublime text 2,可能会出现一些问题

  1. Decode error - output not utf-8
    在Haskell.sublime-build里面把encoding改为cp936(也就是GBK)即可
  2. Not in scope
     Not in scope: main
     Perhaps you meant min (imported from Prelude)
    
    这是因为编译命令行默认调用runhaskell,它会自动调用main程序,所以把命令行改为ghci即可
    现在可以愉快地写Haskell啦
  3. end of file
     <stdin>: hGetLine: end of file
    
    这是Haskell的一个bug,参考StackOverflow上这篇回答

Ch1 Introduction

Haskell大法好!函数式大法好!

  1. 现代软件危机:
    1. 如何处理现代程序大小和复杂度问题
    2. 如何减少程序开发的时间和代价
    3. 如何提高程序可靠性
  2. 解决方案:
    1. 更清楚、简明、高度抽象的代码
    2. 可重用的组件
    3. 形式证明(formal verification)的使用
    4. rapid prototyping
  3. 函数式编程(functional language)
    是一种把函数应用到参数(application of function to arguments)作为基本运算的编程风格
  4. Alonzo Church:lambda演算
  5. John McCarthy:Lisp
  6. John Backus:FP,high-order functions and reasoning about program,类似于Linq
  7. Robin Milner:ML,type inference and polymorphic types
  8. Peter Landin:ISWIM,没有赋值的纯函数式编程语言
  9. David Turner:lazy evaluation
  10. SKI组合子演算(Haskell Curry等人提出)
  11. 一个非原地的快速排序,类似于Linq(where语句)或派通(Python,神奇的口音)一行版本的写法。

Ch2 First Steps

首先是讲了一堆Prelude大法好

列表处理

在Ch4中会看到部分函数,例如headtail是如何实现的

  1. 获取列表片段
    返回移除列表首元素的新列表,类似car

    1
    2
    > head [1,2,3,4,5]
    1

    返回移除列表首元素的新列表,类似cdr

    1
    2
    > tail [1,2,3,4,5]
    [2,3,4,5]

    返回移除列表前n个元素的新列表

    1
    2
    > drop 3 [1,2,3,4,5]
    [4,5]

    返回前n个元素组成的新列表

    1
    2
    > take 3 [1,2,3,4,5]
    [1,2,3]
  2. 返回列表第n个元素

    1
    2
    > [1,2,3,4,5] !! 2
    3
  3. 连接两个列表

    1
    2
    > [1,2] ++ [3,4]
    [1,2,3,4]
  4. 列表属性
    获得列表长度

    1
    2
    > length [1,2,3,4,5]
    5

    获得列表和/积

    1
    2
    > sum/product [1,2,3,4,5]
    15/120

    翻转列表

    1
    2
    > reverse [1,2,3,4,5]
    [5,4,3,2,1]
  5. 生成列表
    注意生成的是中括号区间

    1
    2
    > [1..5]
    [1,2,3,4,5]

    1
    > [1..]

    生成一个无尽的列表,类似python中的生成器count,不同于python,Haskell的实现是因为它是lazy evaluation的

  6. 判断元素属于列表

    1
    2
    > 1 `elem` [1..5]
    True

三种编程语言的比较

  • C#(OOP)

      [1,2,3].drop(3)         
      receiver.method(arguments)
    

    这里receiverarguments不是等价的参数,一切围绕receiver对象为基础

  • Haskell

      drop 3 [1,2,3]
      method receiver arguments
    

    这里receiverarguments是等价的参数,可以更方便地match每个参数的特定值

  • F#

      [1,2,3] -> drop 3
    

函数调用

  1. 使用空格而不是括号+逗号来分离函数名以及参数
  2. 函数调用比其他运算符,如+具有更高的优先级(毕竟你连括号都没有),因此比较好的书写习惯是,如果都是函数调用,需要把内层参数括起来
     Mathematics : f(g(x))
     Haskell     : f (g x)           
     Mathematics : f(x, g(y))
     Haskell     : f x (g y) 
     Mathematics : f(x + 1, y - 1)
     Haskell     : f (x + 1) (y - 1)
    
    这样写有最少的语法噪音
  3. $运算符
    $运算符实际上表示“应用”的意思。常常可以用来改变运算顺序,从而省略括号,它可以看做id函数对函数的特化
     id :: a -> a
     id x = x
     
     ($) :: (a -> b) -> a -> b -- ->是右结合的
     ($) :: (a -> b) -> (a -> b)
     ($) = id
    
    f $ g x,即($) f (g x),等价于f (g x)
    如果不加上$,那么gx都会被当成一个二元f的两个参数,可以参照下面的例子理解:
     Prelude> (+) 1 (+2) 1
     error
     
     Prelude> (+) 1 $ (+2) 1
     4
    

type class

这里的a称为类型参数,注意这里面的类型参数是静态的而不是动态的,编译器/解释器会自动进行类型推导a是什么的。如对于double函数

double :: Num a => a -> a

这里出现在=>符号前的Num a作用是给类型参数a加上类型约束,称为类型类,或type class、type/class constraint、context(?)。当有多个类型约束时,用小括号括起所有的类型约束。
虽然type class和type都是大写字母开头的,但两者是不一样的,type class通过class等语句定义,type根据typedata等语句定义。
type class类似于C#中的接口interface,在功能上也有点类似于C++中的concept

1
2
3
T quadruple<T> (T x) where T:INumeric<T>{
return double(double(x));
}

类型类通常通过class语句来定义,下面是一个最简单的示例

class BasicEq a where
    isEqual :: a -> a -> Bool
    isNotEqual :: a -> a -> Bool

有关类型类的更多细节会在Ch10探讨。

instance

然后我们可以用instance语句来创造这个类型类的实例类型(instance type),也就是a
首先我们需要区分几个类似的用法:
第一个是上面见到的函数定义中的Num a,这是type constraint,说明函数中的类型变量a应当满足给出的type class。
第二个是马上要见到的foldr中的t a,这是由一个type constructor产生的concrete type(简称type)。
下面的语句定义了一个Bool的类型,它实现了BasicEq的constraint或者说type class。

instance BasicEq Bool where
    isEqual True  True  = True
    isEqual False False = True
    isEqual _     _     = False
    isNotEqual True  True  = False
    isNotEqual False False = False
    isNotEqual _     _     = True

不过我们发现同时定义两个明显互补的函数是浪费而不美观的。Haskell中允许我们通过定义默认实现的方式来避免这个

class BasicEq a where
    isEqual :: a -> a -> Bool
    isEqual x y = not (isNotEqual x y)

    isNotEqual :: a -> a -> Bool
    isNotEqual x y = not (isEqual x y)

composition

我们可以通过double来定义一个四倍函数

quadruple x = double (double x)
double x = x + x    

更Haskell一点的方法,使用composition(fusion, pipe to)

quadruple = double . double
(f . g) x = f (g x)     

这里的.类似于数学里面的复合函数,可以写出它的签名

> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

例如

length = sum . map (\_ -> 1)

由于Haskell是lazy的,所以看到map时,并不立即计算map

.运算符和$运算符的比较

.运算符的作用是

(f . g) x
:: f (g x)

$运算符的作用是

f $ g x
:: f (g x)

看起来他们具有相同的作用,但实际上两者具有差别
.的作用实际上是生成一个新的函数,比如f . g是合法的,但是f $ g就不合法了。
$的作用实际上是消除一些括号,于是haskell不会像lisp一样骚。

将函数作为操作符

1
2
3
factorial n = product [1..n]
average ns = sum ns `div` length ns
main = print (average [1,2,3,4,5])

这里的div实际上是一个函数,加上`后变成了一个运算符,这称为gave accent或backquote,有点类似于fortran中的.op.运算符。相反地,可以在运算符两边加上小括号(op)将其作为柯里函数使用,称为prefix notation或者operator section,这将在后面讲到

:reload

Haskell使用:reload命令通知GHC重新加载hs文件

命名规则

  1. Haskell的函数或者参数名字必须以小写字母开头

  2. 类型名必须以大写字母开头

  3. 通常列表以s结尾

  4. layout rule
    为了省略大括号,Haskell并列语句不能随意缩进(对的游标卡尺),并且缩进只能用空格,而不能够用tab

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

    的大括号(explicit grouping)形式是

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

    再次说明Haskell消除了不必要的冗余语法

  5. 对Haskell缩进规则的补充
    如果写过Python,一定知道冒号后面要缩进,tab缩进和空格缩进是不同的,并且每个缩进的长度一定是与层级有关的,但是Haskell并不是。
    主要原因是Haskell不强制在“冒号”后面换行。例如在do语句中,如果按照Python的语言习惯,do后面就该直接换行了。但是Haskell可以将do结构里面的第一个语句写到do的同一行,这时候下一行的语句应当和第一个语句是并排的,例如

     putStrLn' xs = do    putStr xs
                          putChar '\n'
    

    注意putStrpputCharp是并排的,又比如

     f x = case x of 0 -> 18
                     1 -> 15
    

    这里面的01也是要对齐的
    但是如果我们偏偏在关键字处换行呢?那至少要缩进一个空格,例如

     putStrLn' xs = do
      putStr xs 
      putChar '\n'
    

     f x = case x of
      0 -> 18
      1 -> 15
    

Ch3 Types and Classes

表达式的类型

如果一个表达式e的计算得到类型是t的结果,那么称为e具有类型(has type)t,写作

e :: t      

由于Haskell是静态类型的(static typed),所以编译器能够通过类型推导(type inference)得到所有表达式的类型

:t或:type

使用:t:type可以获得参数的类型

Haskell的基本类型

 Bool          | 布尔                                                   
 Char          | 字符,字符直接量用单引号括起                           
 String        | 字符串,字符串直接量用单引号括起,也可以看做Char的List 
 Int           | 固定精度整数
 Integer       | 任意精度整数
 Float         | 浮点数
 [t]           | 类型t的列表
 (t1, ..., tn) | 元组

特别地,使用中括号括起数据生成列表时,中括号起到data constructor作用,括起类型生成列表类型时,中括号起到type constructor作用

函数的类型

函数也就是映射,Haskell中使用t1 -> t2表示函数将t1类型映射到t2类型
我们可以用type form去“声明”函数,这就是先前看到的e :: t这样的语法。
我们也可以使用value form直接来“定义”函数,我们还可以使用lambda表达式来定义一个函数,做法是在最前面加一个反斜杠,\x -> y
特别地,lambda表达式也可以拥有多个参数,可以写成\x y -> x + y
由此看出,由于Haskell的类型推导机制,函数的type form在具备value form是并不是强制的(但并不总是可以省略),这和C++等强制性声明函数类型(function type)是不一样的。当然在C++模板编程中可以推导部分参数的类型/返回值,但在编译器层面,每个重载/特化版本的函数签名也是确定的。
在实际书写Haskell程序时,先写一遍type form来限定来限定参数的类型、规定函数的签名写出来是一个非常好的习惯,这被称为类型驱动开发(Type Driven Development)。

unit

()称为unit,类似于void,会在monad中用到

柯里化

对于一个多元函数,例如div,设想它的类型是这样的

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

但实际上它的类型是这样的

> :t div
div :: Integral a => a -> a -> a

事实上这是因为add x y实际上接受一个参数a,并返回一个一元函数(闭包),这个函数的类型是a -> a。这个一元函数的作用是将自己的参数badd的参数a相加,这样的函数称为柯里函数
因此实际上div的类型是

div :: Integral a => a -> (a -> a)

注意到Haskell中的->符号是右结合的,因为柯里化是从左边开始的,所以可以省略括号写成a -> a -> a
使用lambda可以写为

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

多态函数

关于这一部分,在文末有专题讨论。
Haskell中的函数默认可以接受任意类型的参数,这称为Haskell的类型多态。但有时需要限定类型,例如sum函数,去接受一个Bool类型是没有意义的。因此我们需要引入另一种多态即Ad-hoc多态。Ad-hoc多态的实现是基于typeclass和class instance的。

typeclass

下面的语句为a提供typeclass为Num的类型约束

1
sum :: (Num a) => [a] -> a

如前面Ch2.5提到过的那样,typeclass类似于C#中interface而非class。不过相比interface,我们看到typeclass中可以定义具有ad-hoc多态类型的值的。此外我们也注意到其实Haskell中,值也可以看成一种特殊的函数:

1
2
3
class TypeClassWithValue t where 
plainValue :: t
functionValue :: t -> t

在typeclass中定义的函数也可以是类型多态或Ad-hoc多态的,例如典型的Monad

1
2
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b

这里的Monad是一个typeclass,m将来是可以用instance产生的实例(instance)类型,也是一个type constructor,类似C++中的模板,可以用来构造类型。而m a则是由type constructor产生的具体类型(concrete type)——这里概念有点乱的话是正常的,可先查看instancetype的相关章节——我们注意到实例m受到Ad-hoc多态的typeclass Monad的约束,但它自己确是类型多态的,因为它可以是任意的类型a

常用的typeclasse有

  • Eq:表示能判断相等的类型
    • Num:表示数字,不继承OrdNum没有(/)
      • Real:实数,继承了Ord
        • Integeral:整型
  • Ord:表示能比较大小的类型
    特别注意,Ordering是一个类型,包含GTLTEQ三个constructor
  • Show:可以被转成字符串的类型,Haskell中除了函数都能被表示成字符串
  • Read:可以从字符串被读取的类型
  • Enum:能被枚举的类型
  • Bounded:有界的类型
  • Fractional:具有除法的数字类型类(/)
    • Floating:浮点

Existential Quantification

作为拓展,必须介绍Existential Quantification这个Haskell类型系统中的重要概念,Haskell借助于此实现类似OOP中的多态。

Ch4 Defining Functions

if

Haskell中的if语句和其他语言的并无二致

if cond then exp1 else exp2

但是else分支是必须的,毕竟是强类型语言

guarded equations

这个名字还挺熟悉的,原来是在《程序设计语言原理?这本书上看到过,当时翻译成守卫。这里的guard指的是|符号,注意|在list comprehension另有用途。guarded equations是Haskell比较独特的一种表示条件分支的办法,有点类似于数学公式里面的条件,或者说其他语言中的select case的用法

abs n | n >= 0 = n
      | otherwise = -n

偏函数应用与部分函数

不同于Scala,Haskell中的部分函数,相对于全函数(total function)是不被鼓励的。部分函数类似于div(!!),它并不是对于指定类型的所有值都有定义。以head为例,它的参数是所有的列表,可是对于一个空列表应用head会抛出一个异常。

Prelude> head []
*** Exception: Prelude.head: empty list

在Haskell中,偏函数应用(partial application)和部分函数(partial function)是两个不同的概念。偏应用在随后会有介绍。

where语句

这里补充一下where,这是一个类似占位符placeholder的语句,让我们的代码更漂亮一点,同时能够在guard、do这样的结构中复用一些结果。

f x
  | cond1 x   = a
  | cond2 x   = g a
  | otherwise = f (h x a)
  where
    a = w x

可以看出来where的缩进应当与其所在的结构下属的语句相同,而不是与所在的结构平齐。并且where作为一个结构,其下属语句也需要缩进。
where也可以通过模式匹配来定义函数

fib = (map fib' [0 ..] !!)
    where
      fib' 0 = 0
      fib' 1 = 1
      fib' n = fib (n - 1) + fib (n - 2)

此外go惯用法里面也常用到where

where的作用域

根据stackoverflow上的这篇回答
对于下面的这个式子

someFunc x y | guard1 = blah1
             | guard2 = blah2
  where {assignments}

{assignments}域中只能够访问xy,但guard1guard2blah1blah2都能访问{assignments}

where存在的问题

一个不恰当的where语句会导致性能的降低,比较一下下面的两段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
-- 1
fib = (map fib' [0 ..] !!)
where
fib' 0 = 0
fib' 1 = 1
fib' n = fib (n - 1) + fib (n - 2)

-- 2
fib x = map fib' [0 ..] !! x
where
fib' 0 = 0
fib' 1 = 1
fib' n = fib (n - 1) + fib (n - 2)

这两种写法互为eta-conversion(η-conversion)。eta-conversion是lambda演算中的一种变换,指\x -> f xf这两种写法在语义上是等价的。
但实际上第一段代码要比第二段代码要快,这是因为第一段代码满足了Constant applicative form(CAF),因此编译器默认会进行优化,而对于第二段代码由于x不确定,所以对于每个x,编译器都要重新计算一遍fib'函数。
使用GHC的float-in/float-out能够进行优化。

where、let in与let的区别

首先let和前两者是非常不同的。

let..in..含义是在let和in之间可以包含多个表达式作为定义,辅助in后面的一个表达式,而in后面的表达式是整个let..in..的值。例如

1
g x = let {y = x + 1; z = y + 1} in z

g 1等于3。

pattern matching

模式匹配(pattern matching)可以用来进行解构绑定(deconstruction binding)
借助于Haskell的模式匹配还可以实现下面的写法。

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

这可以借助OOP中的虚函数(dynamic dispatch)实现,例如下面的C#伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Bool{
Bool Not();
}
class True : Bool{
Bool Not(){
return new False();
}
}
class False : Bool{
Bool Not(){
return new True();
}
}

特别地,下划线_表示可以匹配任何参数,称为wildcard。例如

True && b = b
False && _ = False

lazy evaluation

lazy evaluation相对于eager evaluation有相当的好处,阐明这点将贯穿整个课程,这里讲了一个比较具体的例子

f x = 4711

于是可以有下面的求值方案,这里X是某个任意值

f(True && X)
= f(X)
= 4711

这样的好处是避免了对X的求值(注意这里X没有被逻辑与短路),因为X可能是不可计算的:假如定义并求值X = X或者X = head [],那程序是不能终止(non-terminating)的,在Haskell中是通常的一种错误(Error)形式。但是f(X)是可以计算的。采用eager evaluation的大多数其他语言会在True && X表达式时就对X求值,而这时会造成问题的。
此外,lazy evaluation无论对于什么样的求值顺序结果都是不变的,这是由于Haskell语言本身(除了Monad)不会造成副作用。例如对于上面的例子可以直接根据f x = 4711归约

f(True && X) = 4711
    

pattern具有优先级

对于这个例子中,值永远是False,因为第一个规则的优先级更高

_ && _ = False
True && True = True

所以我们在写规则的时候,会把更特化的规则写在面,这是非常需要重视的一点。

重复的名字不能出现在pattern中

此外还需要注意重复的名字(patterns may not repeat variables),例如下面的代码是错误的

b && b = True

会输出错误

? Conflicting definitions for ‘b’
Bound at: F:\Codes\Haskell\3.hs:2:1
        F:\Codes\Haskell\3.hs:2:6
? In an equation for ‘Main.&&’

这是为什么呢?
其实这样的东西称为nonlinear pattern。理想情况下,我们希望通过使用同一个字符b来限定&&的左操作数和右操作数是相等的。但是这是不可能实现的,因为当左右操作数出现lambda时,是没有一个统一标准判断lambda是否相等的

list pattern和:

运算符:(cons)可以构造列表,下面的第一行代码称为list constructor,我们常喜欢用的第二行可以看做第一行的语法糖。

1:(2:(3:[]))
[1,2,3]

然而它还可以用在pattern matching中,例如实现headtail

head :: [a] -> a
head (x:_) = x
tail :: [a] -> [a]
tail (_:xs) = xs

注意点:

  1. x:xs去pattern matching空list是未定义行为
  2. x:xs一定要用括号括起来,因为函数调用(application)的优先级比:的优先级要高
  3. 注意区分**(x:y)****[x:y]**
    [x:y]匹配具有一个参数的list,这个参数满足匹配x:y
    (x:y)匹配具有x作为head和y作为tail的list
    总之,[]匹配是固定个数的,可以利用这个来匹配终结条件,例如
     product [] = 1
     product (x:xs) = x * product xs
    
     product [x] = x
     product (x:xs) = x * product xs
    
  4. as sign(@)
    有时候会见到这样的代码ps@(x:xs),这时候我们可以同时给列表、列表中的第一个元素、列表的剩余部分同时命名。
  5. 有办法去pattern matching列表的最后一个元素么
    为什么要去这样做呢?我们要注意到haskell中的列表是lazy evaluate的,也常是无尽列表,而无尽列表是不存在最后一个元素的。
  6. integer pattern
    这是一个类似数列递推公式的pattern,可以使用n + k这样的形式使用。这时候n是一个变量,而k是一个常数
     pred :: Int -> Int
     pred (n + 1) = n
     
     fib :: Integer -> Integer 
     fib 0 = 1
     fib 1 = 1
     fib n = fib (n-1) + fib (n-2)
     main = print (fib 5)        
    
    函数调用(application)的优先级比+等代数运算的优先级要高,所以同样要用括号括起来

lambda

在上一Chapter中通过add的例子讲到Haskell如何通过柯里化让一个函数返回另一个函数,而使用lambda可以更清晰地表现出一个函数究竟是返回的一个值还是另一个函数。例如

const :: a -> b -> a
const x _ = x

也可以写成柯里形式,接受一个参数,返回一个接受一个参数的函数

const x = \_ -> x

使用lambda同时还可以声明一个匿名函数,然后避免定义这个只用一次的具名函数。
对于多元的lambda表达式

\x -> \y -> f x y

可以简写为

\x y -> f x y

section与偏函数

prefix notation是Haskell独有的特性,即之前(Ch2.6)上在运算符两边加上小括号(op)将其作为柯里函数的用法。因为在Python中要不自己定义一个lambda x,y: x + y要不传一个operator.add
注意到既然是柯里函数,意味着说我们还可以这样写,这称为section

1
2
3
4
> (1+) 2
3
> (+2) 1
3

而不要写成lambda x: 1 + x

作为补充,提及一下。类似于(1+)的写法称为偏函数应用(partial function application)。
偏函数是对于柯里化来说的,类似于C++中的偏特化,其目的是固定一个多元函数中的某几个函数的值,产生一个新函数。例如对于add函数

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

我们可以特化出一个addOne函数

addOne :: Int -> Int
addOne = add 1

在定义偏函数应用的时候,要注意我们partial的是application而不是function。例如偏函数应用也能对下面比较复杂的高阶函数奏效

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

现在我们试图特化gadd,可以记住一条简单的规则偏应用的定义式右部必须出现原函数,例如addOne函数的右部出现了add函数。
因此尝试comp2' f = (\x y -> add (f x) (f y))是不对的,它实际上定义了一个新的函数,而正确的偏应用应当为

comp2' f = comp2 f add

Ch5 List Comprehensions

顾名思义,这章讲的是Haskell的列表生成器

[x + 1 | x <- [1..5]]

这个最近的C++标准/草案中也有类似的range
可以生成笛卡尔积

> [(x,y) | x <- [1,2,3], y <- [4,5]]
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

这类似嵌套的for循环的性质,越往右for的嵌套层数越深

> [(x,y) | y <- [4,5], x <- [1,2,3]]
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

同样类似嵌套的for循环,内层for的界可以依赖外层的值

> [(x,y) | x <- [1..3], y <- [x..3]]

它还可以做

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

这类似于派通(Python,老外奇妙的口音)中的

[item for sublist in [[1,2], [3], [4,5,6]] for item in sublist]

还可以加上guard

[x | x <- [1..10], even x]

下面是一个质数暴力筛程序

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]
prime :: Int -> Bool
prime n = factors n == [1,n]
primes :: Int -> [Int]
primes n = [x | x <- [2..n], prime x]   

zip

常用函数不解释

zip :: [a] -> [b] -> [(a, b)]

Haskell中的zip函数同样是不要求两个list长度匹配的,于是可以写出这样的代码

> pairs xs = zip xs (tail xs)
> pairs [1,2,3,4]
[(1,2),(2,3),(3,4)]

zip的反函数是unzip

unzip :: [(a, b)] -> ([a], [b])

string

string是Char的list

Ch6 Recursive Functions

  1. 介绍__Why Functional Programming Matters__这本书
    为什么lazy和pure的functional programming很重要

  2. 证明

     product [1..n] = recfac n
    
  3. 递归的作用

    1. 容易
    2. 自然
    3. 能够使用数学方法induction
  4. lazy evaluation和purity
    这块讲得比较抽象,实际上就是不同的函数有一些相似点可以提炼成一个大操作,这个大操作中包含着若干实现不同的小操作(初始条件,迭代更新规则),由于小操作是不互相影响的(purity),所以可以只实现提炼出的大操作,然后对于每个函数实现对应的小操作。这些在下一章会有详细说明

  5. 多元函数的递归

     zip :: [a] -> [b] -> [(a,b)]
     zip [] _ = []
     zip _ [] = []
     zip (x:xs) (y:ys) = (x,y) : zip xs ys
    
  6. drop
    drop需要处理两个初始条件

     drop :: Int -> [a] -> [a]
     drop 0 xs = xs
     drop _ [] = []
     drop n (_:xs) = drop (n-1) xs
     
    
  7. quick sort
    下面是出现在整个课程开头的快速排序

     qsort :: Ord a ⇒ [a] -> [a]
     qsort [] = []
     qsort (x:xs) =
         qsort smaller ++ [x] ++ qsort larger
         where
             smaller = [a | a <- xs, a <= x]
             larger = [b | b <- xs, b > x]
    

Ch7 Higher-Order Functions

上一章讲了如何使用递归来实现某些函数,这章学习通过高阶函数如mapfilterfoldr来实现它们
高阶函数(Higher-Order Functions)指的是接受一个函数作为参数,或者返回一个函数的函数(然而Haskell天生自带Currying,所以参数大于等于2就一定是高阶函数了啊)
首先介绍一些关于Combinator的书

高阶函数用途

  1. common programming idiom
    写出更短小精炼的程序
  2. DSL
    可以方便地定义领域特定语言(DSL),例如一个简单的加法器的语法
     data expr
         = value
         = add expr expr         
    
    可以发现这和我们常用来描述文法的BNF是非常类似的,而下面需要parse的话可以实现一个eval函数
     eval :: expr -> Int
    
    Haskell相比C++方便多了,要是C++的话可能会想着自己撸个逆波兰式或者LL/LR解释器啥的
    另外Haskell的模式匹配也减少了大量的代码
  3. algebra properties
    高阶函数具有一定的代数性质可以进行宏观变换,而不要担心实现细节,类似于上一章讲到的分为大操作小操作

map

map接受一个函数和一个列表,将这个函数应用到列表中的每个元素中,并返回一个列表

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

注意不要错写成

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

在一些函数式编程语言中还可以见到flatMap这个函数,它和map有本质的不同,它的签名可以写为flatMap :: (a -> [b]) -> [a] -> [b]。当作用在一个[a]数组时,可以理解成它首先生成[[b]]数组,再将这个数组拍平成[b]

filter

可以通过guard或者list comprehension来实现filter

fold

Haskell或者C++17中的fold expression,类似于python等语言中的reduce函数。这两者的区别在reduce只能处理一个相同类型(fold前),但是fold可以处理两个不同类型(fold前和fold的结果)
Haskell中分为foldlfoldr,其中foldr比较常用,将归约到的值作为运算f的右操作数

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

它接受三个参数:

  1. (a -> b -> b):一个接受ab类型参数并返回b类型参数的函数
  2. b:归约到的类型
  3. t a:这个表示一个t a的类型。这里t表示一个Foldable的类型。
    在C++中有叫模板参数的东西,例如std::vector<int>表示一个用int特化的向量表vector。Haskell中的t a类似于这个,其中t对应着类模板vectora对应着类型int
    因此可以理解成一个叫t的函数,接受一个类型变量(type variable)a作为参数,产生了一个新的类型t a。这里的t称为type constructor,而a是一个concrete type。
    一个concrete type是具有值的,例如Int之类的,它通常是由data声明的;但一个type constructor function必须接受一个type parameter才能成为一个concrete type,例如,当t为list时,t a就是[a],这里[a]是一个语法糖,等价于[] a。type constructor通常是由class声明的并可以由instance提供实现的,例如instance Applicative []
    这里注意,这里的t并不一定是容器类型,例如它不局限于list、tuple这样的东西,所以我们不能局限地认为fmap是“对于某个容器里面的所有元素都进行XX操作”。
  4. =>:我们之前见过在=>左边的Num a,这个称为类型约束。而=>右侧的函数签名部分,称为type form。

因此这个函数可以理解为

foldr f 当前/初始归约的结果 用来归约的列表  

reduce可以用fold来实现,例如Python中的

print reduce(lambda x, y: x + [y], [1,2,3,4], [])

可以用foldr实现为

main = print (foldr (\x -> \y -> [x] ++ y) [] [1,2,3,4])

类似的有foldl函数

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

上面的reduce可以用foldl实现为

main = print (foldl (\x -> \y -> x ++ [y]) [] [1,2,3,4])

foldl和foldr的区别

从定义上看,这两个函数的区别在第一个参数f上,这实际反映了运算顺序的不同。查看定义

foldlX f acc [] = acc
foldlX f acc (x:xs) = trace ("acc == " ++ show acc) foldlX f acc' xs
    where
    acc' = f acc x

foldrX f acc [] = acc
foldrX f acc (x:xs) = trace ("acc == " ++ show acc) f x (foldrX f acc xs)

执行结果

> main = print $ foldlX (+) 0 [1..5]
acc == 0
acc == 1
acc == 3
acc == 6
acc == 10
15
> main = print $ foldrX (+) 0 [1..5]
acc == 0
acc == 0
acc == 0
acc == 0
acc == 0
15

提炼出来
foldl = foldl f(x, acc) xs
foldr = f x foldr(acc, xs)
可以发现foldl是从左到右计算的,但foldr是从右到左计算的。由此导致的foldl会产生一个尾递归(右递归),foldr产生一个左递归。由于编译器可以针对尾递归优化,所以foldl可能会快一点。此外,利用strict特性(详见Ch12 strict application)的foldl'能够减少空间。
那么foldr的优势在于处理无穷列表的时候,考虑

myAndL = foldl (&&) True 
myAndR = foldr (&&) True 
> myAndL (repeat False)
> myAndR (repeat False)

那么foldr由于f = (&&)的性质被短路,所以能够返回。但是foldlf在内部,而foldl本身不具备短路原则,会陷入无限的尾递归

部分内容来自文章进行说明

使用fold实现函数

fold是被提炼出的一种“大操作”,利用foldr可以实现很多函数,之前这些函数往往要递归地通过guard、if或者list comprehension来实现

sum = foldr (+) 0

这是因为

  sum [1,2,3]
= foldr (+) 0 [1,2,3]
= foldr (+) 0 (1:(2:(3:[])))
= 1+(2+(3+0))

类似地可以定义

product = foldr (*) 1
or = foldr (||) 1
and = foldr (&&) 1

对于length函数可以如此定义

length = foldr (\_ n -> 1 + n) 0
length = sum . map (\_ -> 1)

对于reverse函数可以如此定义

reverse = foldr (\x xs -> xs ++ [x]) []

这是因为

  reverse [1,2,3]
= reverse (1:(2:(3:[])))
= (([] ++ [3]) ++ [2]) ++ [1]

所以可以看到foldr接受a类型的xb类型的xs,然后反向地去连接xs[x],最后得到的是另一个列表,这和上面的length函数是不一样的
特别地,可以重新定义++

(++ ys) = foldr (:) ys

这是因为

(xs ++ ys) = foldr (:) ys xs

这表示把Foldable类型的xs中的每个元素:ys的前面,这就相当于

  foldr (:) ys [1,2,3]
= foldr (:) ys (1:(2:(3:[])))
= (1:(2:(3:[ys])))

继续改写

  (xs ++ ys)
= (++) xs ys -- 这里原版写的是(++) ys xs但是我觉得应该是(++) xs ys
= foldr (:) ys xs

因此可以得到

  (++) ys = foldr (:) ys
= (++ ys) = foldr (:) ys

fold的作用

  1. 有些递归函数用foldr更容易实现(可以从之前的讨论中看出)
  2. 有些函数的性质可以通过foldr的代数性质推导得到,例如fusion规则和banana split规则
    • fusion
      fusion(composition)是之前讨论过的.运算符,用来实现复合函数,其具有类型
        (.) :: (b -> c) -> (a -> b) -> (a -> c)     
      
    • banana split
      这个会在后面提及
  3. 使用foldr而不是递归,可以方便进行优化

unfoldr

unfoldrfoldr的对偶函数,定义为

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

一般可以理解为a为生成的list里面的每一项,而b是下次迭代的时候的b,类似于for循环中的更新规则

unfoldr具有性质

unfoldr f' (foldr f z xs) == xs

scanl

scanlfoldl非常相似,只不过它是“扫描”获得列表,而不是将列表“折叠”起来

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

更多的高阶函数

all、any、takeWhile(常常被用来读无尽列表)、dropWhile

fmap

fmap与Functor息息相关,Functor在下章会进行补充。首先比较一下fmapmap的定义

Prelude> > :t fmap
fmap :: Functor f => (a -> b) -> f a -> f b
Prelude> > :t  map
map :: (a -> b) -> [a] -> [b]

fmap接受一个(a -> b)函数,这个函数负责将一个f a转换为f b。这里注意f是一个type constructor。
如果我们把fmapf替换成[],便可以发现map实际上是fmap对list即[]的特化。

instance Functor [] where  
    fmap = map  

Ch8 Functional Parsers

在官网上下载的PPT中第8章是Declaring Types and Classes,但实际上这章在课程中被放到了第10章。本章是Functional Parsers,会讲授重要的概念Monads,于是教授穿了件自己设计的(密集恐惧症)衣服
这一章会有点突兀,有比较多的没学过的东西,在我学习的过程中,最让我感到困惑的并不是Monad本身,而是教授讲授时定义的复杂的类型,例如即将看到的IO aShow a这样的类型,有时这会导致运行教授讲授的代码存在困难,不得不说是课程的一个缺憾。
首先要补充一个控制结构,对于下面的guard

f 0 = 18
f 1 = 15
f 2 = 12
f x = 12 - x

这种写法又称为piece-wise version,因为实际上定义了4个f函数。如果用case,可以写作

f x = case x of 0 -> 18
                1 -> 15
                2 -> 12
                _ -> 12 - x

课程开始,照例讲了点别的,介绍Functional Portal

Parser Type

在本章中,我们要实现一个类型Parser,通过实现这个Parser,我们也就实现了Monad的核心部分。
很自然地,在Haskell中,用函数来表示Parser

type Parser = String -> Tree

但是有时候Parser只处理输入串String的一部分,所以Parser也要返回未使用的String

type Parser = String -> (Tree, String)

有时候输入串String不能生成语法树Tree,于是Tree并不是一定有的,是一个optional值,这在Haskell中可以用Maybe来表示

data Maybe a = Nothing
             | Just a

Maybe在Haskell中用来处理optional值,它是一个Monad,data语句在第10章会有介绍,NothingJust aMaybe a的两个constructor,它们看起来像为C++中的enum,但实际上更类似于C++中的构造函数。Maybe一个类型可以从Nothing构造,但返回一个非Nothing的值a时就需要返回Just a
Nothing很好理解,类似于其他语言中的nullNonenil
在没学习Ch10 Declaring Types and Classes时,Just是个比较奇怪的概念。首先查看它的定义

Just :: a -> Maybe a

从定义中可以看到Just返回的是Maybe a对象,这有点类似于函数重载或者SFINAE的意味,我们可以理解为调用了Maybe不同的构造函数,并且Nothing可以表示另一个构造函数,不过这个构造函数不接受参数罢了。如果我们把data语句当成了enum,这里就不好理解了。
教授认为出于方便考虑,并不需要使用Maybe这东西,用一个简单的list就可以了

type Parser = String -> [(Tree, String)]

因此这个list要不是一个单元素的列表(singleton list),要不是个空列表
最后,Parser并不一定返回一个语法树,所以加上一个泛型

type Parser a = String -> [(a, String)]

总结一下,现在我们已经知道了list的作用是为了实现optional,tuple的作用是辅助类似于遍历字符串的一个指针。
事实上这个Parser是一个Monad雏形。注意如果使用附带的代码Parsing.hs会发现视频隐藏了Parser的一些关键定义,这会导致直接键入并运行视频中的代码可能会出现错误(接下来会看到)。视频中给出上面这样的Parser定义是为了方便理解的考虑,实际上也是实现了一个Monad的type class。

Bottom

我打算在这里插进来介绍一个_|_,它叫Bottom。
当我们在讨论编程语言时,我们常常厌恶null。但实际上null的语义是无法避免的,因为停机问题是没有解的。Haskell中也有Bottom这个东西。

一些简单的语法分析器

item

这个Parser在输入为空是fail,否则读取输入的第一个字符,下面根据type Parser a = String -> [(a, String)]来推导item的类型

item :: Parser Char
     :: String -> [(Char, String)]
     :: [Char] -> [(Char, [Char])]

下面查看item的定义

item = \inp -> case inp of
                    [] -> []
                    (x:xs) -> [(x,xs)]

failure

和名字一样,这个语法分析器总是失败

failure :: Parser a
failure = \inp -> []

return

这个语法分析器的定义不太一样了,它返回一个接受任何输入的一个语法分析器,这个语法分析器对于任意输入返回v

return :: a -> Parser a
return v = \inp -> [(v, inp)]       

我们分析一下返回类型

   Parser a
:: String -> [(a, String)]
:: [Char] -> [(Char, String)]

原来返回的是个函数,测试一下

main = print $ (return "123") "xxx"

发现结果是"123"

return关键字的辨析

Haskell中的return的和大多数语言中return关键字名字相同,也都经常出现在语句的末尾。但两者的意义却完全不同。Haskell中也不需要什么return,语句自身就是返回值,所以不要把两个混淆。
在Haskell的Prelude中定义有类似以上代码实现的return函数。

> :t return
return :: Monad m => a -> m a

实际上return是Monad里面的一个非常重要的运算,在后面即将讲到。

+++

这个语法分析器类似于一个选择结构,实际上它是一个存在的运算符<*>的重新实现。它表现得像语法分析器p,如果p能succeed,否则表现得像语法分析器q

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = \inp -> case p inp of
                        [] -> parser q inp
                        [(v, out)] -> [(v, out)]                                

parse

parse是个很重要的语法分析器,如果实际运行附带代码里面的Parsing.hs,就会发现

print (item "123")

是会报错的,正确的方式是运行

print (parse item "123")

这类似return的问题,这是因为Parser的定义不同导致的,在现阶段应该使用视频中给出的代码
再看一下parse的定义

parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp

值得注意的是parse函数将这个语法分析器(再次强调根据type Parser定义,Parse实际上也是一个函数p应用(apply)到inp上。它的作用是让代码更清晰

检验上面的语法分析器

检验上面的语法分析器需要Parser类型的定义。

  1. item
     > parse item ""
     []
     > parse item "abc"
     [('a', "bc")]
    
  2. failure
     > parse failure "abc"
     []
    
  3. return
     > parse (return 1) "abc"
     [(1, "abc")]
    
  4. +++
     > parse (item +++ return 'd') "abc"
     [('a', "bc")]
     > parse (failure +++ return 'd') "abc"
     [('d', "abc")]
    

Sequencing

到目前为止,我们都是使用递归来描述一系列的操作的,借助list comprehension或者高阶函数也可以实现循环操作,借助if、guard或者case实现选择语句。
但是顺序操作,这个命令式语言最常见的操作却一直没有办法实现,事实上由于Haskell的lazy特性,其更倾向于是并举的。而Monad正是解决这个问题的

do

可以用do来表示顺序操作,do能够作用在任意的monadic类型上

p :: Parser (Char, Char)
p = do x <- item
       item
       y <- item
       return (x, y)                

注意:这段代码需要通过附带的代码Parsing.hs运行,因为Parser类型实际上要实现Monad类型类,才能够使用>>=<-等运算符
如果仅仅使用type来定义

type Parser a = String -> [(a, String)]

简单地推导下可以发现

:: Parser (Char, Char)
:: [((Char, Char), String)]

但是在错误信息中发现编译器实际上推导出的(x, y)

:: [(([(Char, String)], [(Char, String)]), String)]

同样,在Parsing.hs运行下面的代码可能会报错,因为使用了newtype定义的类型和[(a, String)]是两个完全不一样的类型了,所以要在前面加一个P。可以参考Parsing.hs里面的itemparse函数。

在下面两节将要介绍>>=运算符,这个运算符和do同样可以描述序列化的操作,而序列化是Monad的一种用途。

Select和SelectMany

在了解>>=前,教授提到了C#中的Select方法和SelectMany方法,其中Monad类似于SelectMany方法,因为Monad可以控制如何返回结果。

可以看到,SelectMany能够将结果“拍平”成一维数组。并且可以多接受一个函数,表示如何返回结果。

>>=

这个操作称为bind,是Monad中最重要的一个运算符,在C#中称为SelectMany,先查看它的定义

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

【注】实际上在Haskell源码(在安装目录下的doc文件夹)中,该运算符是以如下形式出现的(>>=) :: forall a b. m a -> (a -> m b) -> m bforall关键字来自Existentially quantified types这个扩展,并且作为默认的选项,这里可以直接忽略。
因为Parser是一个Monad,为了直观一点,所以对应到Parser类型

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

这个运算接受一个参数Parser a,将它给一个函数(a -> Parser b),随后得到结果Parser b
于是我们产生了几个问题:

  1. 这看起来就是提供了一个策略,能通过a -> Parser b实现函数m a -> m b能实现的功能,感觉没什么了不起的,为什么不能直接定义一个m a -> m b的函数呢?
    首先在m a -> m b的函数里面,Haskell无法从m a类型把a提取出来,这样就不能完成需要直接操作a的运算了。
    如果我们把m a想成有副作用的a,那能不能把m a当成a来操作,这样定义了a -> b相当于也定义了m a -> m b呢?答案是也不能的,因为还有一个具有另外含义的Monad,如list, Maybe
  2. 这个操作有点类似于前面见到过的复合运算(.),或者($),他们之间有什么关系呢?
    事实上($)(<$>)(fmap)、(<*>)(apply)、(>>=)(bind)四个运算符有着相似的性质,在下面的。
  3. 为什么要专门拿出来这个操作大书特书呢?
    其实这和Haskell需要实现的纯洁性有关。在看完<-的介绍和下章的内容后会有更深的体会。

Monad

根据Wikipedia,Monad具有两个操作,第一个是之前看到的**return,另一个是上面的bind**

  1. return
    return操作又称为unit,从一个普通类型a构造一个具有类型M a的monadic value
  2. bind
    这个操作接受一个M a的monadic value,将aM a类型的变量里面拆出,并传给函数(a -> M b)来,输出具有类型M b的另一个值。有点类似linux里面的管道命令。

此外,之前看到的failure其实都可以作为Monad的一部分,除此之外还有第四个运算符>>。这个运算符实际上是>>=的一个简化版本

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

这个操作的意义实际上也是合成两个操作,起到语法糖的功能,例如a >> b实际上等价于a >>= \ _ -> b,也就是对于任意的a返回常量b
其实do操作也可以看做>>的语法糖

do action1
   action2
   action3

可以写成

action1 >>
action2 >>
action3

不过由于没有>>=do中必须通过下面的<-来从Monad中“提取”值

List Monad和<-

在list comprehension中出现了<-这个运算符,例如在下面的例子中,<-[a]中“提取(feed)”了a

[x | x <- xs]

但是对于do中的x <- itemitem是语法分析器,类型Parser Char,而通过<-得到Char类型,这是为什么?其实这和Monad中的>>=是一个道理。
do语句中,<-运算符称为single assignment operator,或binding operator。这个被用作在monadic computation中提取一个值。准确一点说,<-将Monad内的一个计算结果和一个名字绑定,或者可以说<-类似于赋值的等号。
例如这里的item是一个Parser a,在提取后得到一个a。这有点类似于C#中的装箱拆箱操作,如果把return当做一个“装箱”,那么<-就可以看做一个“拆箱”。但是必须记住的是,Parser或者后面提到的IO这样的Monad,拆箱操作必须只能通过>>=或等价的do语句执行,这样保证了Haskell语言本身的无副作用性。
>>=里面不需要<-,因为“拆箱”操作由被隐式地实现。观察>>=的第二个参数a -> Parser b,这个a从第一个参数m a中被隐式地提取出来了。而对于do中,我们必须要用<-来显式地提出。

作为补充,提及一下list monad。从上面的讨论中我们可以发现list comprehension和monad中的do语句有着异曲同工之妙。事实上list也是一个monad,我们可以用do来实现list comprehension。

[(i,j) | i <- [1,2], j <- [1..4] ]

对于上面的list comprehension,我们可以使用do来改写

do i <- [1,2]
   j <- [1..4]
   return (i,j)

Maybe Monad

之前提及的Maybe也是一个Monad,我们可以给出如下的定义

return :: a -> Maybe a
return x  = Just x

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
(>>=) m g = case m of
               Nothing -> Nothing
               Just x  -> g x

结论

再一次说明,可以看出,这四行首先调用item获得一个x,然后再次调用item,获取并discard掉一个结果,然后再次调用item,获得一个y。最后返回一个tuple(x, y)
这类似于Linq中的from-select notation

from x in item
from dummy in item
from y in item
select new {x, y}

最后关于Monad,推荐一篇文章

Monad与Continuation

从这里开始是我的一些补充。
Monad和CPS有一些类似之处,事实上这篇文章中提及了两者之间的关系。

Continuation简介

单独列了一篇文章

Continuation Monad

Functor

在上章的fmap部分我们了解了函子(Functor)。
Functor是一个type class,实际上Functorfmap是紧密联系的,一个能被mapped over(即能够fmap)的类型即是Functor,我们定义一个Functor f

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    (<$) :: a -> f b -> f a
    (<$) =  fmap . const

其中fmap有对应的操作符

(<$>) :: Functor f => (a -> b) -> f a -> f b

这里f a称为**上下文中的值(in context value)**,因为af包装了起来。从定义中可以看出,fmap把Functor f a从上下文中的东西拿出来,然后交给一个函数(a -> b),函数处理完又封装进contextf b中。
此外,由于我们的函数是柯里函数,并且->是右结合的,所以fmap还可以理解为

fmap :: (a -> b) -> (f a -> f b)

即接受一个(a -> b)类型的函数,并返回一个函数f a -> f b,这个函数接受一个Functor f a并返回一个Functor f b,例如

fmap (*2) :: (Num a, Functor f) => f a -> f a  

Maybe Functor

之前看到的Maybe也是一个Functor

instance Functor Maybe where  
    fmap f (Just x) = Just (f x)  
    fmap f Nothing = Nothing  
    

Function Functor ->

Function,也是一个Functor。Arrow运算符->,对,就是用来定义函数的。r -> a可以写成(->) r a。由于type constructor能且只能接受一个参数,所以(->)不是Functor,但是(->) r(r ->)是Functor。
既然函数->是Functor,那就得定义它对应的fmap啊,于是

instance Functor ((->) r) where  
    fmap f g = (\x -> f (g x))

f (g x)看起来很眼熟,不禁联想到前面的

(f . g) x
:: f (g x)

我们是不是可以直接给出如下定义?

instance Functor ((->) r) where  
    fmap = (.)

于是我们再直接代入一下看看

f    :: (->) r
fmap :: (a -> b) -> f a -> f b
     :: (a -> b) -> ((->) r a) -> ((->) r b)
     :: (a -> b) -> (r -> a) -> (r -> a)
(.)  :: (a -> b) -> (r -> a) -> (r -> b)

可以发现这个((->) r)其实等价于composition(.)

fmap的性质

fmap具有下面的性质

fmap id = id
fmap (p . q) = (fmap p) . (fmap q)

第一条看起来很简单,第二条讲的是fmap.有分配律。
对于第二条,我们假设另一个Functor X

fmap (f . g) X = (fmap f) . (fmap g) X

不妨令f :: b -> cg :: a -> b
首先看左边

fmap (f . g) X
::  fmap (a -> c) X a -> X c
::  X a -> X c

再看右边

(fmap f) :: f -> X b -> X c
(fmap g) :: f -> X a -> X b
(fmap f) . (fmap g) X
::  (X b -> X c) . (X a -> X b)
::  X a -> X c

因此等式成立。在推导的时候需要注意,里面的fmap.都是函数应用而不是函数定义,带入定义式是不对的。

Applicative

Applicative定义如下,这里省略了(*>)(<*)的默认实现

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

先看一看这个东西怎么用吧

> [(2*),(5*),(9*)] <*> [1,4,7]
[2,8,14,5,20,35,9,36,63]

在这个例子里面Applicative((<*>))像计算笛卡尔积一样,将一列表的函数应用到另一个列表的整数上,然后列表的长度改变了。
首先class Functor f => Applicative f where,我们知道这里出现在=>前的Functor f是type constraint,所以一个Applicative也是是Functor。这意味着Applicative类型(List、Maybe等)不仅可以当成Functor来用,还具有Functor没有的一些用法。

> (+3) <$> (Just 5)
Just 8
> Just (+3) <*> (Just 5)
Just 8
> Just (+3) <$> (Just 5)

pure可以参照理解成Monad里面的return,相当于我们把一个a打包放到了一个Applicative Functorf a里面。
<*>的定义就有意思了。
首先查看第一个参数f (a -> b),这是把一个函数作为type parameter给f。从前我们的Functor里面包含的是值,不过这次里面包含着Function,例如本节开头的例子中,f是List,f (a -> b)便是一个List的Num a => a -> a函数,所以f (a -> b)在这里被称作上下文中的函数(in context function)。如果把这个函数从上下文中拿出来一看,原来就和fmap的第一个函数一样了。
第二个参数是一个Functor f a。然后(<*>)做的事情是把Function从Function Functor中“提取”出来,fmap到第二个Functorf a上,这个fmap就和Functor一致了。
为了观察具体流程,下面的代码对比实现了Maybe的Functor和Applicative

instance Applicative Maybe where  
    pure = Just  
    Nothing <*> _ = Nothing  
    (Just f) <*> something = fmap f something  
    
instance Functor Maybe where  
    fmap f (Just x) = Just (f x)  
    fmap f Nothing = Nothing 

首先我们看到(Just f)似乎通过pattern match提取出了f,而Nothing里面并没有任何的函数可以被提取,如果我们第一个参数的类型不是f (a -> b)而直接是a -> b,那我们就不能传入Nothing这样的参数了。可以发现,Applicative的特点是**<*>运算符的两边都可以使Applicative**,而Functor的特点是fmap/<$>只有第二个参数能够是Functor。

Applicative还有一个性质是Sequencing,也就是我们在本章看到的Monad所具有的性质。它的表现是Applicative Style,也就是对于一个多元的普通函数,也可以通过<*>来应用到多个带上下文的参数中。

pure f <*> x <*> y <*> ...
fmap f x <*> y <*> ...
f <$> x <*> y <*> ...

注意到pure ffmap f xf <$> x是等价的。例如

> (\x y z -> [x,y,z]) <$> (+3) <*> (*2) <*> (/2) $ 5  
[8.0,10.0,2.5]  

在本节开头,我们接触了List Applicative,[(2*),(5*),(9*)] <*> [1,4,7] = [2,8,14,5,20,35,9,36,63],下面我们看看具体的定义

instance Applicative [] where  
pure x = [x]  
fs <*> xs = [f x | f <- fs, x <- xs]

查看Applicative的介绍,还可以发现((->) a)这个东西也是Applicative的,这个奇怪的东西,我们在Functor中看到过。
如下所示,pure的签名实际上是pure :: a -> (r -> a)

1
2
3
instance Applicative ((->) a) where
pure x = (\_ -> x)
(<*>) f g x = f x (g x)

<*>类似于SKI组合子中的S,pure类似于SKI组合子中的I。

Monoid

幺半群(Monoid)即带有单位元的半群,因此幺半群满足封闭性、结合律、单位元

import Data.Monoid
class Monoid m where  
    mempty :: m  
    mappend :: m -> m -> m  
    mconcat :: [m] -> m  
    mconcat = foldr mappend mempty  

Monad和Functor以及Applicative

Monad是一个Applicative,而Applicative是Functor,所以所有的Monad都是Functor(因为Applicative都是Functor)。
这三者有着类似的定义,和各自的独特之处

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

如果把(>>=)的参数掉个个成=<<

(=<<) :: Monad m        => (a -> m b) -> (m a -> m b)
(<*>) :: Applicative m  => m (a -> b) -> (m a -> m b)
(<$>) :: Functor m      =>   (a -> b) -> (m a -> m b)

可以发现fmap的返回值都是(m a -> m b),三者差距在于“定义域”的不同。其中Functor能够接受任意函数,但是(<*>)能接受m (a -> b)(其实这都不一定是个函数),而(>>=)只能接受(a -> m b)
fmap(<*>)再到(>>=), 我们对于值的控制力和计算的灵活性逐渐增加, 但这是以结果性质的弱化为代价的。
这里的控制力和灵活性取决于是我们传入的函数m的信息有多少。即使这三个操作符会再接受一个m a值的参数,但m a这个值对其实际的操作者,即传入的函数来说是一个黑箱。

  1. 对于fmap来说,我们传入的(a -> b)一点都接触不到m这个东西,m是List,抑或是Maybe,我们的函数根本不需要去考虑,m a的拆箱和结果的装箱,Functor m已经包办了,你自己是一点主都做不了的。
  2. 但是对(<*>)来说,我们的函数和值f a一样都是in context的,因此在函数里面我们是知道“容器类型”m是个啥的。例如我们可以知道(<*>)包装的是列表还是Maybe
  3. (>>=)比Applicative更进一步的是,它可以自行制定如何将结果包装成m b类型,而这在Applicative都是由具体的instance来规定的。

Derived Primitive

  1. 一个判断一个Char是否满足给定谓词(Predicate)的语法分析器

     sat :: (Char -> Bool) -> Parser Char
     sat p = do x <- item
                if p x then return x else failure
    
  2. 使用sat

     digit :: Parser Char
     digit = sat isDigit
     
     many :: Parser a -> Parser [a]
     many p = many1 p +++ return []
     many1 :: Parser a -> Parser [a]
     many1 p = do
                 v <- p
                 vs <- many p
                 return (v:vs)
                 
    

    还有若干代码,这里先告一段落

Monad的性质

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

幺半群(Monoid)在前面已有介绍
自函子(Endofunctor)即一个将范畴映射到自身的函子(Functor)

do

  1. do {e} -> e
    一个操作用do包裹起来等于它自己
  2. do {e; es} -> e >> do{es}
    这就是前面的>>的语法糖
  3. do {let decls; es} -> let decls in do {es}
    这里面用到了letlet...in两个不同的结构块。

>>=

  1. return a >>= f = f a
    这个性质相当于是将一个普通值a穿上Monad的衣服,传给一个函数f,相当于直接调用这个函数f a
  2. m >>= return = m
    这个性质是因为对于一个Monad mm >>= return动作相当于先通过>>=把衣服脱掉,然后在通过return重新穿上Monad的衣服
  3. f >>= (\x -> g x >>= h) ≡ (f >>= g) >>= h

Monad相关函数操作

Lifting

fmap是一个lifting操作,lifting操作一般作用于一个函数,并把它变为另一个相关的函数。

Ch9 Interactive Programs

上一章讲了什么是Monad,并了解了一些常见的Monad。通过将Functor和Applicative和Monad比较,能看出Monad使用在纯函数计算上的方便之处。
这章进一步讨论了IO Monad,并以此体会Monad是如何帮助IO来封装副作用的。

本章节还介绍了Hangman游戏的实现,在此略过。

交互式操作

IO和上一章见到的Parser一样,都是一个Monad typeclass的实现,它“封印”了IO操作中和副作用相关的部分。
我们将只在开始接受所有输入、只在最后返回所有输出的程序称为批处理程序batch program,如果这个程序能够在运行时从键盘等设备获取输入,并将结果写到屏幕上,这样的程序称为交互式程序interactive program。

交互式程序有副作用,并且是顺序操作。因此难点在于Haskell作为纯函数式语言是没有副作用,类似于数学函数和批处理程序。当然,无副作用的好处也是显而易见,我们在pure函数中,我们不需要关注外界的异常,只需要处理返回值即可,减轻了负担。

从代码角度来看,整个IO过程“投射”在Haskell代码的部分是纯函数式,无副作用的,而将副作用投射到另一个“里世界”中,Monad成为了这两个世界之间沟通的桥梁。

为了能够描述这样的IO,Haskell借助了Monad。很容易发现Monad带有的Sequencing特性非常适合。

考虑最简单的一个情况,一个纯交互式程序是没有返回值的,对于“没有返回值”,可以将其定义为IO ()()在先前提到过,称为unit,是一个空的tuple,类似于C++中的void。这样你就可以在不破坏无副作用的情况下到另一个次元做坏事了。下面我们看看具体的一些函数。

常用IO函数

标准输入输出

getChar :: IO Char,从键盘读取一个字符,显示到屏幕上,并作为返回值。

它可能类似C++中的int ::getchar(void)函数,但在Haskell中它的定义并不是一个函数,例如可以写成getChar :: () -> IO Char。教授讲解由于Haskell是lazy的,所以上述的函数形式虽然显得更熟悉一些,但是并没有必要写成这样。

在Scala中,函数就是对象,但在Haskell中,我们可以感受到“对象”就是函数,在下面的章节中,会看到邱奇编码的概念,展示了如何用函数(lambda演算)来表达数组、元组、整数等常见的数据结构。

putChar :: Char -> IO ()将一个Char打印在屏幕上,不返回值。
return :: a -> IO a,接受一个a类型,并返回一个IO a类型。

文件操作

套接口操作

IO Sequencing

前面提到do语句可以合并多个IO操作为一个IO操作。考虑下面的一个do语句

a :: IO (Char, Char)
a = do
      x <- getChar
      getChar
      y <- getChar
      return (x, y)

根据上面的分析,其中xyChar类型,return(x, y)的tuple转变为一个IO tuple类型。这样的do也可以通过>>=来写(在上一章已经了解了怎么用>>来改写do

getChar >>= \x ->
  getChar >>= \_ ->
    getChar >>= \y -> 
      return (x, y)
          

Derived Primitives

本章节中顺着演讲者的思路,去定义一些自己的IO函数。
可以从getChar定义getLine

getLine = do
            x <- getChar
            if x == '\n' then
              return []
            else
              do 
                xs <- getLine
                return (x:xs)

Haskell中,字符串就是Char的list,下面是和字符串有关的函数

putStr' :: String -> IO ()
putStr' [] = return ()
putStr' (x:xs) = do
                  putChar x
                  putStr' xs

putStrLn :: String -> IO ()
putStrLn xs = do
        putStr xs
        putChar '\n'
        

同时我们可以使用foldr来定义putStr函数,这里同样用>>=来代替do表示顺序操作

putStr2 :: String -> IO ()
putStr2 = foldr (++++) (return ())
            where
              x ++++ p = putChar x >>= \_ -> p
              

下面是一个求字符串长度的函数

strlen :: IO ()
strlen = do
          putStr "Enter a string:"
          xs <- getLine
          putStr "Length is"
          putStr $ show $ length xs
          

可以再次体会到,Haskell程序解决副作用的方法是将副作用放在执行IO ()时了,但是这个语句对于Haskell本身而言,是pure functional的。
注意IO对象是不能够被print的

a = do 
  x <- getChar 
  return x
main = print a

这个代码中a通过return返回了一个IO,因此是有副作用的,如果print能够处理,那副作用就“蔓延到”无副作用的代码里面了。所以可以认为IO这样的Monad是有传染性的。如果要实现这样的操作应该借助于<-运算符

f = do 
  x <- getChar 
  return x

main = do 
        x <- f
        print x

或者>>=运算符

f = do 
  x <- getChar 
  return x

main = f >>= print

随机

异常

IO 操作会产生异常显而易见,因为外界的环境无法预知。pure函数可能产生异常,但只有它涉及IO操作时,异常才会被捕获。

1
2
3
4
ghci> 4 `div` 0  
*** Exception: divide by zero
ghci> head []
*** Exception: Prelude.head: empty list

Ch10 Declaring Types and Classes

观察Monad m a中的m,在这里被用作type constructor,所以m可以是Parer可以是IO,这种higher kinded polymorphic并不是使用type parameter,而是使用一个从type到type的函数(type function)来实现。这种Higher Kinded Types实现的方式是Haskell的一个特别的性质。在Haskell中,我们可以定义具有>>=bind运算,就可以被称作Monad,但是在C#等语言中,没有这样的概念(notion),有这样的模式(pattern)。

有关type function

我们知道普通的函数,例如a -> b表示从类型a的值到类型b的值的一个映射。而type function中,把类型本身当做了“操作数”,即a -> b是类型a到类型b的映射,我们甚至可以把a -> b看做(->) a b。这两者的概念有点类似type constructor和data constructor的区别。
类似于对于普通函数的type(:t)我们可以使用kind(:t)来描述type function。容易理解type的kind是*,而Functor/Monad这些类型类的的kind就是* -> *。有趣的是->也有kind,即* -> * -> *

Type Declarations

type语句为一个已有类型提供别名,类似于C/C++中的typedefusing

type String = [Char]

type语句可以拥有参数,所以我们可以把它看做类型上的一个函数,可以发现type level和value level上的函数形式上非常相似

type Pair a = (a, a)
pair a = (a, a)

下面是一个mult函数的定义

mult :: Pair Int -> Int
mult (m, n) = m * n

很多其他的函数式语言完全模糊了这两者的界限,如Agda、Cayenne这两个类似Haskell的语言,和有关函数式编程本质有关的Coq语言等。还有一个替代的方案叫做lambda cube。介绍Phil Watler(音)的论文。

Type Declaration是可以嵌套的,下面的代码是正确的:

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

但是递归是不可以的,显然这会得到一个无尽的定义

type Tree = (Int, [Tree])

Data Declarations

使用data语句可以定义一个新的类型

data Bool = False | True

这类似于C#中的抽象类(为什么不是enum哦),或者用来描述上下文无关文法的BNF。

abstract class Bool {}
sealed class True : Bool {}
sealed class False : Bool {}

这表示我们定义了一个Bool类型,其中TrueFalse是具有一个Bool类型的值的constructor。TrueFalse还可以被称为subtype。在定义类型的时候,type constructor和value/data constructor的名字都应该以大写字母开头。
由于True不是类型,所以定义函数的时候不能写成

f :: True -> ...

而只能

f :: Bool -> ...

然后True等constructor可以用来做pattern matching,这称为deconstructing。这看起来像C++中的downcasting

f True = ...

使用data定义的类型的值(values)和内置类型的值使用方式是类似的

data Answer = Yes | No | Unknown
answers :: [Answer]
answers = [Yes, No, Unknown]

注意answers类似于上章遇到的getChar,可以看做一个接受0个参数的函数。
在定义type的时候constructor也可以拥有参数(所以上面会理解成抽象类)。如下面的代码所示,我们可以在Shape的定义外部对CircleRect进行“特化”。

data Shape = Circle Float
            | Rect Float Float
square :: Float -> Shape
square n = Rect n n

由于Haskell很难添加一个subtype到已有的type中,例如想要给Shape加上一个Polygonsubtype是不容易的,但是用上面这种“虚函数”的方式确实简单的。这和C#等OOP语言是截然相反的,OOP的语言往往继承是容易的(假设去掉sealed),但是给一个写好的类里面增改一个虚函数确实不容易的。这是一种难以两全其美的问题,有许多论文研究这点。
上面的代码中,CircleRect被看做类型Shape“构造函数”(constructor functions)。
特别注意,CircleRect是constructor,但不是类型,他们构造出的是Shape类型。

Circle :: Float -> Shape
Rect :: Float -> Float -> Shape

constructor functions和普通函数的区别是前者不用=来定义(no defining equations)。

同样地,data语句也可以带参数,例如经典的Maybe:

data Maybe a = Nothing | Just a

这里教授又讲授了一遍自己prefer list to Maybe的理由,然后其实Maybe和list都是Monad,其实看到这里我还是挺惊讶的。于是不妨推导一下为什么list是Monad:
首先介绍一个concat函数,其定义为

concat :: Foldable t => t [a] -> [a]

为了理解这个定义,可以把Foldable t看做它的一个特例,也就是[],那么concat就是将一个二维数组拍平

concat :: [[a]] -> [a]

而list的>>=运算,即list >>= f可以理解为等价于concat (map f list)

特别地,对于仅有一个constructor的、一个field的类型,可以使用newtype替代data关键字

data/value constructor和type constructor

作为扩展,解释一下data/value constructor和type constructor之间的联系与区别。这其实在stackoverflow上讲得很清楚。两者区别是:

  1. data/value constructor可以看做一个返回的函数
    例如本章讲的CircleRect,它们都能够返回一个Shape类型的
  2. type constructor可以看做一个返回类型的函数
    fmap定义中的f,Monadm a中的m,实际上是产生了一个新的类型。这个有点类似于C++中的模板类,不过Haskell在这方面要更加深层次,我们将在最后的多态性专题进行讨论。

两者联系
data Tree a = Tip | Node a (Tree a) (Tree a)为例。

  1. 等式左边的Tree称为type constructor。而Tree a是一个type。
  2. 等式右边具有两个data/value constuctor,因此这个data type是多态的

instance、type和data语句的区别

instance根据class定义的type class来产生一个type constructor
type用来一个type constructor产生一个具体类型concrete type
data用来一个type constructor提供一系列data/value constructor得到value

Recursive types

使用data语句定义的type可以是递归的。例如我们可以定义一个自然数类型(邱奇数)

data Nat = Zero | Succ Nat

这里的Nat是一个新类型,Nat有两个constructor,它们分别具有类型Zero :: NatSucc :: Nat -> Nat,由Ch3中学习过的,这里的::表示“具有类型”。
于是我们实际可以得到这样的一个无尽序列

Zero
Succ Zero
Succ (Succ Zero)
...

我们看看能不能输出它

Prelude> (Succ Zero)
<interactive>:15:1: error:
    ? No instance for (Show Nat) arising from a use of ‘print’
    ? In a stmt of an interactive GHCi command: print it
Prelude> print $ (Succ Zero) 

可以先转换成Int

nat2int :: Nat -> Int
nat2int Zero = 0
nat2int (Succ n) = 1 + nat2int n

然后输出

print $ nat2int (Succ Zero)

下面实现自然数类型的加法,对于C++来说,这意味着定义operator+

add :: Nat -> Nat -> Nat
add m n = int2nat (nat2int m + nat2int n)

上面是一个很直截了当的做法,先转换成Int,加完后再转回Nat,有没有不需要借助Int的方法呢?

add' :: Nat -> Nat -> Nat
add' m Zero = m
add' m n = (iterate Succ m) !! nat2int n

首先想到的是add m n等于nSucc m,不过这种方法还是需要转换,于是有下面的方法

add Zero n = n
add (Succ m) n = Succ (add m n)

我们把n看做常数,将add转换为一元函数gSucc类比做+1,这就有点类似数学归纳法的味道:

g (x + 1) = (g x) + 1、

Church encoding 和 Scott encoding

Arithmetic Expressions

下面我们来为代数运算的“AST”实现一套类型系统

data Expr = Val Int | Add Expr Expr | Mul Expr Expr

注意我们将所有的代数运算定义到一个Expr类型里面,这是一个“比较Haskell”的写法。我们的代数式可以写成下面这样,从计算一个“函数”变成了构造一个Expr“对象”

Add (Val 1) (Mul (Val 2) (Val 3))

我们使用eval来计算这个Expr,可以写成

eval :: Expr -> Int
eval (Val n) = n
eval (Add x y) = eval x + eval y
eval (Mul x y) = eval x * eval y

Binary Tree

二叉树由叶子(Leaf)和节点(Node)构成

data Tree = Leaf Int | Node Tree Int Tree

定义了occur用来查找具有某个值的节点

Ch11 The Countdown Problem

这次换了一位讲师

Countdown游戏介绍

Countdown游戏中使用若干个正整数(每个数最多使用一次),使用四则运算来计算得到一个指定值,其中所有的中间结果也必须是正整数。

Haskell建模

首先我们把运算定义成一个Op类型

data Op = Add | Sub | Mul | Div

然后定义一个applyapply将一个Op作用到它的两个操作数上。

apply :: Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x `div` y

由于游戏中有正整数的限制,所以使用valid来判断某运算是否可以执行

valid :: Op -> Int -> Int -> Bool
valid Add _ _ = True
valid Sub x y = x > y
valid Mul _ _ = True
valid Div x y = x `mod` y == 0

下面定义Expr

data Expr = Val Int | App Op Expr Expr

相比上一章看到的Expr,这里将AddMul等constructor合并成了App(application)constructor。例如1 + 2可以写成

App Add (Val 1) (Val 2)

eval函数能够计算一个Expr的值

eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r) = [apply o x y | x <- eval l
                                , y <- eval r
                                , valid o x y]

虽然eval返回的是一个列表,但到最后列表里只会有一个数,除非出现问题列表里一个数都没有。
这里eval匹配了Expr的两个data constructor。
在第二个pattern matching条件中使用到了Ch5中讲到的list comprehension,特别地,valid o x y称为guard。注意到在eval (App o l r)中,list comprehension右部给出了三个条件,这三个条件只要有一个不满足,这个list就会变成空的。

Brute force solution

定义values函数,列出一个表达式中所有用到的数
定义exprs函数,得出一组Int能够构造出的所有Expr,这是一个关键的函数

exprs :: [Int] -> [Expr]
exprs [] = []
exprs [n] = [Val n]
exprs ns = [e | (ls,rs) <- split ns
              , l <- exprs ls
              , r <- exprs rs
              , e <- combine l r]

对于空列表和单元素列表(singleton list)这是显然的。
对于多元素有序列表,我们进行divide and conquer。可以用split ns将列表ns进行分划,对于长度为l的序列,我们有l - 1中分划方案。然后我们对于每一个分划(ls,rs),对其左右部分别递归调用exprs
于是定义split函数,列出一个列表所有的分划
得到l::Exprr::Expr,最后将这两个列表分别合并,得到App Add l r等四个结果。
于是可以定义combine函数

combine :: Expr -> Expr -> [Expr]
combine l r = [App o l r | o <- [Add,Sub,Mul,Div]]

其中

perms :: [a] -> [[a]]
perms []     = [[]]
perms (x:xs) = concat (map (interleave x) (perms xs))

现在我们可以解决这个问题了,我们对于exprs构造出的每个expr,使用eval expr == [n]即可filter出所有可能的结果。注意到我们不一定要用尽给定的数,也不一定这些数就按照从小到大等特定的顺序排列,所以我们需要尝试给出的数的所有子集。
于是可以定义choice函数,列出一个列表所有的子集

choices :: [a] -> [[a]]
choices = concat . map perms . subs

现在我们可以列举出所有的结果了

solutions :: [Int] -> Int -> [Expr]
solutions ns n = [e | ns' <- choices ns
                    , e <- exprs ns'
                    , eval e == [n]]

此外我们还可以判断某输入能否构成一组解

solution :: Expr -> [Int] -> Int -> Bool
solution e ns n = elem (values e) (choices ns) && eval e == [n]

剪枝优化

考虑到valid的计算式时很少的,所以可以通过earlier rejection策略进行剪枝。

Ch12 Lazy Evaluation

lazy evaluation是Haskell的一个独特的性质

求值顺序

以自增函数inc为例,inc (2*3)有两种求值顺序。第一种是intermost call-by-value,先对2*3求值为6,然后计算inc 6;第二种是outmost call-by-name,先计算inc (2*3) = (2*3) + 1,然后再计算6 + 1。接着和C#中的带副作用的impure运算进行比较,说明的求值顺序不同的影响。

下面是一个Church-Rosser证明的定理,如果a可以归约为b和c,那么一定有一个d,b和c可以归约到d。

下面介绍带lambda的情况,如mult (1+2) (2+3)可以归约为mult 3 (2+3)(\y -> 3 * y) (2 + 3)(\y -> 3 * y) 5。这里教授讲了一个lambda只有在被apply的时候,才会对其内部的东西进行计算,也就是no evaluation under lambda。

call-by-value容易造成陷入无限循环,因为它必须做完所有的求值。例如fst (0, inf),设inf = inf + 1,很显然call-by-value并不能结束(terminte),而call-by-name能够将inf“短路”掉返回0。此外,我们还可以想到之前的无限列表。
call-by-name相比call-by-value效率就会低一点了,它需要稍多一点的步骤。

综合两种求值顺序的优点

Lazy evaluation通过call-by-name和sharing的方式综合了两者的优点。
例如square (1+2),可以归约为(1+2) * (1+2),由于这里重复了(1+2),所以可以使用late binding的原理,进行下面的归约

   square (1+2)
=> let n = (1+2) in n*n
=> let n = 3 in 3*3
=> 6

lazy evaluation依赖于改变计算先后不影响计算结果

bottom

下面比较两个函数

filter (<=5) [1..]
takeWhile (<=5) [1..]

这两个函数有什么区别呢?
在GHCI中运行第一个函数,发现lazy evaluation并没有发生,其结果可以表示为

1: (2: (3: (4: (5: _|_))))

这里的_|_即⊥,称为bottom,在之前的课程中也出现过,表示something that won’t terminate。
而第二个函数则能够正常结束

1: (2: (3: (4: (5: []))))

strict application

可以用($!),称为strict application运算符来强制计算函数的参数

f $! _|_ = _|_
f $! x = f x

对于有多个参数的情形,可以按照以下方法

(f $! x) y -- 强制计算 x
(f x) $! y -- 强制计算 y
(f $! x) $! y -- 强制计算 x和y

有的时候强制计算的eager evaluation反而是更好的,例如

-- lazy
sumWith v [] = v
sumWith v (x:xs) = sumWith (v+x) xs
-- strict
sumWith v [] = v
sumWith v (x:xs) = (sumWith $! (v+x) ) xs

这两者的计算结果都是6,但是中间过程会有区别。事实上,strict版本会更加节省空间,因为如果我们对lazy版本展开会发现存在以下两步的推导过程

sumwith (((0 + 1) + 2) + 3) []
((0 + 1) + 2) + 3

所以在每一步计算中,我们都要维护一个逐渐增长的列表。但是如果使用strict版本,我们实际上维护的只有一个累加值。

Ch13 Reasoning about programs

总结与专题论述

Haskell的特性

  1. 柯里化和高阶函数(包括section)
  2. 惰性求值
  3. 模式匹配和guard(包括where)
  4. 类型系统和多态(包括泛型、类型类、抽象代数类型(ADT)、higher kinded polymorphic、type defaulting等)
    具体特性的部分解释可以查看这个网站
  5. Monad(包括ST Monad)
  6. 强类型、静态类型

有关多态

多态(polymorphism)在C++/Java等面向对象语言中常指子类多态(Subtype polymorphism),也就是在继承关系中子类可以修改或者扩展父类中的方法,但此时在包含关系上它也被视作是父类型的对象。例如在C++中调用虚函数时会根据当前this的类型查阅虚函数表从而选择正确的函数,这个多态是在运行期的。在Real World Haskell一书中指出Haskell虽然不具有子类(subtype)多态,但它有类型多态和参数多态。类型多态是我们之前提过的higher kinded polymorphic(注意区别higher rank polymorphic),比如Haskell中的列表[]就是类型多态的,因为我们常常可以见到如map这样的函数中出现[a],也就是说我们不关心a到底是什么,这里的[]也被称为一个type constructor。与此同时我们称map :: (a -> b) -> [a] -> [b]为参数多态(Parametric polymorphism),因为map接受的参数可以是符合其signature的任意(unconstrained 的)类型的。Ad-hoc多态强调一个值对应于不同类型时拥有分别的定义。显而易见的,函数重载也被视为一种Ad-hoc多态,一个例子是

1
2
3
4
5
6
7
8
// https://www.jianshu.com/p/b641cf2908cf
class BasicEq a where
isEqual :: a -> a -> Bool

instance BasicEq Bool where
isEqual True True = True
isEqual False False = True
isEqual _ _ = False

有关Parametric polymorphism、higher kinded polymorphism和higher rank polymorphism的概念我们将在另外一篇文章中进行探讨。

备注

在学习完这本书后,能够对Haskell的关键概念有比较清晰的理解,但是如果需要应用Haskell编程还有一些困难,这时候可以再看看另一本很好的书《Haskell趣学指南》
此外,我这个笔记其实有部分的碎碎念,这导致笔记的逻辑可能不太连贯。但是我还是记录下这部分,如果有和我一样在某些地方钻了牛角尖的,至少我这里能给出我的一些见解。

【未完待续】

Reference

  1. http://learnyouahaskell.com
  2. https://www.zhihu.com/question/19804597
    Church 编码
  3. https://faculty.iiit.ac.in/~venkatesh.choppella/popl/current-topics/lambda-calculus-2/index.html
    Church 编码