CODEWITHSUNDEEP
sml
C. Miller
C. Miller

Reputation: 31

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

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

Upvotes: 1

Views: 3947

Answers (2)

test
test

Reputation: 1

A simple approach:

fun nth (nil,0) = raise Fail "You are out of bounds with nth element"
  | nth ((x::xr),n) = if n=0 then x else nth (xr,(n-1))

Upvotes: 0

sshine
sshine

Reputation: 16145

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

Upvotes: 2

Related Questions