SML

Question

对不起，我又需要你的帮助了！我需要一个将

作为输入的函数

list of (string*string)

和returns作为输出a

list of (int*int)

该函数应该操纵列表，使得由相同字符串表示的每个元素都必须由相同的数字替换。例如，如果我插入：

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

输出应该是： val = [(0,1),(1,2),(2,3),(3,0)]

有没有人有解决这个问题的想法？我真的很感激。非常感谢！

Answer 1

这是一种方法：

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

此处 lp 获取字符串对列表、将字符串与整数相关联的映射以及跟踪下一个未使用数字的变量 max。在每次迭代中，我们在映射中查找两个字符串。如果找到，则 return 那个整数，否则，使用下一个可用的整数。最后一种情况，映射中不存在任何字符串，我们需要检查字符串是否相等，如果您的输入是 [("s0", "s0")]，我们期望 [(0, 0)]。如果它们相等，我们将它们映射到相同的数字，否则创建不同的数字。

如果您不熟悉函子，前 5 行是创建满足 ORD_KEY 签名的结构。您可以在

的文档中找到更多详细信息

通过将 ReBlackMapFn 仿函数应用到 StringKey 结构，它创建了一个新的映射结构（作为红黑树实现），将字符串映射到类型 'a

SML - 查找字符串中的相同元素

SML - Find same elements in a string

string

list