SML - Get specific Element out of List without using List.nth

Question

im trying to learn the basics of SML atm and stumbled across a task I can't find the answer for.

It is to write a function which takes in an int and a list, returns a specific element in the list on the index of that given int. As you see, it's exactly like the List.nth()-function.

Now I'm curious. This is how far I came, but I just can't think of a way to target a specific index manually.

fun nth(nil, _)     = 0
  | nth(x::xs, 0)   = x;
  | nth(x::xs, y)   = 

val list = [1, 2, 3];
nth(list, 0);

Your first basis case seems problematic. Shouldn't that be left undefined or trigger an exception rather than returning the number 0? As far as the rest goes here is a hint: Note that e.g. the 7th element of x::xs is the same as the 6th element of xs. — John Coleman
Thank you for that answer, i already new about the hint at the end. My problem is that even though I know the index of the elements, I don't really know how to interact with them individually. — C. Miller
You don't explicitly interact with the indices (other than subtracting 1 from them) in this naive recursive approach. You just count-down (via recursive calls) until the index reaches 0, at which time you return the head of the remaining list. — John Coleman
Thank you very much, I'm still not really used to the functioning of SML. The simple solution I searched for was: nth(xs, y-1) — C. Miller

Simon Shine Simon Shine · Accepted Answer · 2018-10-03T09:50:00

As John suggested, indexing an empty list could raise an exception instead of returning 0. This makes nth work for any type of list, not just the subset of int lists for which 0 can reasonably be considered "no result". It seems that the function lacks recursion to work for any index beyond 0. Here's a template to work with:

fun nth ([], _) = raise Empty
  | nth (x::_, 0) = x
  | nth (_::xs, n) = ...

Here an exception is added, and the variables that will not be used in each case of the function have been blanked out with the pseudo-variable _. You might want a more informative error message, too.

fun nth ([], n) = raise Fail "Failed to find the appropriate index!"
  | nth (x::_, 0) = x
  | nth (_::xs, n) = ...

A "safer" version of nth has the type 'a list * int -> 'a option, i.e. for nth (xs, i), if xs has an ith element x, it returns SOME x, and if it doesn't, it returns NONE:

fun nth_safe ([], _) = NONE
  | nth_safe (x::_, 0) = SOME x
  | nth_safe (_::xs, n) = ...

It's "safer" because it doesn't throw an exception if the list is not long enough. An adversarial example: nth ([0,1,2], 3)

But it still doesn't handle if the index is negative. An adversarial example: nth ([0,1,2], ~1)

You could address that concern inside the ... of the third function body with if n < 0 then ..., but then that would get executed on every recursive step, even though you would most likely only need to check it once.

A robust version of this function raises an error when you pass it a negative index. Otherwise your function might cause you to loop negatively until you run out of memory, since the recursive case (the 3rd case) does not converge towards the two base cases (case 1 and 2). For the exception-based version, you can write:

exception IndexError of int
fun nth (xs, n) =
    let fun go ([], _) = raise IndexError n
          | go (x::_, 0) = x
          | go (_::ys, i) = ...
    in if n < 0 then raise IndexError n else go (xs, n)
    end

A robust version using error-aware data types could instead look like:

fun nth (xs, n) =
    let fun go ([], _) = NONE
          | go (x::_, 0) = SOME x
          | go (_::ys, i) = ...
    in if n < 0 then NONE else go (xs, n)
    end

And a robust version using error-aware data types that capture the index error just like the exception-based version with the custom IndexError exception looks like:

datatype ('a, 'b) either = Left of 'a | Right of 'b
fun nth (xs, n) =
    let fun go ([], _) = Left n
          | go (x::_, 0) = Right x
          | go (_::ys, i) = ...
    in if n < 0 then Left n else go (xs, n)
    end

val example_1 = nth ([2,3,5], 5)  (* gives: Left 5  *)
val example_2 = nth ([2,3,5], ~1) (* gives: Left ~1 *)
val example_3 = nth ([2,3,5], 2)  (* gives: Right 5 *)

SML - Get specific Element out of List without using List.nth

2 Answers