SML - Find same elements in a string

Question

Sorry but I need your help again! I need a function which takes as input a

list of (string*string) 

and returns as output a

list of (int*int)

The function should manipulate the list such that, every element that is represented by the same string has to be replaced by the same number. For example if I insert:

changState([("s0","l0"),("l0","s1"),("s1","l1"),("l1","s0")]);

the output should be: val it = [(0,1),(1,2),(2,3),(3,0)]

Is there someone who has an idea to solve this problem? I would really appreciate that. Thanks a lot!

Answer 1

Here is one way:

structure StringKey = 
struct 
  type ord_key = string 
  val compare = String.compare
end

structure Map = RedBlackMapFn(StringKey)

fun changState l =
  let fun lp(l, map, max) = 
        case l 
           of nil => nil
            | (s1,s2)::l' => 
                case (Map.find(map, s1), Map.find(map, s2))
                   of (SOME i1, SOME i2) => (i1, i2)::lp(l', map, max)
                    | (NONE, SOME i) => (max, i)::lp(l', Map.insert(map, s1, max), max+1)
                    | (SOME i, NONE) => (i, max)::lp(l', Map.insert(map, s2, max), max+1)
                    | (NONE, NONE) =>
                        if s1 <> s2
                        then (max, max+1)::lp(l', Map.insert(Map.insert(map, s1, max), s2, max+1), max+2)
                        else (max, max)::lp(l', Map.insert(map, s1, max), max+1)
  in lp(l, Map.empty, 0) end

Here lp takes the list of string pairs, a map which relates strings to integers, and a variable max, which keeps track of the next unused number. In each iteration, we lookup the two strings in the map. If they are found, return that integer, otherwise, use the next available integer. The last case, where neither string exists in the map, we need to check if the strings are equal, in case your input was [("s0", "s0")], we would expect [(0, 0)]. If they are equal, we map them to the same number, otherwise create distinct ones.

If you are not familiar with functors, the first 5 lines are creating a structure that satisfies the ORD_KEY signature. You can find more details in the documentation at

1. http://www.smlnj.org/doc/smlnj-lib/Manual/ord-map.html
2. http://www.smlnj.org/doc/smlnj-lib/Manual/ord-key.html#ORD_KEY:SIG:SPEC

By applying the ReBlackMapFn functor to the StringKey structure, it creates a new structure of a map (implemented as a red black tree) that maps strings to things of type 'a