0
$\begingroup$

Having trouble understanding what it means to define something inductively in the following context.

Can you give an inductive to define the length of a list L?

a. The total number of items in L is the length of L

b. Basis: the length of an empty list is 0 Induction: the length of a list is 2*(length of half the list)

c. Basis: the length of an empty list is 0 Induction: the length of a list is (length of head(list))+(length of tail(list))

d. Basis: the length of an empty list is 0 Induction: the length of a list is 1+(length of tail(list))

The answer is (d). Why might this be?

And also for this similar question:

Can you give an inductive definition to define what it means for an element X to be a member of a list L?

a. X is a member of a list L if and only if X belongs to the list L.

b. X is a member of a list L if either X is the head of the list or X is a member of the tail of L.

c. X is a member of a list L if we can find an element Y in L and X=Y.

d. X is a member of a list L if we can find an element Y in the tail of L

The answer is (b).

Thank you.

$\endgroup$
1
  • $\begingroup$ A multiple choice question beginning with "can you..." should have two possible answers: yes and no. $\endgroup$
    – Kai
    May 10 '17 at 9:40
1
$\begingroup$

In an inductive definition what you have to do is to find a base case and the inductive step.

In your case, suppose to have a list $L$ and let head be the first element and tail the rest of the list.

For example, if $L=[1,2,3,4,5]$:

  • head = $1$
  • tail = $[2,3,4,5]$

In order to understand the meaning you could consider writing a recursive function to compute the length of the list.

According to the answer

  • Basis: the length of an empty list is 0
  • Induction: the length of a list is 1+(length of tail(list))

This corresponds to the recursive function

function len(list L)
   if L is empty
        return 0
   else return 1 + len(tail(L))

Same for the second question:

function member(elem x, list L)
   if L is empty
       return false
   if head == x 
       return true
   else return member(x, tail(L))

and this corresponds to say: X is a member of a list L if either

  • X is the head of the list or
  • X is a member of the tail of L.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.