函数式程序设计（一）——初⻅函数式思维

2022-07-14 约 1122 字预计阅读 3 分钟

列表的操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


> head [1,2,3,4,5]
1
> tail [1,2,3,4,5]
[2,3,4,5]
> [1,2,3,4,5] !! 2
3
> take 3 [1,2,3,4,5]
[1,2,3]
> drop 3 [1,2,3,4,5]
[4,5]
> length [1,2,3,4,5]
5
> sum [1,2,3,4,5]
15
> product [1,2,3,4,5]
120
> [1,2,3] ++ [4,5]
[1,2,3,4,5]
> reverse [1,2,3,4,5]
[5,4,3,2,1]

函数应用

在Haskell中，函数应用使用空格来表示，乘法用星号*来表示。

1

f a b + c*d

Mathematics	Haskell
`f(x)`	`f x`
`f(x, y)`	`f x y`
`f(g(x))`	`f (g x)`
`f(g(x), y)`	`f (g x) y`
`f(x)g(y)`	`f x * g y`

Haskell脚本

用户自己定义的函数在一个script中，由一系列定义组成的文本文件，后缀名习惯用.hs。

当开发一个Haskell脚本时，保持两个窗口的打开是很有用的，一个是运行脚本的编辑器，另一个是运行GHCi。

1
2
3


-- test.hs
double x = x + x
quadruple x = double (double x)

终端中运行ghci test.hs，然后输入double 3，得到6，输入quadruple 3，得到12。

我们不关闭GHCi，然后在test.hs中添加阶乘函数和求均值函数：

1
2
3
4


double x = x + x
quadruple x = double (double x)
factorial n = product [1..n]
average ns = sum ns `div` length ns

注意

div是用反引号括起来的，而不是正引号。
x ``f`` y只是f x y的语法糖。

GHCi不会自动检测到脚本已经被改变，所以在使用新的定义之前，必须执行一个重新加载命令:reload。

1
2
3
4
5
6
7


ghci> ::reload
[1 of 1] Compiling Main             ( test.hs, interpreted )
Ok, one module loaded.
ghci> factorial 5
120
ghci> average [1,1,4,5,1,4]
2

常用GHCi命令

命令	作用
`:load` `name`	加载脚本name
`:reload`	重新加载脚本
`:set editor` `name`	设置编辑器为name
`:edit` `name`	编辑脚本文件name
`:edit`	编辑当前脚本
`:type` `expr`	显示表达式expr的类型
`:?`	列出所有命令
`:quit`	退出GHCi

函数式思维

使用数学中的函数作为求解信息处理问题的基本成分。

从零开始定义一些基本函数
把已有的函数组装起来，形成新的函数

自然数上的 `fold` 函数

plus、mult、expn这三个函数之间存在共性，这种共性可以被封装在一个函数中。

$$ \begin{aligned} foldn&:(A\rightarrow A) \rightarrow (A \rightarrow (\mathbb{N} \rightarrow A)) \\ foldn(h)(c)(0)&\doteq c \\ foldn(h)(c)(succ(n))&\doteq h(foldn(h)(c)(n)) \\ \end{aligned} $$

可知

$$ \begin{aligned} h&:A\rightarrow A \\ c&:A \\ \end{aligned} $$

给定函数$h:A\rightarrow A$和值$c:A$，令$f=fold(h)(c)$，则由上述定义可知：

$$ \begin{aligned} f(0)&\doteq c \\ f(succ(n))&\doteq h(f(n)) \\ \end{aligned} $$

注意

从另一个角度理解$foldn$函数：

给定一个自然数$n$，可知：
$$n=(\underbrace{succ\cdot succ\cdots succ}_\text{n $succ$ functions})(0)$$
已知$f=foldn(h)(c)$，可知：
$$f(n)=(\underbrace{h\cdot h\cdots h}_\text{n $h$ functions})(c)$$

利用foldn函数，可以对plus、mult、expr进行更简洁的定义：

$$ \begin{aligned} plus&:\mathbb{N}\rightarrow (\mathbb{N}\rightarrow \mathbb{N}) \\ plus(n)&\doteq foldn(succ)(n) \\ m&=(\underbrace{succ\cdot succ\cdots succ}_\text{m $succ$ functions})(0) \\ plus(n)(m)&=(\underbrace{succ\cdot succ\cdots succ}_\text{m $succ$ functions})(n) \\ \end{aligned} $$

$$ \begin{aligned} mult&:\mathbb{N}\rightarrow (\mathbb{N}\rightarrow \mathbb{N}) \\ mult(n)&\doteq foldn(plus(n))(0) \\ mult(n)(m)&=(\underbrace{plus(n)\cdot plus(n)\cdots plus(n)}_\text{m $plus(n)$ functions})(0) \\ \end{aligned} $$

$$ \begin{aligned} expr&:\mathbb{N}\rightarrow (\mathbb{N}\rightarrow \mathbb{N}) \\ expr(n)&\doteq foldn(mult(n))(1) \\ expr(n)(m)&=(\underbrace{mult(n)\cdot mult(n)\cdots mult(n)}_\text{m $mult(n)$ functions})(1) \\ \end{aligned} $$

`fact`函数

为了使用foldn函数定义fact和fib函数，首先引入两个辅助函数：

$$ \begin{aligned} outl&:A\times B \rightarrow A \\ outl(a,b)&\doteq a \end{aligned} $$

$$ \begin{aligned} outr&:A\times B \rightarrow B \\ outr(a,b)&\doteq b \end{aligned} $$

fact函数定义如下：

$$ \begin{aligned} f&:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}\times \mathbb{N} \\ f(m,n)&\doteq (m+1,(m+1)\times n) \\ fact&:\mathbb{N}\rightarrow \mathbb{N} \\ fact(n)&\doteq outr\cdot foldn(f)(0,1) \\ \\ m&=(\underbrace{succ\cdot succ\cdots succ}_\text{m $succ$ functions})(0) \\ fact(m)&=outr((\underbrace{f\cdot f\cdots f}_\text{m $f$ functions})(0,1)) \\ \end{aligned} $$

`fib`函数

$$ \begin{aligned} g&:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}\times \mathbb{N} \\ g(m,n)&\doteq (n,(m+n)) \\ fib&:\mathbb{N}\rightarrow \mathbb{N} \\ fib(n)&\doteq outl\cdot foldn(g)(0,1) \\ \\ m&=(\underbrace{succ\cdot succ\cdots succ}_\text{m $succ$ functions})(0) \\ fib(m)&=outl((\underbrace{g\cdot g\cdots g}_\text{m $g$ functions})(0,1)) \\ \end{aligned} $$

序列（List）以及序列上的`fold`函数

TBD

List 相关函数的重定义

TBD

一种排序算法

TBD

目录