Potentially useful information

$$ Quantification over a list

Quantification over the elements of a list is defined inductively:

Given the environment:

Type Ty

xs : list$($Ty$)$

p: Ty $->$ B

Universal quantification over a list is defined as: $$x in xs$.$ p$($x$)$ :$=$ else F

if empty$($xs$)$ then

T

p$($front$($xs$))$x in pop$($xs$).$ p$($x$)$

Existential quantification over a list is defined as:

$$x in xs$.$ p$($x$)$ :$=$

if empty$($xs$)$ then

else p$($front$($xs$))$x in pop$($xs$).$ p$($x$)$

Q$1$ Proof of Deletion $(15$ marks$)$

The function del below deletes all occurrences of an element from a list.

del$($x: Ty$,$ xs: list$($Ty$))$: list$($Ty$)$ :$=$

if empty$($xs$)$ then $[]$

else

val fr $=$ front$($xs$)$

if xfr then

del$($x$,$ pop$($xs$))$

else

push$($fr$,$ del$($x$,$ pop$($xs$))$

Q$1$ a$.$ Proof $(14$ marks$)$

Prove that del satisfies the theorem below:

xs: list$($Ty$).$

Vx: Ty$.$

$$y in del$($x$,$ xs$).$ y $!=$ x