Haskell列表递归如何工作？myLength函数为何不会无限运行？

基础运行逻辑 #

这个函数是典型的递归列表处理实现，利用了Haskell列表的代数数据结构特性：所有Haskell列表只有两种结构，要么是空列表[]，要么是由头元素x和剩余子列表xs拼接成的x:xs结构。
函数通过模式匹配处理两种输入情况：

• 匹配到空列表[]时，直接返回整数0
• 匹配到非空列表(x:xs)时，先递归计算剩余子列表xs的长度，再给结果加1

为什么不会无限执行 #

递归不会无限执行的核心原因是每一步递归的输入规模都在严格缩小：
每次调用myLength (x:xs)时，下一轮递归的参数是去掉了头元素的子列表xs，长度比原列表少1。对于任意有限长度的输入列表，递归的输入规模最终一定会缩小到0，不会出现无限递归的情况。如果输入的是无限列表，递归才会永不停止，不过这属于特殊使用场景。

函数的停止条件 #

这个函数的明确停止条件就是输入参数匹配到空列表[]，此时会直接返回常量0，不再触发新的递归调用，之后会逐层回溯完成之前每一步的+1计算，最终得到整个列表的长度。

你可以参考下面的实际运行推导过程理解：

myLength [1,2,3]
= (+1) (myLength [2,3])
= (+1) ((+1) (myLength [3]))
= (+1) ((+1) ((+1) (myLength [])))
-- 此处触发停止条件，myLength [] 返回 0
= (+1) ((+1) ((+1) 0))
= (+1) ((+1) 1)
= (+1) 2
= 3

内容的提问来源于stack exchange，提问作者smarinrojas