What is actually happening inside List.nth in SML?

Question

Could somebody help me understand List.nth in SML?

It outputs a specified element from the list. a)

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

b)

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

For example:

1. Implementation of map function using recursion would be:

fun map _ nil = nil | map f (a::b) = (f a) :: (map f b);

2. Implementation of foldr function using recursion would be:

fun foldr _ c nil = c | foldr f c (a::b) = f(a, foldr f c b);

Likewise, what is actually happening inside List.nth.

Answer 1

A simple implementation of List.nth would be something like the following, using pattern-matching, and the option type to handle out of bounds errors.

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

• It doesn't matter what index we're looking for in an empty list. It's not there.

• If the index is 0, return the first element in the list. It doesn't matter what the rest of the list is.

• Otherwise, call nth on the rest of the list and decrease the index by 1.

So if we call nth([3, 7, 4, 1, 8], 3) the recursion looks like:

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