TEACH SETS1                                        Aaron Sloman Feb 82

This is for use in conjunction with TEACH * SETS.

--- DEFINING THE PROCEDURE  ISELEMENT --------------------------------

This was our schema for ISELEMENT.

    DEFINE ISELEMENT(ITEM,LIST) -> RESULT;
      IF  <the list is empty>
      THEN    <not there>
      ELSEIF  <the item is the first element of the list>
      THEN    <it is there>
      ELSE    <repeat this process with the rest of the list>
      ENDIF
    ENDDEFINE;

We can find out if a list is empty by seeing if it is equal to the empty
list, that is:

    IF    LIST = []

but how is ISELEMENT to indicate that the item is not in the list?
It could print a message on the teletype, for example:

    THEN  [^ITEM IS NOT IN THE LIST] =>

This is fine if we only use ISELEMENT directly from the teletype but not if
ISELEMENT is called from another program, which needs to get a RESULT.
So we need something like:

      IF  LIST = []
      THEN    FALSE -> RESULT

Can you now complete the procedure?

If you've got a working version of ISELEMENT, you can leave this teach file
as follows. Make sure the cursor is in this file (use ESC X if necessary).
Press the ENTER button and type Q, then RETURN. VED will quit this file. You
can use ESC X or ENTER TEACH to get back to where you were, if the previous
TEACH file does not come back to the screen.


-- MORE DETAILED EXPLANATION -------------------------------------------

We can translate the phrase <the item is the first element of the list>
into POP11.

      ITEM = HD(LIST)

and the result of ISELEMENT is to be TRUE. (TRUE -> RESULT).

      IF  ITEM = HD(LIST)
      THEN    TRUE -> RESULT

Now we come to the tricky bit

    <repeat the  process with the rest of the list>

Normally we use a procedure call to tell POP11 we want a process performed. So
in this case we are going to have to write something like

      ISELEMENT(ITEM, TL(LIST)) -> RESULT;

That is, we want the procedure named ISELEMENT to be performed on the rest of
the list (the TaiL). See if you can complete the definition now.
the overal schema printed out, look back at the beginning of this file.




If you did not manage, type in this definition.

    define iselement(item,list) -> result;
      if  list = []
      then    false -> result
      elseif  item = hd(list)
      then    true -> result
      else    iselement(item,tl(list)) -> result
      endif
    enddefine;

Test your procedure:

    trace iselement;
    iselement(3, [1 2 3 4 5])=>


The tracing shows how ISELEMENT is 'recursive', i.e. it calls itself, each
time with a shorter argument. Try:
    iselement("cat", [animals cat dog mouse]) =>

Try:
    iselement("fish", [animals cat dog mouse])=>

Try some more variants of calls of ISELEMENT.
To 'turn off' tracing, type:

    untrace iselement;
    iselement(10, [ 1 2 3 4])=>


N.B. POP11 includes a procedure called MEMBER which works like ISELEMENT. You
can use MEMBER in your procedures where you would have used ISELEMENT.

When you have finished with this teach file, you can get back to what you
were doing by pressing <ESC> then q.