TEACH SETS.ANS                                       A.Sloman Feb 1984
                                               Revised A.Sloman Oct 1995

This file has been re-written to conform to the current good practice
regarding programming in Pop-11. In particular, "vars" has been replaced
by "lvars" in many places.

For quick reminders of the syntax of Pop-11 see TEACH POPCORE
A lot more information is given in TEACH PRIMER, also available in
printed form.


                   ILLUSTRATIVE ANSWERS TO TEACH SETS
                    =================================

         CONTENTS - (Use <ENTER> g to access required sections)

 -- ISELEMENT
 -- -- Recursive version of iselement
 -- HAPPYMAN
 -- FINDONE
 -- -- A note on testing for equality using "==" or "="
 -- -- Tests for findone
 -- -- Defining findone
 -- FINDALL
 -- -- Tests for findall
 -- FINDSET
 -- -- Tests for findset

There are many possible ways to define procedures of the sorts specified
in TEACH SETS and TEACH SETS2. So if your answers are different from
those given below, that doesn't mean yours is wrong.

-- ISELEMENT ----------------------------------------------------------

Look back at TEACH SETS for the specification of ISELEMENT

define iselement(item, list) -> result;
    ;;; an 'iterative' version, using a loop
    lvars item, list, result;
    ;;; search down the list looking for a thing = item.
    ;;; if found return true.
    lvars thing;
    for thing in list do
        if item = thing then
            true -> result; return()
        endif;
    endfor;
    ;;; not found, so
    false -> result;
enddefine;

NOTE: we need the call of return() to make sure that when the item is
found the loop stops, i.e. the procedure does not go on searching through
the list. We could not just use quitloop() because then it would do the
instruction after 'endfor', and that would produce a false result.
return() is roughly equivalent to 'goto enddefine', though the latter is
not legal Pop-11.

We need to have 'false -> result' after 'endfor' since if the procedure
gets to the end of the list without finding the item, then that means
the result should be false.

define iselement(item, list)->result;
    lvars item, list, result;
    ;;; Another 'iterative' version, using an "until" loop
    ;;; instead of a "for" loop
    ;;; Is it less clear?
    until list = [] do
        if item = hd(list) then     ;;; or list matches [^item == ]
            true -> result; return()
        else tl(list) -> list
        endif;
    enduntil;
    false -> result;
enddefine;

-- -- Recursive version of iselement

define iselement(item, list) -> result;
    lvars item, list, result;
    ;;; a recursive version
    if list = [] then
        false
    elseif item = hd(list) then     ;;; or list matches [^item == ]
        true
    else iselement(item,tl(list))   ;;; use recursion to search the tail
    endif -> result;
enddefine;

Notice that in this last version we do a single assignment to RESULT
after the conditional expression (if .... endif). We could have done the
assignment in each branch. We are using the fact that the recursive call
will return a true or false result, which will also be the result of the
caller. See TEACH SETS1 for a slightly different format.

Here is a version using MATCHES

define islement(item, list);
    lvars item, list;
    list matches [== ^item ==]
enddefine;

Note that MATCHES will leave a true or false result on the stack.

This version is equivalent, but makes it clearer that a result is
produced:

define islement(item, list) -> result;
    lvars item, list, result;
    list matches [== ^item ==] -> result;
enddefine;


-- HAPPYMAN -----------------------------------------------------------

Test inputs for happyman

vars
    john = [male happy single clerk tall],
    freda = [female happy married surgeon tall],
    tim  = [male sad single butcher short]
;

;;; Use the procedure iselement defined above, or the system procedure
;;; member.

define happyman(list) -> result;
    ;;; list is a description of an object. Check that it contains
    ;;; both the word "happy" and the word "male"
    lvars list, result;
    if iselement("happy", list) then
        if iselement("male", list) then
            true -> result
        else
            false -> result
        endif
    else
        false -> result
    endif;
enddefine;

;;; test it

happyman(john) =>
happyman(freda) =>
happyman(tim) =>
happyman([cow sad milky]) =>

;;; The above definition can be abbreviated

define happyman(list) -> result;
    lvars list, result;
    if iselement("happy", list) and iselement("male", list) then
        true -> result
    else
        false -> result
    endif;
enddefine;

;;; or

define happyman(list) -> result;
    lvars list, result;
    if iselement("happy", list) and iselement("male", list) then
        true
    else
        false
    endif -> result;
enddefine;

;;; or

define happyman(list) -> result;
    lvars list, result;
    iselement("happy",list) and iselement("male", list) -> result
enddefine;

You should make sure that you can see why each of the above has the same
effect. For this you need to understand how conditionals work, how
output locals work, and how the stack works.

See TEACH DEFINE, TEACH STACK.

-- FINDONE -----------------------------------------------------------


-- -- A note on testing for equality using "==" or "="

In the examples that follow, in the definition of findone, I have used
the test

    if list == [] then

instead of

    if list = [] then

because the empty list [] is a unique object, like an integer 66 or a
word "cat" so we do not need the sophistication of the "=" test. The
latter first checks if two things are identical (the very same unique
object, or the very same integer bit pattern), if not, "=" checks to see
if they are of the same type with the same components. So "=" allows two
different strings with the same characters to be the same, whereas "=="
does not:

'the cat' = 'the cat' =>
** <true>

'the cat' == 'the cat' =>
** <false>

With the empty list, an integer or a word only "==" makes sense, and "="
wastes time when the objects are not ==.

If you want to know more about this see HELP * EQUAL


-- -- Tests for findone

;;; test data for findone

vars
    people = [john ethel mary fred],

    john = [male happy single clerk tall],

    ethel = [female unhappy single prime_minister ],

    mary = [female happy married teacher thin tall],

    fred = [male small typist old];

Try the following test examples on the different versions of findone
defined below.

findone("male", people) =>
findone("old", people) =>
findone("male", rev(people)) =>         ;;; searches in reverse order
findone("female", [john fred]) =>
findone("female", [john mary fred]) =>


-- -- Defining findone

;;; These examples use the system procedure member, rather than the
;;; procedure iselement, defined above

define findone(prop, list) -> result;
    ;;; a recursive version
    lvars prop, list, result;
    if list == [] then
        false -> result;
    elseif member(prop, valof(hd(list))) then
        hd(list) -> result
    else
        findone(prop,tl(list)) -> result
    endif
enddefine;


Explanation:
The following line may not be very clear.
    elseif member(prop, valof(hd(list))) then

The crucial thing is to understand the expression:
    member(prop, valof(hd(list)))

which needs to produce a true or false result. In order to do this it
first has to get the arguments for member. The first is the value of
"prop", so that is just left on the stack. Secondly it has to get the
head of list, which may, for instance be the word "john". Then to get
the list associated with the word it does

    valof(hd(list)) ;;; which might be valof("john")

The following might be an easier version to understand, though it is
somewhat longer to write:

define findone(prop,list) -> result;
    lvars
        prop, list, result,
        name, properties;

    if list == [] then
        false -> result;
    else
        hd(list) -> name;
        valof(name) -> properties;
        if member(prop, properties) then
            name -> result
        else
            findone(prop,tl(list)) -> result
        endif
    endif
enddefine;

Probably this iterative version is clearer:

define findone(prop, list) -> result;
    lvars
        prop, list, result,
        name;
    for name in list do
        if member(prop, valof(name)) then
            name -> result;  return()
        endif
    endfor;
    false -> result;
enddefine;

Here is a version using matches (it will be less efficient - why?)

define findone(prop, list) -> result;
    lvars
        prop, list, result,
        name;
    for name in list do
        if valof(name) matches [ == ^prop ==] then
            name -> result;  return()
        endif
    endfor;
    false -> result;
enddefine;


-- FINDALL ------------------------------------------------------------

-- -- Tests for findall

Use the same test data as for findone, above, in these test commands.

findall("male", people) =>
findall("female", people) =>
findall("hungry", people) =>

define findall(prop, list) -> result;
    ;;; prop is any item, though usually a word, as in the above
    ;;;   examples
    ;;; list is a list of variables whose values are lists.
    ;;; search for all the wors whose values contain prop.
    lvars prop, list, result;
    ;;; This is how teach sets suggests you do it recursively
    if list == [] then
        []                              ;;; nothing to go in the result list
    elseif member(prop, valof(hd(list))) then
        ;;; search the rest of the list and combine the result with
        ;;; the first element
        [^(hd(list)) ^^( findall(prop,tl(list)) )]
    else
        ;;; ignore the first element and search the rest of the list
        findall(prop, tl(list))
    endif -> result
enddefine;

Notice that by now the pattern
    member(...., valof( .... ))

has begun to recur. It can therefore be replaced by a procedure.

define hasprop(prop, name);
    lvars prop, name;
    member(prop, valof(name))
enddefine;

So we can re-write the last procedure:

define findall(prop, list) -> result;
    lvars prop, list, result;
    if list = [] then
        []                              ;;; nothing to go in the result list
    elseif hasprop(prop, hd(list)) then
        [^(hd(list)) ^^( findall(prop,tl(list)) )]
    else
        findall(prop, tl(list))
    endif -> result
enddefine;

Make sure you are convinced that this works, by testing it, and tracing
findall, member and hasprop, to see what is going on.

Here is an iterative version

define findall(prop, list) -> result;
    lvars
        prop, list, result,
        item;
    ;;; put all the items satisfying the test on the stack, and then
    ;;; collect them into a list
    [%
      for item in list do
        if hasprop(prop, item) then item endif
      endfor
    %] -> result
enddefine;

-- FINDSET ------------------------------------------------------------

-- -- Tests for findset
;;; use the lists defined above

findset([happy male], people) =>
findset([happy female], people) =>
findset([tall male], people) =>
findset([tall happy ], people) =>
findset([tall happy female], people) =>
findset([tall happy female single], people) =>

We first need a procedure HASALL which will check that something has all
the properties in a given list. This can use the procedure ISSUBSET,
to be defined below:

vars procedure issubset;    ;;; definition coming

define hasall(proplist, name) -> result;
    lvars
        proplist, name, result,
        list;
    valof(name) -> list;    ;;; the actual list of the person's properties
    issubset(proplist, list) -> result;
enddefine;

Now we can define issubset. We take two lists. For each item in the
first list check that it is in the second. If it isn't, then we can
stop: issubset must produce a false result. If we get to the end without
finding such an item in list1, then every item in list1 is in list2. So
the result for issubset must be true. This version uses member instead
of iselement. Thus:


define issubset(list1, list2) -> result;
    lvars
        list1, list2, result,
        item;
    for item in list1 do
        if not(member(item, list2)) then
            false -> result; return();
        endif
    endfor;
    true -> result;
enddefine;

Note the RETURN() which ensures that issubset stops with a false result
should an item from list1 be found which isn't in list2.

Now we can make a procedure which collects all the things which
have all the properties in a given list of properties:

Take each thing in turn: if it has all the properties, then add
it to the list being produced as the result:

define findset(proplist, thinglist) -> result;
    ;;; a recursive version
    lvars proplist, thinglist, result;
    if thinglist = [] then
        []
    elseif hasall(proplist, hd(thinglist)) then
        [^(hd(thinglist)) ^^(findset(proplist, tl(thinglist)) )]
    else
        findset(proplist, tl(thinglist))
    endif -> result
enddefine;

An iterative version which makes a list by putting relevant names on the
stack, using the list brackets  with '%' symbols (see TEACH PERCENT):

define findset(proplist, thinglist) -> result;
    lvars
        proplist, thinglist, result,
        name;
    [%
        for name in thinglist do
            if hasall(proplist, name) then
                name        ;;; just leave the name on the stack
            endif
        endfor
    %]-> result
enddefine;



--- Originally produced at the University of Sussex

--- $poplocal/local/teach/sets.ans
--- The University of Birmingham 1995.  --------------------------------