TEACH LISTANSWERS                                          A. Sloman Feb 1984

24 Aug 1999: Bug in one of the answers to question 1, fixed.


                        Answers to TEACH LISTQUESTIONS
                        ==============================

There are no 'right' answers. Any of the problems could be solved in different
ways, using different  programming techniques. Some of the  answers given here
use recursive procedures, because these are  easier to trace. However, in most
cases you  may find it  easier to understand  versions using UNTIL,  or WHILE.
When  testing programs  which do  'WHILE ...  MATCHES  ...' you  can do  TRACE
MATCHES; to get a better idea of what is going on.

1)      define listify(list) -> result;
              vars next,tail;
              [] -> result;           ;;; initialise result
              while   list matches [?next ??tail]
              do      [^^result [^next] ] -> result;
                      tail -> list;
              endwhile
        enddefine;

Note that MATCHES  is  used  both to tell when it's time to stop, and to
decompose  the  LIST into first element and the rest. It is essential to
initialise RESULT, in line 3, otherwise the use of result in line 5 will
cause problems the first time round the loop. Why?

Here's a version which aviods the extra variable RIGHTS, and lets MATCHES
assign  all  but  the  first element of LIST to LIST each time round the
loop.  If  you  use  this  construction  be  very  careful  not  to   do
Tl(LIST) -> LIST in addition to using ??LIST in the call of match.
        define listify(list) -> result;
              vars next;
              [%
                 while list matches [?next ??list]
                 do    [^next ]
                 endwhile
              %] -> result
        enddefine;

This version uses [% ... %] to make a list of all the things put on  the
stack  inside the UNTIL loop. The thing put on the stack each time round
the loop is the list made just after DO, i.e. a  list  containing  NEXT.
Notice  that  each  time  round  the  loop  LIST  will be different, and
therefore so will NEXT.

Here's a recursive version:
        define listify(list) -> result;
              vars x,rest;
              if      list matches [?x ??rest]
              then    listify(rest) -> result;   ;;; temporary
                      [ [^x] ^^result] -> result;
              else    [] -> result
              endif
        enddefine;

or, equivalently, but more compact:
        define listify(list) -> result;
              vars x;
              if      list matches [?x ??list]
              then    [[^x] ^^( listify(rest) ) ]
              else    []
              endif -> result
        enddefine;

Here is a version using the FOR construction:

        define listify(list) -> result;
              vars next;
              [ ^( for next in list do [^next ] endfor ) ] -> result
        enddefine;


Which of these versions do you find clearest?  If you try  HELP  MAPLIST
you may be able to find a more compact definition.


                ----------------------------------------

2)      define doublel(list) -> result;
              vars x;
              [% for x in list do [% x + x %] endfor %] -> result
        enddefine;

or      define doublel(list);
              maplist(list, procedure (x); 2 * x endprocedure)
        enddefine;

Note 'PROCEDURE' in POP11 introduces an anonymous procedure. Here the
anonymous procedure doubles its input.

                ----------------------------------------

3)      define countw(list, item) -> total;
            ;;; count occurrences of item in list
              0 -> total;
              while   list matches [== ^item ??list ]
              do      1 + total -> total;
              endwhile
        enddefine;

Note the need to initialise total before the  loop  begins.  Why?   Note
that  LIST  gets  a different value each time round the WHILE loop. Why?
You may find it helpful to TRACE MATCHES; if you test this.

Here's a recursive version
        define countw(list, item);
            if list = [] then 0
            elseif list matches [^item ??list] then
                1 + countw(list,item)
            else
                countw(tl(list),item)
            endif
        enddefine;
                ----------------------------------------

4) Here's a version using FOR

        define countp(list,pred) -> total;
            ;;; return number of things in list which satisfy pred
            vars item;
            0 -> total;
            for item in list do
                if pred(item) then total + 1 -> total endif
            endfor
        enddefine;

Here's a recursive method:
        define countp(list,pred) -> total;
              vars x,rest;
              if      list matches [?x ??rest]
              then    countp(rest, pred) -> total;   ;;;temporary
                      if      pred(x)
                      then    1 + total -> total
                      endif;
              else    0 -> total
              endif
        enddefine;

You may find the following easier to understand:

        define countp(list,pred) -> total;
              vars x;
              0 -> total;
              while   list matches [== ?x:pred ??list]
              do      1 + total -> total
              endwhile
        enddefine;

This occurrence of ':PRED' after X restricts the match, so that it  will
only accept values for X such that PRED(X) is TRUE.

This could have been used in the answer to question 3, e.g.:
        define countw(list,item);
              countp(list, procedure (x); x = item endprocedure)
        enddefine;

                ----------------------------------------

5) First an iterative answer:

    define allbefore(list,word) -> result;
        vars item;
        [ ^(for item in list do
                if item = word then quitloop() else item endif
            endfor)] -> result;
    enddefine;


A recursive version:

define allbefore(list,word)-> result;
              vars x;
              if      list matches [?x ??list]
              and     x /= word
              then    [^x  ^^( allbefore(rest, word) ) ] -> result;
              else    [] -> result
              endif
        enddefine;

Try tracing that procedure to see where it stops.  It's much  easier  to
define ALLBEFORE using MATCHES!

    define allbefore(list,word) -> result;
        unless list matches [??result ^word ==] then
            list -> result
        endunless
    enddefine;

                ----------------------------------------

6)      define allafter(list,word)-> result;
              if      list = []
              then    [] -> result
              elseif  hd(list) = word
              then    tl(list) -> result
              else    allafter(tl(list),word) -> result
              endif
        enddefine;

Again, using MATCHES makes this much easier:
        define allafter(list,word) -> result;
              unless  list matches [ == ^word ??result]
              then    [] -> result
              endunless
        enddefine;

Note how the value of RESULT is set by MATCHES if the WORD is found in
LIST.

                ----------------------------------------

7)      define addup(list)-> sum;
              if      list = []
              then    0 -> sum
              else    hd(list) + addup(tl(list)) -> sum
              endif
        enddefine;

or
        define addup(list) -> sum;
            vars x;
            0 -> sum;
            for x in list do
                sum + x -> sum
            endfor;
        enddefine;

                ----------------------------------------

8)      define more(list1,list2)->bigger;
              if      addup(list1) > addup(list2)
              then    list1 -> bigger
              else    list2 -> bigger
              endif
        enddefine;

                ----------------------------------------

9)
        define repeated(list) -> result;
              vars x,rest;
              [%while list matches [ ?x ??rest] do
                      if rest matches [^x ==] then x endif;
                      rest -> list
               endwhile %] -> result
        enddefine;

How would this have to be different if it was to produce all items which
occurred more than once in the list, not necessarily consecutively?

                ----------------------------------------

10)     define merge(list1,list2)-> result;
              vars x,y;
              [%while list1 matches [?x ??list1]
                  and list2 matches [?y ??list2]
                do    x, y
                endwhile %] -> result;
        enddefine;

What should happen if the lists are of different lengths?

                ----------------------------------------

11)
        define insert(num,list) -> result;
            vars x, y, firstbit;
            [%while list matches [?x ??y] and x < num do
                     x;
                     y -> list;
                 endwhile%] -> firstbit;
            [^^firstbit ^num ^^list] -> result;
        enddefine;

More compactly
        define insert(num,list) -> result;
            vars x, y ;
            [%while list matches [?x ??y] and x < num do
                     x;
                     y -> list;
              endwhile, num % ^^list] -> result;
        enddefine;

Compare:
        define insert(num, list) -> result;
              vars firstbit;
              [%until list = [] or num < hd(list) do
                      hd(list);
                      tl(list) -> list;
                enduntil%] -> firstbit;
              [^^firstbit ^num ^^list] -> result;
        enddefine;

Or a recursive version:
        define insert(num,list) -> result;
            if list = [] or num < hd(list) then
                [^num ^^list]
            else [^(hd(list)) ^^(insert(num, tl(list))) ]
            endif -> result
        enddefine;

                ----------------------------------------

12)
        define sort(list) -> result;
              vars item;
              [] -> result;
              for item in list do
                      insert(item, result) -> result
              endfor
        enddefine;

OR a recursive version
        define sort(list) -> result;
              if      list = []
              then    [] -> result
              else    sort(tl(list)) -> result;    ;;; temporary value
                      insert(hd(list), result) -> result;
              endif
        enddefine;
Notice that POP11 doesn't really mind if you use the same  variable  for
output  as  for input, in this case LIST. It could have be done for some
of the earlier answers too.

13)
        vars memory;     [] -> memory;

        define store(pattern);
                [^pattern ^^memory] -> memory
        enddefine;

        define known(pattern)->result;
                memory matches [== ^pattern ==] -> result
        enddefine;

        define recall(pattern);
                unless  known(pattern) then
                  mishap('RECALL ERROR - PATTERN NOT FOUND', [^pattern])
                endif
        enddefine;

        define forget(pattern);
                vars item;
                [%for item in memory do
                        unless  item matches pattern
                        then    item
                        endunless
                endfor%]
                        ->memory
        enddefine;

                ----------------------------------------

14)
        define picpoints()->list;
            vars x y;
            [] -> list;

            for x from 1 to xmax do
                for y from 1 to ymax do
                    if      picture(x,y) /= space
                    then    [[^x ^y]  ^^list] -> list
                    endif
                endfor
            endfor
        enddefine;


See TEACH PICTURES for more on this.
