functional-programming - SML 中的 List.nth 内部究竟发生了什么？

Question

有人可以帮助我理解 SML 中的 List.nth 吗？

它从列表中输出指定的元素。一)

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

二)

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

例如:

1. 使用递归实现 ma​​p 函数是:

趣味 map _nil = nil| map f (a::b) = (f a)::( map f b);

1. 使用递归实现 foldr 函数是:

有趣的文件夹 _ c nil = c| foldr f c (a::b) = f(a, foldr f c b);

同样，List.nth 内部实际发生了什么。

Answer 1

List.nth 的简单实现如下所示，使用模式匹配和 option 类型来处理越界错误。

fun nth([], _) = NONE
  | nth(x::_, 0) = SOME x
  | nth(x::xs, i) = nth(xs, i - 1)

我们在空列表中寻找什么索引并不重要。它不在那里。

如果索引为 0，则返回列表中的第一个元素。列表的其余部分是什么并不重要。

否则，对列表的其余部分调用 nth 并将索引减 1。

所以如果我们调用 nth([3, 7, 4, 1, 8], 3) 递归看起来像:

nth([3, 7, 4, 1, 8], 3)
nth([7, 4, 1, 8], 2)
nth([4, 1, 8], 1)
nth([1, 8], 0)
SOME 1