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. --------------------------------