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
}
您好,我有一个类似 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
}