Dafny反向查找图

Dafny reverse lookup map

您好,我有一个类似 map<char,int> 的地图,我希望进行反向查找,即从一个值中找到一个键。

在 Dafny(例如 map.getKey(value))中是否有任何尚未记录的方法可以做到这一点?

我认为一种解决方案是反转地图,这样我就可以将 map<char,int> 反转为 map<int,char,然后在反转地图上使用正常查找。我不确定如何执行此操作,但已尝试通过地图理解使用 map table[i] | i in table :: i,但这不起作用。

请帮帮我。

您可以使用 "let such-that" 语句来做到这一点。例如:

method Test(m: map<char,int>, val: int)
    requires exists i :: i in m && m[i] == val;
{
    var i :| i in m && m[i] == val;
    // now use i...
}

您也可以按如下方式反转地图(但您不需要只进行一次反向查找)

function method InvertMap(m: map<char,int>): map<int,char>
{
    map b | b in m.Values :: var a :| a in m && m[a] == b; a
}