What is actually happening inside List.nth in SML?

3
votes

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);

  1. 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.

2
functional-programmingsml

2 Answers

2
votes

A simple implementation of List.nth would be something like the following, using patter-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
0
votes

nth (l, i) returns the i(th) element of the list l, counting from 0. In other words it's accessing the element in l by index i.

In example "a" List.nth([7,3,6,1], 0) returns the i(th) element in l which is 7

In example "b" List.nth([7,3,6,1], 1) returns the i(th) element in l which is 3