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中会看到部分函数，例如head、tail是如何实现的

  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)

    这里receiver和arguments不是等价的参数，一切围绕receiver对象为基础

  • Haskell 

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

    这里receiver和arguments是等价的参数，可以更方便地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)
    如果不加上$，那么g和x都会被当成一个二元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根据type、data等语句定义。
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'

    注意putStr的p和putChar的p是并排的，又比如

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

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

     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。这个一元函数的作用是将自己的参数b和add的参数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)——这里概念有点乱的话是正常的，可先查看instance与type的相关章节——我们注意到实例m受到Ad-hoc多态的typeclass Monad的约束，但它自己确是类型多态的，因为它可以是任意的类型a。

常用的typeclasse有

  • Eq：表示能判断相等的类型
    • Num：表示数字，不继承Ord。Num没有(/)
      • Real：实数，继承了Ord
        • Integeral：整型
  • Ord：表示能比较大小的类型
    特别注意，Ordering是一个类型，包含GT、LT、EQ三个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}域中只能够访问x和y，但guard1、guard2、blah1、blah2都能访问{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 x和f这两种写法在语义上是等价的。
但实际上第一段代码要比第二段代码要快，这是因为第一段代码满足了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中，例如实现head和tail

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))

现在我们试图特化g为add，可以记住一条简单的规则偏应用的定义式右部必须出现原函数，例如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

上一章讲了如何使用递归来实现某些函数，这章学习通过高阶函数如map、filter、foldr来实现它们
高阶函数(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中分为foldl和foldr，其中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)：一个接受a和b类型参数并返回b类型参数的函数
  2. b：归约到的类型
  3. t a：这个表示一个t a的类型。这里t表示一个Foldable的类型。
    在C++中有叫模板参数的东西，例如std::vector<int>表示一个用int特化的向量表vector。Haskell中的t a类似于这个，其中t对应着类模板vector，a对应着类型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 = (&&)的性质被短路，所以能够返回。但是foldl的f在内部，而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类型的x和b类型的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

unfoldr为foldr的对偶函数，定义为

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

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

unfoldr具有性质

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

scanl

scanl和foldl非常相似，只不过它是“扫描”获得列表，而不是将列表“折叠”起来

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

更多的高阶函数

all、any、takeWhile（常常被用来读无尽列表）、dropWhile

fmap

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

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。
如果我们把fmap的f替换成[]，便可以发现map实际上是fmap对list即[]的特化。

instance Functor [] where  
    fmap = map

Ch8 Functional Parsers

在官网上下载的PPT中第8章是Declaring Types and Classes，但实际上这章在课程中被放到了第10章。本章是Functional Parsers，会讲授重要的概念Monads，于是教授穿了件自己设计的（密集恐惧症）衣服
这一章会有点突兀，有比较多的没学过的东西，在我学习的过程中，最让我感到困惑的并不是Monad本身，而是教授讲授时定义的复杂的类型，例如即将看到的IO a和Show 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章会有介绍，Nothing和Just a是Maybe a的两个constructor，它们看起来像为C++中的enum，但实际上更类似于C++中的构造函数。Maybe一个类型可以从Nothing构造，但返回一个非Nothing的值a时就需要返回Just a。
Nothing很好理解，类似于其他语言中的null、None、nil
在没学习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里面的item和parse函数。

在下面两节将要介绍>>=运算符，这个运算符和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 b。forall关键字来自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，将a从M 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 <- item，item是语法分析器，类型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，实际上Functor和fmap是紧密联系的，一个能被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)**，因为a被f包装了起来。从定义中可以看出，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 -> c，g :: 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 f、fmap f x、f <$> 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}
    这里面用到了let和let...in两个不同的结构块。

>>=

  1. return a >>= f = f a
    这个性质相当于是将一个普通值a穿上Monad的衣服，传给一个函数f，相当于直接调用这个函数f a
  2. m >>= return = m
    这个性质是因为对于一个Monad m，m >>= 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)

根据上面的分析，其中x和y是Char类型，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++中的typedef或using。

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类型，其中True和False是具有一个Bool类型的值的constructor。True和False还可以被称为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的定义外部对Circle和Rect进行“特化”。

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

由于Haskell很难添加一个subtype到已有的type中，例如想要给Shape加上一个Polygon的subtype是不容易的，但是用上面这种“虚函数”的方式确实简单的。这和C#等OOP语言是截然相反的，OOP的语言往往继承是容易的（假设去掉sealed），但是给一个写好的类里面增改一个虚函数确实不容易的。这是一种难以两全其美的问题，有许多论文研究这点。
上面的代码中，Circle和Rect被看做类型Shape的“构造函数”(constructor functions)。
特别注意，Circle和Rect是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可以看做一个返回值的函数
    例如本章讲的Circle和Rect，它们都能够返回一个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 :: Nat和Succ :: 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等于n次Succ m，不过这种方法还是需要转换，于是有下面的方法

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

我们把n看做常数，将add转换为一元函数g，Succ类比做+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

然后定义一个apply，apply将一个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，这里将Add、Mul等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::Expr和r::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 编码