CODEWITHSUNDEEP
functional-programmingsml
asworeya shrestha
asworeya shrestha

Reputation: 79

What is actually happening inside List.nth in SML?

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.

Upvotes: 3

Views: 1949

Answers (2)

Chris
Chris

Reputation: 36451

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

Upvotes: 3

Brian
Brian

Reputation: 20285

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

Upvotes: 0

Related Questions