diff options
Diffstat (limited to 'Test/hofs/Fold.dfy')
-rw-r--r-- | Test/hofs/Fold.dfy | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/Test/hofs/Fold.dfy b/Test/hofs/Fold.dfy new file mode 100644 index 00000000..df7d0126 --- /dev/null +++ b/Test/hofs/Fold.dfy @@ -0,0 +1,30 @@ +// RUN: %dafny /compile:3 "%s" > "%t" +// RUN: %diff "%s.expect" "%t" + +datatype List = Nil | Cons(A,List<A>); + +datatype Expr = Add(List<Expr>) | Mul(List<Expr>) | Lit(int); + +function method Eval(e : Expr): int +{ + match e + case Add(es) => Fold(es,0,(e,v) requires e < es => Eval(e) + v) + case Mul(es) => Fold(es,1,(e,v) requires e < es => Eval(e) * v) + case Lit(i) => i +} + +function method Fold(xs : List<A>, unit : B, f : (A,B) -> B): B + reads f.reads; + requires forall x : A, y: B :: x < xs ==> f.requires(x,y); +{ + match xs + case Nil => unit + case Cons(x,xs) => f(x,Fold(xs,unit,f)) +} + +method Main() { + var two := Lit(2); + var add := (x,y) => Add(Cons(x,Cons(y,Nil))); + assert Eval(add(two,two)) == 4; + print "3 = ", Eval(add(Lit(1),two)), "\n"; +} |