人生苦短,快来学 Elixir - 上

2021-04-11
·
35 min read
a purple water drop in the center, representing the Elixir programming language logo

前言

一直都想正经学习一门函数式的语言,于是最近选定了 Elixir 深入了解学习了一下,发现除了有别于传统命令式编程和面向对象编程的函数式编程带来的思维冲击以外,Elixir 整个的语言设计都非常让人愉悦,比起 Python 可能这才是更符合 “人生苦短” 这句话的编程语言(逃

所以接下来想写几篇文章记录 Elixir 中语法上的 Highlights 以及其相关的生态。如果以前从来没接触过函数式编程的同学,可以重点看看模式匹配、递归这两个部分,感受一下函数式的思维和一般的命令式的思维有什么不一样。

变量的不可变性 | Immutability

函数式推崇的变量不可变性,使得我们在写 C Java Python 之类语言的很多思维不再适用,例如下面一个数组求和的例子:

def sum(nums):
    result = 0
    for i in nums:
        result += i
    return result

但这在 Elixir 中完全行不通,因为变量 result 的值始终是不可改变的,我们最多只能将该变量绑定到另外一个值上,但绝不可能实现更改值。

说到这想起了前段时间在纸糊上看到的梗,可以说很好的诠释了 immutability。

immutability joke

而如今很多现代化的语言或框架都在尽可能拥抱 immutability,例如 React 中 State,Rust 默认变量不可变,Kotlin 也推荐优先用不可变的变量。

头等函数 | First-class Functions

函数作为头等公民,可以作为变量的值,也可以作为函数的参数,这在很多现代化的语言中都得到了实现。而函数在 Elixir 中的地位是更加重要,甚至连 + - * / 这些运算符其实也是函数。一个完整的函数名类似 Module.func/1,包括了所属模块名,函数名,以及参数个数,因此可以实现基于函数参数个数的重载。

匿名函数与函数引用 | Annoymous Functions and Function References

在 Elixir 中的很多操作都是依靠各种函数的组合实现的,函数也经常作为参数传递给另一个函数,例如下面一个例子,将列表 [1, 2, 3] 的每一个元素求平方并返回一个新的列表

Enum.map([1, 2, 3], fn x -> x * x end)

有时候我们的匿名函数可能仅仅是调用了另一个函数,或者只是一个简单的表达式,Elixir 提供了使用 & 创建函数引用的特性

Enum.each([1, 2, 3], &IO.puts/1) # 将列表中的每个元素打印输出
Enum.map([1, 2, 3], &(&1 * &1)) # 将列表中的每个元素平方后返回新的列表, &1 代表匿名函数的第一个参数

闭包 | Closures

若匿名函数引用了外部作用域的变量,则该匿名函数将持有的是一份外部变量的拷贝,即外部变量所绑定的值发生改变不会影响匿名函数内的变量值。

num = 0
my_func = fn -> IO.puts(num) end
num = 1
my_func.() # 0

类型系统 | Type System

Elixir 提供了一些非常基础的数据结构类型,今后的一切数据抽象都将由这些基础类型构建起来。

原子 | Atom

Atom 是值为其名字本身的常量,如果了解 LISP 的话,其实这就是 LISP 当中的 Symbol,通常一个 atom 以 : 开头,Atom 在 Elixir 中的用途非常广泛,其可以用作枚举常量,例如 :apple :orange :melon 或者是用在函数的返回结果中,例如 {:ok, result} {:error, reason}。 两个名字完全一样的 atom 即判定为相等,即 :apple == :apple :apple != :orange,因此 Elixir 中并不提供单独的布尔类型,而是直接用 :true :false 两个 atom 来表示,Elixir 的空值 :nil 也是一个 atom,对于这几个常用的 atom,可以省略前面的冒号直接写成 true false nil

元组 | Tuple

元组是 Elixir 中非常常用的一种数据,是一种有序且长度固定的数据结构,例如 person = {"Tom", 16"}

Elixir 很多函数的返回值也是一个类似 {:ok, result} 或者 {:error, reason} 的元组,结合后文将会介绍的模式匹配可以实现非常优雅的错误处理。

Rust 中用 Result 处理错误非常类似,不过 Rust 的应该叫做 Algebraic Data Type

列表 | List

Elixir 中的列表是一种动态且长度可变的数据集合,例如 [1, 2, 3, 4, 5]

其底层实现实际为单链表,所以对于列表的绝大多数操作,比如求长度,随机访问元素等操作都具有 O(n)O(n) 的时间复杂度。

同样基于该特性,列表还可以定义为 list = [head | tail],其中 head 可以是任意类型的元素,而 tail 必须是一个列表,因此上面的例子还可以递归的写成 [1 | [2 | [3 | [4 | [5 | []]]]]]

通过 hd/1tl/1 函数可以分别取出列表的头和尾,该操作的时间复杂度均为 O(1)O(1)

++ 操作符可以拼接两个列表。

Map

Map 是 Elixir 中非常重要的一种数据类型,今后的数据抽象很大程度依赖 Map 实现,甚至 Elixir 中的结构体实质上都是一个 Map。

我们可以通过 %{1 => 1, 2 => 4, 3 => 9} 这样的字面量来创建 Map, 也可以通过 Map 模块提供的函数 Map.new/1 来创建 Map, 例如 Map.new([{1, 1}, {2, 4}, {3, 9}]),可以看到我们传入了一个列表作为参数,列表的每个元素都是一个二元的元组,分别代表一个键值对。

因为 Elixir 中标识一个函数必须明确函数参数的个数,所以 Elixir 的函数不支持变长参数,因此上面各个元组需要包裹在一个列表里作为参数传递进去。

我们可以很方便的用 map[key] 这样的形式来获取值,这相当于调用了 Map.get/2 函数,如果元素不存在则返回 nil,可以使用 Map.get/3 来指定一个元素不存在时的默认值,例如 Map.get(map, key, :not_found),若元素不存在则返回 :not_found

另外还可以使用 Map.fetch/2 来获取元素,区别在于其返回值会以元组 {:ok, result}{:error, reason} 的形式返回。

若使用 Map.fetch!/2 来获取元素,若元素不存在则会抛出一个 KeyError 的错误。

习惯上,Elixir 中的变量或函数结尾带有问号,则表示其值或返回值为布尔类型,若一个函数以感叹号结尾,则表明这个函数为抛出错误。

当一个 Map 的所有键都是 atom 的时候,例如 %{:name => "Tom", :age => 16},我们除了可以用 map[:key] 来获取元素意外,还可以使用 map.key 这样的语法来获取元素。

这样的 map 还可以直接通过 %{name: "Tom", age: 16} 的语法来创建。另外,如果要更改某个键值对的值,可以使用 %{person | age: 17}

Binaries

Elixir 中还有一种用来表示一串字节或比特位的数据类型,例如 <<1, 2, 3>>

其中的每一个十进制的数字值便代表了对应的字节,通过 <> 操作符可以连接两个 binary。

字符串 | String

字符串在 Elixir 中也并不是一种特殊的数据类型,其有两种不同的实现。

一种是通过 binary 实现的字符串,其字面量形式和其它语言的字符串没什么区别,都是用双引号引起来,用 \ 进行字符转义。

此外 Elixir 的字符串支持表达式插值,例如 "one plus one is #{1 + 1}"

另一种字符串是通过字符列表实现的,本质是一个整数列表,用单引号引起来,即 'ABC' == [65, 66, 67],但同样支持表达式插值。

另外 Elixir 当中还提供了一种叫做魔符Sigils)(非常中二的名字,不愧是名叫圣水的语言)的东西,可以用来便捷地创建某种数据类型,例如 ~s(This is a test) 会生成 "This is a test",其同样支持表达式插值。

此外还有一个大写的版本 ~S("To be or not to be, that is a question." - Shakespare),这个魔符不会处理内嵌的表达式以及会自动转义字符。

上面两个魔符生成的都是 binary 实现的字符串,对应的字符列表字符串版本的魔符为 ~c()~C()

Elixir 内建的还有用来生成日期时间和正则表达式的魔符,其实魔符就相当于一个宏。

高阶数据类型 | High-level Data Types

除了上述的基本数据类型,Elixir 还提供了一些建立在基本类型之上的高阶数据类型,下面介绍区间和关键字列表这两种类型。

区间 | Ranges

区间是一系列连续的整数,通过类似 1..10 的语法创建,可以用 1 in 1..10 来判断某个数是否在区间内,同时区间也是可迭代对象。

关键字列表 | Keyword Lists

如果一个列表形如 [{:key1, 1}, {:key2, 2}, {:key3, 3}],则其便是一个关键字列表,可以用更简洁的语法写作 [key1: 1, key2: 2, key3: 3],还可以直接用 list[:key] 这样的语法来取出对应的值。

但要记住其本质还是个列表,取元素操作的时间复杂度依然是 O(n)O(n)

关键字列表常用作函数的可选参数,例如下面这个例子

# \\ 表示指定参数默认值
def func(arg1, arg2, opts \\ []) do
  ...
end

func(arg1, arg2, [opt1: 1, opt2: 2])
func(arg1, arg2, opt1: 1, opt2: 2)

有了关键字列表,我们就可以向函数传入一系列可选的自定义参数,在传参的时候,列表的方括号甚至都可以省略掉,但实际上整个列表还是作为一个参数传进去的。

模式匹配 | Pattern Match

模式匹配可以说是 Elixir 的灵魂所在,借助模式匹配可以便捷地完成许多操作。

曾有人戏说写代码的一大痛苦在于如何给变量命名,而通过模式匹配可以减少创建很多不必要的中间变量。

在其它大多数的语言当中,我们很熟悉类似 num = 0 这样的表达式,其语义为将 0 这个值赋给变量 num,这是一个赋值表达式。

而在 Elixir 当中,= 是匹配运算符,num = 0 这样的表达式是在进行模式匹配,其左侧是一个模式(Pattern),右侧是要匹配的值。

变量绑定

在 Elixir 当中,num = 0 是在进行模式匹配,若左侧的模式是一个变量,则一定匹配成功,则右侧的值会绑定在变量 num 上面,并且整个表达式会返回右侧的值。

左侧的模式可以为一个常量,例如 1 = 1 匹配成功会返回右侧的值,即整个表达式返回 1,而 2 = 1 则匹配失败,会抛出 MatchError

如果想要将某个变量的值用来进行匹配,可以用 ^ 操作符,例如 当num 的值已经是 1 了,执行 num = 2 能够成功匹配,因为其左侧是一个变量,一定匹配成功,并将右侧的值 2 绑定在了变量 num 上,而执行 ^num = 2 则匹配失败,因为这样会将 num 变量的具体值用来与右侧匹配。

左侧的模式不仅仅只能是一个变量或常量,还可以是更复杂的结构,例如下面的一些例子:

# 左侧是一个列表的结构,能够与右侧的值匹配
# 匹配成功后,first 的值绑定为 1,second 的值绑定为2
# 用下划线或者以下划线开头的变量名来表示不需要将匹配到的值绑定在变量上
# 匹配成功后整个表达式返回的是右侧的值,即 [1, 2, 3, 4, 5]
[first | [second | _]] = [1, 2, 3, 4, 5]

# 左侧是一个 map 的结构,只要左侧作为模式的 map 当中含有
# 右侧的 map 当中的键,即可匹配成功
# name 变量的值绑定为 "Tom", age 变量的值绑定为 17
%{name: name, age: age} = %{name: "Tom", age: 17, city: "LA"}

使用 case 匹配

通过 case 可以通过模式匹配的不同结果执行不同的分支语句,例如:

person = %{name: "Tom", age: 17}
case Map.fetch(person, :city) do
  {:ok, city} -> "#{person.name} lives in #{city}"
  :error -> "Cannot find the city of #{person.name}"
end
# "Cannot find the city of Tom"

而一般的大多数语言的 switch-case 只能对常量进行匹配。

多分支函数 | Functions with Multiple Clauses

在函数接收参数的时候,我们同样能够进行模式匹配,例如下面一个计算面积的函数:

defmodule Geometry do
  def area({:circle, r}) do
    r * r * 3.14
  end
  def area({:rectangle, a, b}) do
    a * b
  end
  def area({:square, a}) do
    a * a
  end
end

Geometry.area({:circle, 3})
Geometry.area({:rectangle, 1, 2})
Geometry.area({:square, 4})

可以看到我们定义了一系列的 Geometry.area/1,它们属于同一个模块,函数名相同,且函数参数个数相同,因此它们是同一个函数的定义,唯一不同的便是在函数参数的模式不同,这样的函数叫做多分支函数。

在调用这样的函数的时候,首先会对传入的参数进行模式匹配,然后根据匹配的结果选择调用对应的分支,如果匹配不成功则抛出错误。

看到这里你可能会觉得,我们同样可以就传入一个 object 参数,然后在函数内部用 case 做模式匹配调用不同分支语句。其实这样也可以,但 Elixir 当中更普遍的做法是采用多分支函数,具体的好处在后面的尾调用和尾递归部分才会体现出来。

枚举模块和流模块 | Enum Module and Stream Module

可以看到 Elixir 当中的许多基础数据都是可迭代的集合类型,因此 Elixir 内建的 Enum 模块提供了非常多的对集合的操作函数,例如下面的一个例子:

Enum.map([1, 2, 3, 4, 5], &(&1 * &1 + 1)) # [2, 5, 10, 17, 26]

除了 map 以外,还有非常多的实用的函数,例如获取集合中某个索引位置的元素,获取最大最小值,排序,过滤等操作,具体可以参见官方文档。

Enum 模块中的操作都是立刻执行的,有时候我们可能会连续对某个集合进行多次变换操作,如果集合的数据量非常大,那么多次遍历操作会带来性能开销,因此 Elixir 还提供了一个 Stream 模块,能够实现对集合类型的惰性操作,这个模块所支持的函数几乎和 Enum 模块一致。

需要注意的是,在文章开头便提到了 Elixir 当中很重要的一个概念,即数据的不可变性,Enum 模块当中的所有操作都不会改变传入的原始集合类型,而是每次都返回一个完成操作后的新的集合。 有人可能会觉得,每次都返回一个新的集合,如果每次都要在内存上分配一块新的空间,然后把数据拷贝过去,也会造成很大的性能开销,关于这个问题的解释是:Elixir 所运行在的 BEAM 虚拟机不会每次都完全拷贝一份原来的数据,而是会尽可能的复用已经存在的数据,更具体的细节可能需要去了解 Erlang 的 BEAM VM...

运算符 | Operators

管道运算符 | Pipe Operator

使用过其他语言当中的函数式编程特性的同学可能会对 map filter reduce 之类的高阶函数的调用比较熟悉,比如下面一个 Java 当中 StreamAPI 的例子:

Arrays.asList(1, 2, 3, 4, 5, 6).stream().map(x -> x * x + 1).filter(x -> x % 2 == 1).forEach(System.out::println);

可以看到我们通过一些列的链式调用对原始的数组中的数据进行变换,最终输出。需要注意的是 map filter forEach 等都是 Stream 对象才具有的方法,因此我们必须将数据转成 Stream 类型后才能使用这些方法。

再来看看 Python 当中同样的例子:

nums = list(filter(lambda x: x % 2 == 1, list(map(lambda x: x * x + 1, [1, 2, 3, 4, 5, 6]))))
for i in nums:
    print(i)

可以看到 Python 当中的几个高阶函数都是全局的函数,无法对数据进行链式调用,看上去可读性很差。

那最后再来看看 Elixir 当中同样的例子:

[1, 2, 3, 4, 5, 6]
|> Stream.map(&(&1 * &1 + 1))
|> Stream.filter(&(rem(&1, 2) == 1))
|> Enum.each(&IO.puts/1)

Elixir 当中提供了管道运算符 |>,用途跟 Shell 里的管道 | 非常类似,即将运算符前的表达式输出作为运算符后的函数的第一个参数,通过管道运算符搭配 EnumStream 模块,我们可以很方便的实现链式调用。使用管道运算符的好处还有就是,我们可以使用任意函数在调用链里面,而不仅仅局限于内建提供的这些函数。

使用 EnumStream 模块配合 |> 来操作数据是 Elixir 当中非常常见的一种模式。

布尔运算符 | Boolean Operators

在 Elixir 当中,只有 :nil:false 这两个 atom 被视为假值,其它的数据都被视为真值。

Elixir 当中提供了 && || ! 三个布尔运算符。

因此我们可以实现类似于下面例子的操作:

some_data = read_cached || read_from_disk || read_from_database
database_value = connect_established? && read_data

需要注意的是,Elixir 中的非匿名函数调用时的括号是可选的,也就是说 func() 可以直接写成 funcfunc(1, 2, 3) 可以直接写成 func 1, 2, 3,而匿名函数的调用则必须要加括号,并且函数名后还必须要加一个点,例如 func.(1, 2, 3)。 为了更好的可读性和避免造成歧义,大多数情况下推荐总是把函数调用的括号写出来,所以上面例子中的 read_cached 等等都是在调用函数。

上面的第一个例子,我们先试图调用 read_cached 来读取数据,若 read_cached 返回假值则再调用 read_from_disk

第二个例子当中,先调用 connect_established? 判断是否建立数据库连接,若返回假值则后续表达式便不会再执行。

推导式 | Comprehension

熟悉 Python (or Haskell) 的同学对这个特性一定不会陌生,例如在 Python 当中,我们可以通过下面的表达式来生成集合:

[(x, y) for x in range(1, 4) for y in range(1,4)]
# [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

Elixir 当中同样也能实现:

for x <- 1..3, y <- 1..3, do: {x, y}
# [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}]

个人觉得 Elixir 的写法可读性更好一点,特别是把 <- 这个符号看成 \in 的时候。

当然,我们还可以将无处不在的模式匹配运用起来,例如:

values = [good: 1, good: 2, bad: 3, good: 4]
for {:good, n} <- values, do: n * n
# [1, 4, 16]

另外推导式还支持过滤数据,例如:

for n <- 0..5, rem(n, 3) == 0, do: n * n
# [0, 9]

再来看看下面一个更加复杂的例子:

dirs = ['/home/tunkshif/Downloads', '/home/tunkshif/Documents']
for dir <- dirs,
    file <- File.ls!(dir),
    path = Path.join(dir, file),
    File.regular?(path),
    do: {file, File.stat!(path).size}
# [
#   {"abc.docx", 13676},
#   {"abc.zip", 955557},
#   {"xxx.zip", 57758},
#   {"xxx.pdf", 531049},
#   {"xxx.md", 1148}
# ]

上述代码功能是将 dirs 列表中的目录下的所有文件以 {文件名, 文件大小} 的形式列出来。

推导式默认生成出来的数据结构都是列表,我们也可以自己指定最终生成的数据类型:

for dir <- dirs,
    file <- File.ls!(dir),
    path = Path.join(dir, file),
    File.regular?(path),
    into: %{},
    do: {file, File.stat!(path).size}

最终生成出来的是一个 map。

尾调用和尾递归 | Tail-call and Tail-recursive

递归代替循环

函数式编程语言中一般不提供直接的循环手段,而是采用递归来实现循环。

举个例子,如果我们想要实现一个函数,能够把数字 1 到 n 打印出来,按照命令式的语言,我们可能会写出下面这样的代码:

void print_n(int n) {
    for (int i = 1; i <= n; i++ ) {
        printf("%d", i);
    }
}

可以看到我们在函数内部新建了一个用来计数的变量 i,每输出打印一次结果便把 i 的值增加 1,可以看到变量 i 的值一直在发生改变,是和文章开头提到的变量不可变性相违背的。

那么如何用递归实现上述的函数,观察下面一个例子:

defmodule Test do
  def print(1), do: IO.puts(1)
  def print(n) do
    print(n - 1)
    IO.puts(n)
  end
end

可以看到上面的例子依赖于模式匹配,多分支函数,递归等特性,如果传入参数为 1,则将 1 输出,否则就将 n - 1 输出,再输出 n 本身。

再看看下面一个将列表个元素累加求和的例子:

defmodule Test do
  def sum([]), do: 0
  def sum([head | tail]) do
    head + sum(tail)
  end
end

同样还是用到了模式匹配,多分支函数的特性,如果传入的参数为一个空列表则返回 0,如果列表非空,则将列表的第一个元素和剩余部分通过模式匹配提取出来,将第一个元素的值与剩余列表递归相加。

如果我们想要实现无限循环,那应该怎么办呢?答案就是递归调用一个函数本身,例如下面的例子:

defmodule Test do
  def loop() do
    IO.puts('yes')
    loop()
  end
end

例:快速排序

可能大家刚学排序算法的时候,总会感觉好像排序的原理听上去挺容易的,用 C/Java/Python 等等语言实现起来怎么就这么困难呢,接下来我们看看在函数式的语言当中,排序算法实现起来是怎样的。

首先回顾一下快排的流程:

  1. 从数列中挑出一个元素作为基准pivot
  2. 对数列排序,使得所有比基准值小的元素处于基准之前,所有比基准值大的元素处于基准之后。在这之后,基准元素处于数列的中间位置,完成了分区partition)操作。
  3. 递归地对基准两侧的子列进行上述操作的排序。

我们就选取待排序数列的第一个元素作为基准来进行排序~~(因为这样写起来最简单~~

注意:这个快排的例子仅作一个演示,因为 Elixir 中的列表实际实现为单链表,所以快排并不是最优方案,Elixir 内建的排序函数 Enum.sort 实际上使用的是归并排序。

defmodule QuickSort do
  def sort([]), do: []
  def sort([head | []]), do: [head]
  def sort([pivot | rest]) do
    smaller = Enum.filter(rest, &(&1 < pivot))
    larger = Enum.filter(rest, &(&1 > pivot))
    sort(smaller) ++ [pivot] ++ sort(larger)
  end
end

# 生成一个长度为 10,数字范围在 1 到 100 的随机数列表并将其排序
1..10 |> Enum.map(fn _ -> Enum.random(1..100) end) |> QuickSort.sort()
# [7, 29, 30, 62, 67, 73, 83, 89, 95, 98]

可以看到上面快排的具体实现非常贴近于算法的语言描述,或者说更贴近于算法的本质,而不是像命令式的语言当中,要不断地使用 forwhile 之类的控制流程来循环,还要自己考虑循环的下标等各种细节问题。

(当然用 C/Java/Python 之类的语言手写排序算法还是必须要会的

尾调用尾递归优化

看到这里大家可能会想,每一次调用函数都会产生调用栈,如果递归深度过大,很可能会爆栈,因此 Elixir (实际上是 Erlang) 对函数尾调用做了优化,例如上面的无限循环的例子,在函数体的结尾调用了函数,这样的调用称作尾调用。

经过尾调用优化后的代码实际执行到函数结束的时候调用函数并不会产生新的调用栈,而是更加类似于执行了 gotojump 之类的语句。

而尾递归是一种特殊的尾调用,即在一个函数的结尾递归调用了该函数本身。

例:斐波那契数列

下面来看一个经典的斐波那契数列的例子:

defmodule Fib do
  def fib(0), do: 0
  def fib(1), do: 1
  def fib(n) when is_integer(n) and n > 1 do
    fib(n - 1) + fib(n - 2)
  end
end

1..10 |> Enum.map(&Fib.fib/1)
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

上面的例子很好理解,也是一般初学递归函数时会写出来的样子,但问题在于这个函数不是尾递归的,因为函数体的最后一个表达式 fib(n - 1) + fib(n - 2) 不是一个单纯的函数调用,而出现了运算操作。因此在数据过大的时候会爆栈。

下面来把它改造成尾递归的版本:

defmodule Fib do
  defp do_fib(_a, b, 0), do: b
  defp do_fib(a, b, n), do: do_fib(b, a + b, n - 1)
  def fib(1), do: 1
  def fib(2), do: 1
  def fib(n) when is_integer(n) and n > 2, do: do_fib(1, 1, n - 2)
end

Fib.fib(100)
# 354224848179261915075
Fib.fib(1000)
# 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

经过改造之后,计算斐波那契数列的第 1000 项都可以立刻出结果。下面来具体分析一下:

上面使用 defp 定义了一个模块内部的私有函数 do_fib,用来实际计算数列值。

我们通常的递归实现思路是要设定一个停止递归的条件,例如最开始的版本当中的 def fib(0)def fib(1) 这两个子句便是递归结束的条件,而在尾递归的版本当中,我们把控制递归停止的条件作为了函数的第三个参数 n,即相当于函数其实维护了一个控制递归停止的状态。

defp do_fib(a, b, n) 中的参数 ab 其实分别代表数列中连续的两项 an1a_{n-1}ana_n,每次进行尾递归时,将 ana_na_{n+1}=a_{n-1}+a_{n} 作为参数传入,同时传入的 n 的值也减一,表示剩余的递归次数。

n 减少到 0 的时候,defp do_fib(_a, b, 0) 会被匹配调用,将 b 的结果返回,这里的 b 其实就是数列的 a_n 项。

在调用 do_fib 的时候,我们实际需要传入斐波那契数列的开头两项即 1 和 1。

例:列表元素求和

最开始我们演示了一个列表元素累加求和的例子,但它并不是尾递归的,因为函数最后执行的是 head + sum(tail),含有运算操作,接下来我们也试着把它改造成尾递归版本的。

defmodule Test do
  defp do_sum([], acc), do: acc
  defp do_sum([head | tail], acc), do: do_sum(tail, acc + head)
  def sum(nums) when is_list(nums), do: do_sum(nums, 0)
end

Test.sum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) # 55

类似地,求和函数其实需要维护一个当前总的累加值 acc 的状态,而我们把这个状态直接作为函数的参数传递了进去,因此在实际调用 do_sum 的时候,我们需要一个总和的初始值 0