recursionsequenceformal-methodsvdm++vdm-sl

VDMSL Recursive function minimum value of sequence


I think this should be relatively straightforward, was wondering if anyone knew how to answer this:

Define a recursive function seq-min : N+ -> N which returns the smallest value in a sequence of natural numbers.

I was thinking something along the lines of...

if hd seq < hd tl seq then seq-min([hd seq] concat tl tl seq)
else if hd seq > hd tl seq then seq-min(tl seq)
else if hd seq = hd tl seq then seq-min(tl seq)

Thanks for any help!


Solution

  • Here is a slightly different approach, using a single function:

        seq_min: seq of nat -> nat
        seq_min(s) ==
                cases s:
                        [x] -> x,
    
                        [x] ^ rest ->
                                let min = seq_min(rest) in
                                        if x < min then x else min
                end
        pre len s > 0;
    

    This has the advantage that it is short and intuitive (and a single function). Specifications can be very clear when they are written as a set of "patterns" in a cases expression like this, as each case is explicitly "explained".