induction - Dafny and counting of occurences -

i've been looking @ use of lemmas in dafny finding hard understand , below example doesn't verify, quite possibly because dafny doesn't see induction or lemma prove property of count? basically, don't know how or need define convince dafny counting inductive , thing etc. of ensures , invariants specifications not necessary, that's not point. btw, easier in spec#.

function count(items: seq<int>, item: int): nat   decreases |items| {   if |items| == 0 0 else     (if items[|items| - 1] == item 1 else 0)         + count( items[..(|items| - 1)], item ) }  method occurences(items: array<int>, item: int) returns (r: nat)   requires items != null   ensures r <= items.length   // number of occurences of item   ensures r > 0  ==> exists k: nat :: k < items.length                      && items[k] == item   // no occurences of item   ensures r == 0 ==> forall k: nat :: k < items.length                      ==> items[k] != item   ensures r == count( items[..], item ) {   var i: nat := 0;   var num: nat := 0;    while < items.length     // increasing , there elements match     invariant num <= <= items.length     invariant num > 0 ==> exists k: nat :: k <                           && items[k] == item     invariant num == 0 ==> forall k: nat :: k <                            ==> items[k] != item     invariant num == old(num) + 1 || num == old(num)     invariant num == count( items[..i], item )   {     if items[i] == item       { num := num + 1; }     := + 1;   }   return num; } 

i use definition of count based around multiset, works:

function count(items: seq<int>, item: int): nat   decreases |items| {   multiset(items)[item] }  method occurences(items: array<int>, item: int) returns (r: nat)   requires items != null   ensures r <= items.length   // number of occurences of item   ensures r > 0  ==> exists k: nat :: k < items.length                      && items[k] == item   // no occurences of item   ensures r == 0 ==> forall k: nat :: k < items.length                      ==> items[k] != item   ensures r == count(items[..], item) {   var i: nat := 0;   var num: nat := 0;    while < items.length     // increasing , there elements match     invariant num <= <= items.length     invariant num > 0 ==> exists k: nat :: k <                           && items[k] == item     invariant num == 0 ==> forall k: nat :: k <                            ==> items[k] != item     invariant num == old(num) + 1 || num == old(num)     invariant num == count(items[..i], item)   {     if items[i] == item       { num := num + 1; }     := + 1;   }   assert items[..i] == items[..];   r := num; } 

i suggest 2 alternative approaches, , solution original design.

1. without changing implementation, write specification this:

   function count(items: seq<int>, item: int): nat   decreases |items| {   multiset(items)[item] }  method occurences(items: array<int>, item: int) returns (num: nat)   requires items != null   ensures num <= items.length   ensures num == 0 <==> item !in items[..]   ensures num == count(items[..], item) {   num := 0;    var i: nat := 0;   while < items.length     invariant num <= <= items.length     invariant num == 0 <==> item !in items[..i]     invariant num == count(items[..i], item)   {     if items[i] == item       { num := num + 1; }     := + 1;   }   assert items[..i] == items[..]; } 

2. if decide on implementation write this:

   method occurences(items: array<int>, item: int) returns (num: nat)   requires items != null   ensures num == multiset(items[..])[item] {   num := multiset(items[..])[item]; } 

3. there way original verify adding assertion. nb. think "old" doesn't think in loop invariant.

   function count(items: seq<int>, item: int): nat   decreases |items| {   if |items| == 0 0 else     (if items[|items|-1] == item 1 else 0)         + count(items[..|items|-1], item ) }  method occurences(items: array<int>, item: int) returns (r: nat)   requires items != null   ensures r <= items.length   // number of occurences of item   ensures r > 0  ==> exists k: nat :: k < items.length                      && items[k] == item   // no occurences of item   ensures r == 0 ==> forall k: nat :: k < items.length                      ==> items[k] != item   ensures r == count( items[..], item ) {   var i: nat := 0;   var num:nat := 0;    while < items.length     invariant num <= <= items.length     invariant num > 0 ==> exists k: nat :: k <                           && items[k] == item     invariant num == 0 ==> forall k: nat :: k <                            ==> items[k] != item     invariant num == count(items[..i], item)   {     assert items[..i+1] == items[..i] + [items[i]];      if items[i] == item       { num := num + 1; }     := + 1;   }   assert items[..i] == items[..];   r := num; }