Standard ML - Return the index of the occurrences of a given value in a list

Question

I'm trying to figure out how to return a list of the indexes of occurrences of a specific value in another list. i.e. indexes(1, [1,2,1,1,2,2,1]); val it = [1,3,4,7] int list

I'm trying to figure out how lists work and trying to get better at recursion so I don't want to use List.nth (or any library functions) and I don't want to move into pattern matching quiet yet.

This is what I have so far

fun index(x, L) =
if null L then 0
else if x=hd(L) then 
    1
else 
    1 + index(x,tl L);

fun inde(x, L) =
if null L then []
else if x=hd(L) then 
    index(x, tl L) :: inde(x, tl L)
else
    inde(x, tl L);

index(4, [4,2,1,3,1,1]);

inde(1,[1,2,1,1,2,2,1]);

This gives me something like [2, 1, 3, 0]. I guess I'm just having a hard time incrementing things properly to get the index. The index function itself works correctly though.

Answer 1

Instead you could also make two passes over the list: first add an index to each element in the list, and second grap the index of the right elements:

fun addIndex (xs, i) =
    if null xs then []
    else (hd xs, i) :: addIndex(tl xs, i+1)

fun fst (x,y) = x
fun snd (x,y) = y
fun indexi(n, xs) =
    if fst(hd xs) = n then ... :: indexi(n, tl xs)
    else indexi(n, tl xs)

(I left out part of indexi for the exercise.) Where addIndex([10,20,30],0) gives you [(10,0),(20,1),(30,2)]. Now you can use addIndex and indexi to implement your original index function:

fun index(n, xs) = indexi(n, addIndex(xs, 0))

When you get that to work, you can try to merge addIndex and indexi into one function that does both.

However, you really want to write this with pattern matching, see for instance addIndex written using patterns:

fun addIndex ([], _) = []
  | addIndex (x::xs, i) = (x,i) :: addIndex(xs, i+1)

Answer 2

If you do index(1,[2]), it gives 1, which is not correct. When the list is empty, it gives you zero. In a function like this, you'd probably want to use SOME/NONE feature.