Dafny 检查图包含值

Question

我在 dafny 有一张类似 map<int,char> 的地图，我想看看它是否包含一些值。

假设 dafny 中还没有这方面的语法，我已经开始为它创建一个方法，但被卡住了。到目前为止我的代码如下：

method containsValue(m: map<int,char>, val: char) returns (b: bool) 
    ensures b <==> exists i :: i in m && m[i] == val;
  {
    var i := 0;
    while (i < m.Length) {
        if (m[i] == val) 
          { return true; }      
      }
        return false;
    }

这不起作用，因为我不知道如何找到地图的大小，而且可能还有其他一些问题。请帮忙

Answer 1

Modern Dafny 有内置语法，使用地图的特殊 .Values 字段，returns 地图中的值集。地图还有一个 .Keys 用于返回键集。（不幸的是，.Keys 和 .Values 目前都没有记录。我们正在努力。）

你可以用一行表达你的方法如下

method containsValue(m: map<int,char>, val: char) returns (b: bool) 
    ensures b <==> exists i :: i in m && m[i] == val;
{
    return val in m.Values;
}

Dafny 自动验证其满足其规范。

您还可以手动迭代地图的元素，如下所示

method containsValue(m: map<int,char>, val: char) returns (b: bool)
    ensures b <==> exists i :: i in m && m[i] == val;
{
    var m' := m;
    while m'.Keys != {}
        invariant m'.Keys <= m.Keys
        invariant forall k | k in m' :: m'[k] == m[k]
        invariant (exists i :: i in m && m[i] == val) ==> (exists i :: i in m' && m'[i] == val)
        decreases m'.Keys
    {
        var k :| k in m';
        if m'[k] == val {
            return true;
        }
        m' := map k' | k' in m' && k' != k :: m'[k'];
    }
    return false;
}

Dafny 的地图理解和内置语法通常使此类迭代变得不必要，因此风格不佳。（特别是这个方法，单行版的更清楚。）但是，它偶尔会在其他上下文中有用，所以了解该技术是很好的。

Dafny 检查图包含值

Dafny check map contains value

dafny