《Elixir 程序设计》笔记

第7章 列表与递归

Elixir 列表的“头尾”递归定义

在常规语言中，列表通常被看作可遍历的阵列。但在函数式语言 Elixir 中，递归才是处理列表的最佳工具。

Elixir 的列表在底层是单向链表，它的定义是递归的：一个非空列表总是由一个头部（Head）和一个尾部（Tail）组成。

:pushpin: 列表的拆解与构造规则

• 空列表：记作 []。
• 头部（Head）：列表中的第一个元素（可以是任何类型的值）。
• 尾部（Tail）：除第一个元素外剩下的所有元素组成的列表（注意：尾部本身必须是一个列表）。
• 管道符 |：用于在语法上分隔或连接头部和尾部。

:input_numbers: 列表构造的层层嵌套示例

通过管道符 |，任何列表都可以还原为最底层的递归嵌套形式：

标准写法            递归（管道符）等价写法     结构解析
[3]                [3 | []]                 头部是 3，尾部是空列表 []。
[2, 3]             [2 | [3 | []]]           头部是 2，尾部是列表 [3]。
[1, 2, 3]          [1 | [2 | [3 | []]]]     头部是 1，尾部是列表 [2, 3]。

在交互式命令行（IEx）中输入这种嵌套语法，Elixir 会自动将其还原为标准列表：

iex> [1 | [2 | [3 | []]]]
[1, 2, 3]

:magnifying_glass_tilted_left: 结合模式匹配（Pattern Matching）提取元素

正是由于这种头尾结构，我们可以利用模式匹配非常优雅地拆分列表，或者将值赋给变量：

# 1. 基础全量匹配
iex> [a, b, c] = [1, 2, 3]
[1, 2, 3]
iex> a
1
iex> b
2

# 2. :sparkles: 核心：头尾模式匹配（常用核心技巧）
iex> [head | tail] = [1, 2, 3]
[1, 2, 3]
iex> head
1                    # 提取出了第一个元素
iex> tail
[2, 3]               # 提取出了剩余元素组成的列表

使用“头部和尾部”处理列表

在 Elixir 中，通过模式匹配 [head | tail] 处理列表是最基础、最核心的模式。它允许我们在函数参数中直接解构数据。

defmodule MyList do
  # 形式 1：处理边界（基准条件）
  def len([]), do: 0

  # 形式 2：处理解构与递归递推
  def len([head | tail]), do: 1 + len(tail)
end

第二个形式较难适应，主要是因为初学者容易陷入以下几个思维误区或细节陷阱：

• 1. 语法符号的重叠：管道符 | 在这里不是用于“连接”列表，而是作为模式匹配的分隔符，用来强行将列表剥离成“独立元素”和“剩余列表”。
• 2. 未使用变量的警告（Warning）：在上面的写法中，我们在参数中解构出了 head，但在函数体 do: 1 + len(tail) 中完全没有用到 head。这在 Elixir 中会触发编译器的“未使用变量”警告。
• 3. 更严谨的优化写法：为了解决这个麻烦，在实际生产中，我们会使用下划线 _ 来忽略不需要的头部变量，使意图更加清晰：

   def len([_head | tail]), do: 1 + len(tail)
   # 或者直接：
   def len([_ | tail]), do: 1 + len(tail)

IEx 交互式命令行显示列表的“试探机制”

在 Elixir 中，使用单引号包裹的文本（如 ‘cat’）被称为 查理斯特（Charlists，即字符列表）。它在系统底层的本质不是真正的字符串，而是一个包含整数代码点（ASCII/Unicode 码点）的列表。例如，’cat’ 实际上就是由 99 (c)、97 (a) 和 116 (t) 三个整数组成的列表 [99, 97, 116]。

由于底层结构完全相同，这给交互式命令行（IEx）的输出带来了混淆。为了解决这个问题，IEx 采用了一套试探法（Heuristic）来决定如何渲染这类列表。

:pushpin: IEx 显示列表的试探规则

当 IEx 准备在屏幕上打印一个整数列表时，它会执行以下判断逻辑：

• 全员可打印 ➔ 显示为单引号字符列表：如果列表中的所有整数都属于 ASCII 中的“可打印字符”（如字母、数字、常见标点），IEx 就会倾向于人类直观阅读，将其格式化为单引号文本。
• 含不可打印字符 ➔ 降级显示为原始整数列表：只要列表中包含任意一个不可打印字符（例如空字符 0、控制字符等），试探法就会失效，IEx 将老老实实地打印出原生的数字数组。

# :magnifying_glass_tilted_left: 现象一：明明输入的是数字列表，却蹦出了单引号文本
iex> [99, 97, 116]
'cat'
# :light_bulb: 原因：99, 97, 116 对应的 'c', 'a', 't' 全都是合法的可打印字符。

# :magnifying_glass_tilted_left: 现象二：在末尾强行追加一个不可打印字符 0
iex> [99, 97, 116, 0]
[99, 97, 116, 0]
# :light_bulb: 原因：数字 0 不是可打印字符，打破了 IEx 的试探规则，逼迫其原样输出。

:hammer_and_wrench: 生产环境小贴士与避坑指南

• 1. 不要惊慌：在后续编写处理数字（如密码学、字节流、温度传感器数据）的程序时，如果发现明明想要数字列表，命令行却打印出一段古怪的文本，请记住这只是 IEx 渲染上的“视觉把戏”，数据底层的整数值并未发生任何改变。
• 2. 现代标准推荐（双引号）：在 Elixir 中，日常开发中凡是涉及“真正的文本”，一律推荐使用双引号 ""（即二进制型字符串 Binary String）。单引号查理斯特主要用于与底层的老旧 Erlang 库进行互操作。

使用“头尾解构”进行列表转换与构造

在 Elixir 中，利用管道符 | 不仅可以解构（拆分）列表，还能在递归调用中构造（组合）出一个全新的列表。

当我们想要对列表中的每个元素进行某种数学转换时（例如平方或加 1），核心思想是：将原列表头部转换后的新值，作为新列表的头部；然后将原列表尾部递归处理后的结果，作为新列表的尾部。

1. 求平方函数 square/1

defmodule MyList do
  # 规则 1（基准条件）：空列表的平方依然是空列表
  def square([]), do: []

  # 规则 2（递归步骤）：新列表的头部是 head * head，尾部则是 square(tail) 的递归结果
  def square([head | tail]), do: [head * head | square(tail)]
end

2. 元素加 1 函数 add_1/1

defmodule MyList do
  # 规则 1（基准条件）：空列表加 1 依然是空列表
  def add_1([]), do: []

  # 规则 2（递归步骤）：新列表的头部是 head + 1，尾部则是 add_1(tail) 的递归结果
  def add_1([head | tail]), do: [head + 1 | add_1(tail)]
end

测试：

# 测试 square/1 
iex> MyList.square([])
[]
iex> MyList.square([4, 5, 6])
[16, 25, 36]

# 测试 add_1/1
iex> MyList.add_1([1000])
[1001]
iex> MyList.add_1([4, 6, 8])
[5, 7, 9]

高阶函数与代码抽象

仔细观察 square 和 add_1 两个函数，你会发现它们的结构惊人地相似。唯一的区别在于对 head 进行的处理不同（一个是 head * head，一个是 head + 1）。在真实的生产环境和后续的学习中，我们会将这种通用的“遍历并转换”逻辑抽象为一个通用的高阶函数（即 map 映射）。

通用的 map 映射函数与高阶函数

在上一节中，square（求平方）和 add_1（元素加 1）的结构几乎完全相同。为了消除重复代码，我们需要进行泛化（Generalization）。

通过定义一个通用的 map 函数，让它同时接受一个列表和一个函数作为参数，就可以将特定的转换逻辑（如平方、加 1、逻辑判断）动态地应用到列表的每个元素上。这种能接受其他函数作为参数的函数，在函数式编程中被称为高阶函数。

defmodule MyList do
  # 规则 1（基准条件）：如果是空列表，无论传入什么函数，都直接返回空列表 []
  # :sparkles: 技巧：使用下划线前缀 `_func` 忽略未使用的参数，避免编译器抛出警告
  def map([], _func), do: []

  # 规则 2（递归步骤）：新列表的头部是调用 func.(head) 的结果，尾部是继续递归调用 map(tail, func)
  # :warning: 语法细节：调用匿名函数变量时，必须使用「点号」加圆括号，即 `func.(head)`
  def map([head | tail], func), do: [func.(head) | map(tail, func)]
end

通过传入不同的匿名函数（使用 fn … -> … end 结构或 & 快捷符号），map 可以演变成任意我们需要的转换工具：

1. 基础匿名函数写法 (fn)

# ➔ 实现平方转换
iex> MyList.map([1, 2, 3, 4], fn n -> n * n end)
[1, 4, 9, 16]

# ➔ 实现值加 1
iex> MyList.map([1, 2, 3, 4], fn n -> n + 1 end)
[2, 3, 4, 5]

# ➔ 实现条件逻辑判断
iex> MyList.map([1, 2, 3, 4], fn n -> n > 2 end)
[false, false, true, true]

2. :sparkles: 精简的一行流写法 (& 快捷符号)

在 Elixir 中，可以使用 &(…) 和参数占位符 &1 来极大地简化匿名函数的编写：

# ➔ 使用快捷符号实现加 1（&1 代表传入的第一个参数，即各个元素本身）
iex> MyList.map([1, 2, 3, 4], &(&1 + 1))
[2, 3, 4, 5]

# ➔ 使用快捷符号进行大于 2 的判断
iex> MyList.map([1, 2, 3, 4], &(&1 > 2))
[false, false, true, true]

在递归中通过参数传递状态（尾递归基础）

在 Elixir 等函数式编程语言中，数据是不可变的（Immutable）。我们无法像在传统循环中那样，使用一个全局变量或外部可变变量来累加结果。

为了在遍历列表时记住部分元素的总和，我们必须将“当前状态”作为参数直接传递给函数。这个额外引入的参数通常被称为累加器（Accumulator）。

# :pushpin: 携带累加器的求和函数实现:通过两个参数（列表 + 当前和）来实现列表求和：

defmodule MyList do
  # 规则 1（基准条件）：当列表为空时，说明所有元素已加完，当前累计的 total 就是最终答案
  def sum([], total), do: total

  # 规则 2（递归步骤）：将头部 head 加到当前 total 中，然后把新的总和作为参数传递给 tail 的递归调用
  def sum([head | tail], total), do: sum(tail, head + total)
end

:magnifying_glass_tilted_left: 这种设计带来的三大核心优势

• 1. 不变量（Invariant）的维护：在任何时刻、任何一级嵌套调用中，都维护着一个隐式的不变量：当前列表参数的所有元素之和 + 当前 total = 整个列表的最终总和。
• 2. 零外部依赖：不需要模块级或全局级变量，完全依靠函数参数链条传递状态。
• 3. :sparkles: 尾递归优化（Tail Call Optimization）：请注意，规则 2 的最后一步仅仅是调用了函数自身，没有包含任何后续的算术操作（如上一章的 1 + len(tail)）。这允许 Erlang 虚拟机虚拟机（BEAM）复用当前栈帧，即使列表有百万级长度，也绝不会导致栈溢出。
• 使用此类携带累加器的函数时，调用者必须显式传入初始值 0

iex> c "sum.exs"
[MyList]

# :warning: 注意：第二个参数必须传入初始值 0
iex> MyList.sum([1, 2, 3, 4, 5], 0)
15

iex> MyList.sum([11, 12, 13, 14, 15], 0)
65

虽然这种写法性能极佳，但对外部调用者来说很不方便——每次求和都必须强制多写一个 , 0。在实际开发中，我们通常会再暴露一个单参数的同名函数（或者使用默认参数）来隐藏这个底层实现的细节。

方式一：使用默认值

defmodule MyList do
  # :sparkles: 使用 \\ 0 指定 total 的默认值为 0
  # :warning: 核心细节：由于有默认值，在定义“多子句递归”时，必须遵循以下特殊顺序！
  
  # 1. 带有默认参数的子句必须写在最上面，且其 do 体通常为空（仅作签名声明）
  def sum(list, total \\ 0)

  # 2. 接下来的具体实现子句，严禁再次写出 \\ 0，否则编译器会报错（参数定义冲突）
  def sum([], total), do: total
  def sum([head | tail], total), do: sum(tail, head + total)
end

方式二：使用私有辅助函数（Private Helper Functions）隐藏实现细节

在 Elixir 的编程约定中，如果一个递归函数需要传入额外的初始值（如求和中的 0 或求积中的 1），直接暴露给用户会显得不够优雅。标准的做法是：对外暴露一个只接受必要参数的公开函数，而在模块内部通过调用私有辅助函数来完成真正的尾递归工作。这样可以保持公开接口的简洁和安全。

defmodule MyList do
  # :sparkles: 公开门户：只接受一个参数，在 do 体内部隐式帮用户传入初始值 0
  def sum(list), do: _sum(list, 0)

  # :locked: 私有方法：负责真正的尾递归计算
  defp _sum([], total), do: total
  defp _sum([head | tail], total), do: _sum(tail, head + total)
end

• defp 指令：使用 defp（Define Private）定义的函数是私有函数。私有函数只能在当前模块内部被调用，任何在模块外部调用的尝试（如 MyList._sum(…)）都会导致编译或运行报错。
• 下划线命名约定（_）：在 Elixir 中，参数个数不同（Arity）的函数在底层是完全不同的两个函数。因此，私有辅助函数即便和公开函数都叫 sum 也完全合法。但社区通常推荐给辅助函数加上下划线前缀（如 _sum）或者写成 do_sum，这符合人类的阅读习惯，能让人一眼看出它们之间存在母子函数的联系。

练习

不用累加器实现sum函数

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

这种写法非常符合数学定义，简单好懂。唯一的缺点是，如果列表有几十万个元素，由于每一层都需要在内存中等待内层函数的返回，会消耗较多的栈内存空间（而之前使用累加器的尾递归写法能完美避免这个问题）。

通用的 reduce 归纳高阶函数

在前面的章节中，我们学习了求和函数 sum。实际上，求和只是将一个收集（Collection）归约（Reduce）为单个值的特例。其他的操作——如找出最大/最小值、计算所有元素的乘积、或者将元素拼接成一个字符串——其底层逻辑完全一致。

为了消除重复代码，我们需要编写一个通用的 reduce 函数。它属于高阶函数，通过接受三个参数来工作：

reduce(collection, initial_value, fun)$

它将传入的函数 fun 应用于列表的头部和当前累计值，并在递归归约列表的尾部时，将计算结果作为新的当前值传入。

:pushpin: reduce 的递推设计与代码实现

通用的 reduce 函数实现如下：

defmodule MyList do
  # 规则 1（基准条件）：当列表为空时，无法继续归约，直接返回当前的累计值 value
  # :sparkles: 技巧：使用下划线前缀 `_` 忽略未使用的函数参数
  def reduce([], value, _) do
    value
  end

  # 规则 2（递归步骤）：
  # 1. 调用 func.(head, value) 计算出当前头部与当前累计值结合后的“新累计值”
  # 2. 将这个“新累计值”作为参数，继续递归调用 reduce 处理剩余的尾部 tail
  def reduce([head | tail], value, func) do
    reduce(tail, func.(head, value), func)
  end
end

借助 Elixir 的 & 快捷标记符号（其中 &1 代表传给匿名函数的第一个参数，&2 代表第二个参数），我们可以让 reduce 瞬间演变成各种功能强大的计算工具：

## 1. 瞬间进化为“求和函数”（初始值设为 0，逻辑设为 +）

iex> c "reduce.exs"
[MyList]

iex> MyList.reduce([1, 2, 3, 4, 5], 0, &(&1 + &2))
15

## 2. 瞬间进化为“求积函数”（初始值设为 1，逻辑设为 *）

iex> MyList.reduce([1, 2, 3, 4, 5], 1, &(&1 * &2))
120

抽象能力牛掰！

习题

编写函数mapsum，接受一个列表和一个函数作为参数。它将函数应用于列表中的每个元素，然后求这些结果的和，所以：

iex> MyList.mapsum [1, 2, 3], &(&1 * &1)
14

代码：

defmodule MyList do
  def mapsum([],_f), do: 0
  def mapsum([head|tail],f), do: f.(head) + mapsum(tail,f)
end

测试：

iex>  MyList.mapsum [], &(&1 * &1)
0
iex>  MyList.mapsum [1,2,3], &(&1 * &1)
14

编写max(list)，返回列表元素中的最大值。

defmodule MyList do
  def max([]), do: nil

  def max([head|[]]),do: head
  
  def max([head|[tail_head|tail_tail]]) when head>=tail_head do
    max([head|tail_tail])
  end
  def max([head|[tail_head|tail_tail]]) when head<tail_head do
    max([tail_head|tail_tail])
  end
end

• 在 def max(…) 的参数括号和 when 关键字之间，绝对不能加逗号 ,
• **when 内部不能调用自定义函数 **

测试：

iex>  MyList.max([])
nil
iex>  MyList.max([1])
1
iex>  MyList.max([1,9,5,7])
9

Elixir的单引号字符串其实是字符编码列表。编写函数caesar(list，n)，给列表中的每个元素加上n，如果得到的结果超出字符z的编码，则回转。(这里回转假定从a开始,’a’ 对应的值是：97, ‘z’ 对应的值是：122)

defmodule MyList do
  def caesar([],_n), do: []
  
  def caesar([head|tail],n) when (head+n)> 122 do
    # (head+n-122 + 96) 
    [(head+n-26) |  caesar(tail,n)]
  end

  def caesar([head|tail],n) when (head+n) <=122 do
    [(head+n) | caesar(tail,n)]
  end
end

• <> 操作符 专门用于拼接双引号字符串（Binary Strings）（例如 "hello" <> " world"）
• 在 Elixir 中，将一个元素连接到一个列表前面的“唯一指定魔法符号”是管道符 |（即 [ 元素 | 列表 ]）

测试：

iex>  MyList.caesar('',13)
[]
iex>  MyList.caesar('ryvkve',13)
warning: using single-quoted strings to represent charlists is deprecated.
Use ~c"" if you indeed want a charlist or use "" instead.
You may run "mix format --migrate" to change all single-quoted
strings to use the ~c sigil and fix this warning.
└─ iex:30:15

[101, 108, 105, 120, 105, 114]
iex>  MyList.caesar(~c"ryvkve",13)
[101, 108, 105, 120, 105, 114]
iex>  MyList.caesar(~c"ryvkve", 13) |> IO.puts()
elixir
:ok