SML中List.nth函数的内部运行逻辑与实现原理是什么？

List.nth 是SML标准库提供的列表索引取值函数，索引从0开始计数，传入的索引超出列表长度范围时会抛出Subscript异常。

你给出的运行示例完全符合它的基础行为：

• 取索引0的元素：

List.nth ([7,3,6,1],0);
val it = 7 : int 

• 取索引1的元素：

List.nth ([7,3,6,1],1);
val it = 3 : int 

内部实现逻辑 #

SML的列表本质是单向链表，不支持随机访问，因此List.nth通过递归遍历实现，时间复杂度为O(n)，n为传入的索引值。和你给出的map、foldr递归实现风格一致，等效的递归实现代码如下：

fun nth (nil, _) = raise Subscript
  | nth (x::_, 0) = x
  | nth (_::xs, n) = if n < 0 then raise Subscript else nth (xs, n-1);

运行逻辑拆解 #

1. 边界判断：如果传入空列表，无论索引值是多少，直接抛出下标越界异常
2. 递归终止条件：当索引值为0时，直接返回当前列表的头部元素
3. 递归迭代：如果索引值大于0，就去掉当前列表的头部元素，将索引值减1后继续递归调用；如果索引为负也直接抛出异常，避免无限递归

举个实际调用的运行过程示例，比如执行nth([7,3,6,1], 2)：

• 第一次调用：匹配第三个分支，递归调用nth([3,6,1], 1)
• 第二次调用：匹配第三个分支，递归调用nth([6,1], 0)
• 第三次调用：匹配第二个分支，返回头部元素6，递归结束

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