SML - Find element in a list and substitute it

Question

I'm trying to build a function which takes as input two list of type

(string*string) list

and returns one list of the same type. The first list is like a "lookup" list in which the second element is the element to search and the first element is the element to use for the substitution. The aim of the function is to find which element in the second list is equal to which element of the first list. In case of matching the element of the second list will be substitute with the correspondent element of the tuple in the first element. Below an example:

fun check([("0","s0"),("1","s0l0s1"),("2","s1"),("3","s1l1s0")],[("s0","s0l0s1"),("s0l0s1","s1"),("s1","s1l1s0"),("s1l1s0","s0")]);

With these inputs the function should return:

val it = [("0","1"),("1","2"),("2","3"),("3","0")]

Since "s0" corresponds to "0", "s0l0s1" corresponds to "1", "s1" corresponds to "2" and "s1l1s0" corresponds to "3".

I've done two functions so far:

fun check1((l1 as (x1,y1))::nil,(l2 as (x2,y2))::nil) =  if x2 = y1 then [(x1,y2)] else nil
|check1((l1 as (x1,y1))::rest1,(l2 as (x2,y2))::rest2) = 
if x2 = y1 then (x1,y2)::check1(rest1,rest2)
else check1(rest1,l2::rest2)

fun check2((l1 as (x1,y1))::nil,(l2 as (x2,y2))::nil) =  if y2 = y1 then [(x2,x1)] else nil
|check2((l1 as (x1,y1))::rest1,(l2 as (x2,y2))::rest2) = 
if y2 = y1 then (x2,x1)::check2(rest1,rest2)
else check2(rest1,l2::rest2)

The first one checks the element of the first tuple of the second list and the second function checks the element of the second tuple. But they don't work properly. Someone can help me in understanding where is the mistake? Thanks a lot!

Answer 1

You're making this way too complicated.

This first function looks up a string in the first list:

fun lookup ((a,b)::xs) v = if v = b then a else lookup xs v
  | lookup nil v = v;

And this one just runs recursively on both elements in the second list:

fun check (xs,((a,b)::ys)) = (lookup xs a, lookup xs b)::check(xs,ys)
  | check (xs,nil) = nil;