What is actually happening inside List.nth in SML?

user_7215826 0
Viewed 100

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.

sml functional-programming
2 Answers

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
user_152613150

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

user_3907080
Related