Applied

Recursive definitions for data structures are used a lot in programming languages.

One such data structure we can define recursively is the list.

A list is recursively defined as follows:

i$)[]$ is the empty list.

ii$)$ Let $x$ be any object and $L_1$ be a list.

Then $(x$:$L_1)$ is a newly constructed list.

It is object x appended to the front of $L_1.$

Now, we can concatenate two lists, which is the $++$ operator.

Concatenating two lists is defined recursively as follows:

i$)[]++L=L,$ where $L$ is a list.

ii$)(x$:$L_1)++L_2=(x$:$L_1++L_2),$ where $L_1,L_2$ are lists, and $x$ is an object.

Note: Both $(x$:$L_1)$ and $(x$:$L_1++L_2)$ are lists.

Let $S$ and $T$ be lists.

Prove by structural induction that length $(S++T)=$ length $(S)+$ length $(T).$

Hints: Do induction on the $++$ operator. Let $T$ be any list for the whole

proof and modify $S$ based on which rule you are working with, but keep $T$ arbitrary.

Also, the length of a list is simply how many elements are in it$.$