/*
TEACH MATCH_SORTED
Aaron Sloman
http://www.cs.bham.ac.uk/~axs
University of Birmingham
Revised version 8 Dec 2011
Also available at
http://www.cs.bham.ac.uk/research/projects/poplog/teach/match_sorted
A video tutorial based on an earlier version of this file (about 49 minutes) is
on Youtube:
http://www.youtube.com/watch?v=fpomSHwuE9c
CONTENTS - (Use <ENTER> g to access required sections)
-- Introduction
-- Defining 'sorted'
-- A standard recursive definition of 'sorted'
-- An alternative approach using 'matches'
-- Defining match_sorted
-- -- Subsidiary procedure 'descends'
-- Improving efficiency using 'doesmatch'
-- Using 'doesmatch' to check ordering
-- Defining doesmatch_sorted
-- Generalising doesmatch_sorted
-- Procedure doesmatch_sorted_any
-- -- Checking whether a list is sorted in increasing order:
-- -- Checking whether a list is sorted in decreasing order:
-- -- subsidiary predicate alpha_ascends
-- -- A more abstract kind of ordering
-- -- subsidiary predicate vowel_odd
-- Partially applying doesmatch_sorted_any
-- -- define predicates increasing and decreasing
-- Further reading-- Introduction -------------------------------------------------------
This teach file shows how using a pattern matcher to check whether a list of
numbers is sorted in increasing order compares with the more conventional way of
defining a procedure to check whether a list is sorted.
The demonstration uses the Pop11 pattern matcher described in
TEACH MATCHES
http://www.cs.bham.ac.uk/research/projects/poplog/teach/matches
and summarised in
HELP MATCHES
http://www.cs.bham.ac.uk/research/projects/poplog/doc/pophelp/matches
It also shows how for some problems solutions will not be found using the
standard Pop-11 operator MATCHES, but can be found using a more powerful version
called DOESMATCH.
For many purposes the former is adequate and in those situations is much faster
than doesmatch. But there are cases where doesmatch is more efficient, as will
be shown, below, and some cases where doesmatch allows a problem to be solved
that cannot be solved using matches.
-- Defining 'sorted' --------------------------------------------------
We'll present a fairly standard definition for the 'sorted' procedure.
*/
/*
PROCEDURE: sorted (list) -> result
INPUTS : list is a list of numbers
OUTPUTS : result is a boolean
USED IN : programs requiring sorted lists of numbers
CREATED : 3 Dec 2011
PURPOSE : test whether a list of numbers is in increasing order
TESTS:
sorted([]) =>
** <true>
sorted([3 5]) =>
** <true>
sorted([5 5]) =>
** <true>
sorted([5 4]) =>
** <false>
sorted([ 1 3 6 6 9 10 14]) =>
** <true>
sorted([ 1 3 6 9 14 10]) =>
** <false>
sorted([9 8 7 6 5 4 3 2 1 ]) =>
** <false>
;;; turn tracing on and off
trace sorted;
untrace sorted;
*/
/*
-- A standard recursive definition of 'sorted'
We assume that every non-empty list L has
a first element, its head: hd(L)
in Lisp that would be (car L)
a sublist containing all the other elements, its tail: tl(L)
in Lisp that would be (cdr L)
So the first element of a list L is hd(L)
The second element is the head of the tail, i.e. hd(tl(L))
in Lisp that would be (car (cdr L)), or (cadr L)
So if L is the list [cat dog mouse elephant horse]
The first item, i.e. hd(L) is the word "cat".
The tail, i.e. tl(L) is the list: [dog mouse elephant horse]
*/
define sorted (list) -> result;
;;; the result of the conditional is assigned to 'result'
if length(list) < 2 then
true
else
;;; check that first two items are in ascending order
hd(list) <= (hd(tl(list)))
;;; and that the tail of the list is in ascending order
and sorted(tl(list))
endif -> result
enddefine;
/*
-- An alternative approach using 'matches' ----------------------------
For variety we define a procedure for checking whether a list is in
descending order.
*/
/*
PROCEDURE: descends (list) -> result
INPUTS : list is a list of numbers
OUTPUTS : result is a boolean
true if the list contains two items in descending order
USED IN : match_sorted (defined below)
CREATED : 3 Dec 2011
PURPOSE : checking whether a larger list is sorted in ascending order,
by looking for exceptions in the list, i.e. two successive numbers
in descending order
TESTS:
descends([1 2])=>
** <false>
descends([2 1])=>
** <true>
descends([])=>
** <false>
descends([3 4 5 2])=>
** <false>
descends([2 99])=>
** <false>
descends([200 99])=>
** <true>
-- Defining match_sorted ----------------------------------------------
We'll now show how to define a procedure match_sorted that uses the Pop11
pattern matcher, and then go on to discuss some of its problems. First we need a
subsidiary procedure that is given a list of numbers and checks whether it is a
list of two items where the second is smaller than the first: i.e. it's no good
when we are looking for lists sorted in increasing order.
-- -- Subsidiary procedure 'descends'
*/
define descends(list) -> result;
;;; result is true if list is of length 2 and items
;;; are in decreasing order
lvars x, y;
list matches ! [?x ?y] and x > y -> result;
enddefine;
/*
PROCEDURE: match_sorted (list) -> result
INPUTS : list is a list of numbers
OUTPUTS : result is a boolean
USED IN : programs requiring sorted lists of numbers
CREATED : 3 Dec 2011
PURPOSE : test list for increasing numerical order, by checking that
list does not contain two successive numbers where the
the first is bigger than the second.
NOTE : This procedure depends on the fact that the pop11 matcher allows
pattern variables to have 'restrictions' attached, as described in
HELP * MATCHES. So if '??items is a pattern variable, then it will match any
sequence of elements of the datum list allowed by other constraints in the
pattern. E.g. '= = = ??items =' will only allow items to match a list that is
preceded by at least three members of the list with at least one member
following. There may be many sublists that satisfy this condition. If you want
the list items to have exactly three elements then you can add the restriction ':3'
as in
= = = ??items:3 =
which requires the matcher to find at least 7 sequential items in the datum, and
make a list containing the fourth fifth and sixth to assign to the variable
items.
If you have a predicate, such as descends, defined above which returns true ONLY
for a two element list whose first element is bigger than the second, then you
can use ':descends' to restrict the possible values of items, as in
??items:descends
That what is used in the definition of match_sorted below, to make it return
false, if it finds any sublist of two items satisfying descends. If no such
sublist is found then the match_sorted(list) returns true.
TESTS:
match_sorted([]) =>
match_sorted([3 5]) =>
match_sorted([5 5]) =>
match_sorted([5 4]) =>
;;; should be true
match_sorted([ 1 3 6 9 10 14]) =>
;;; should be false
match_sorted([ 1 3 6 9 14 10]) =>
;;; should be false
match_sorted([9 8 7 6 5 4 3 2 1 ]) =>
;;; should be false
match_sorted([ 1 3 6 9 14 10 19 30 2000]) =>
;;; should be true
match_sorted([ 1 3 6 9 14 18 19 30 2000]) =>
;;; should be false
match_sorted([5 1 3 6 9 14 18 19 30 2000]) =>
;;; Try with descends traced:
trace descends
untrace descends
*/
define match_sorted(list) -> result;
lvars items;
;;; it's sorted if no sublist of length 2 descends
not(list matches ![== ??items:descends ==]) -> result
enddefine;
/*
-- Improving efficiency using 'doesmatch'
The match_sorted procedure works and, for people who are not used to recursion,
and for non-programmers or beginner programmes, it can be seen to work in a
manner that probably fits more closely the intuitions of non-programmers (and
beginner programmers) as to what it means for a list of numbers to be sorted in
increasing order. Namely, there must not be a pair of adjacent items in
descending order.
But the pattern used in the definition of match_sorted cannot prevent the
program from trying all sorts of sublists of list, to see if they fail on the
descends test.
For example if we give it this problem
match_sorted([1 2 3]) =>
It produces the right answer, but only after applying the descends procedure to
many irrelevant sublists, including all the empty lists found between successive
pairs of items in the input list. 'match_sorted' produces the result <true>
because it finds no descending pair in the list.
We can demonstrate this inefficiency by telling the descends procedure to trace
its behaviour, i.e. print out records of what it does and what results it
produces.
trace descends ;
match_sorted([1 2 3]) =>
That produces
> descends []
< descends <false>
> descends [1]
< descends <false>
> descends [1 2]
< descends <false>
> descends [1 2 3]
< descends <false>
> descends []
< descends <false>
> descends [2]
< descends <false>
> descends [2 3]
< descends <false>
> descends []
< descends <false>
> descends [3]
< descends <false>
> descends []
< descends <false>
** <true>
The trace printing is very verbose because there are many ways in which
the list 'items' can be selected from the whole list as required in the
definition of the procedure match_sorted, above.
match_sorted([1 2 3 4]) =>
It finds a mis-ordering quickly if it is near the beginning of the list
match_sorted([2 1 3 4]) =>
> descends []
< descends <false>
> descends [2]
< descends <false>
> descends [2 1]
< descends <true>
** <false>
but wastes more time if the first bad pair is near the end of the list
match_sorted([1 2 4 3]) =>
Turn off tracing:
untrace descends ;
The difference in efficiency between the original procedure
PROCEDURE: sorted (list) -> result
and the later one that is easier for many people to understand because
it uses the list matcher
PROCEDURE: match_sorted (list) -> result
may not matter for many simple programs, but for programs that create
very long lists it can make a significant difference.
The problem is that for examples like this we need a way to tell the
test procedure to look only at successive pairs of items in the list
being test, and not to look at all sublists. That is hard to do with the
notation available when using 'matches'.
There is an alternative mechanism in Pop11 that keeps the intuitive
'pictorial' format of the solution but is much more efficient on long
lists.
-- Using 'doesmatch' to check ordering --------------------------------
There is a library called LIB DOESMATCH, described in
HELP DOESMATCH
and
http://www.cs.bham.ac.uk/research/projects/poplog/help/doesmatch
that can be used to find the same wrongly sorted lists as match_sorted
finds, but is much more efficient because it does not waste time on
irrelevant sub-cases.
The 'doesmatch' operator can be used in the same way as 'matches',
though with greater generality, and less speed. But it can also be used
to perform searches inside a list structure that 'matches' cannot do.
For that purpose we'll use the format:
<list> doesmatch <pattern> where <condition>
This expression is a boolean expression, i.e. it produces a true or
false result, and in the process it can bind some variables used in the
<pattern>, provided that the satisfy the tests in <condition>.
We'll see that doesmatch can be controlled a lot more precisely than
matches, because after doesmatch has found a match involving more than
one variable, the results found can be tested in the final expression:
<condition>
-- Defining doesmatch_sorted ------------------------------------------
*/
;;; load the doesmatch library
uses doesmatch;
/*
PROCEDURE: doesmatch_sorted (list) -> result
INPUTS : list is a list of numbers
OUTPUTS : result is a boolean
USED IN : programs requiring sorted lists of numbers
CREATED : 3 Dec 2011
PURPOSE : test for increasing order
TESTS:
doesmatch_sorted([]) =>
doesmatch_sorted([3 5]) =>
doesmatch_sorted([5 5]) =>
doesmatch_sorted([5 4]) =>
doesmatch_sorted([ 1 3 6 9 10 14]) =>
doesmatch_sorted([ 1 3 6 9 14 10]) =>
doesmatch_sorted([ 1 3 6 9 14 10 11 12 13 16]) =>
doesmatch_sorted([9 8 7 6 5 4 3 2 1 ]) =>
doesmatch_sorted([ 1 3 6 9 14 10 19 30 2000]) =>
doesmatch_sorted([ 1 3 6 9 14 18 19 30 2000]) =>
doesmatch_sorted([ 1 3 6 9 14 18 19 30 2000 1]) =>
doesmatch_sorted([5 1 3 6 9 14 18 19 30 2000]) =>
*/
define doesmatch_sorted(list) -> result;
lvars item1, item2;
not(list doesmatch ![== ?item1 ?item2 ==] where item1 > item2) -> result
enddefine;
/*
-- Generalising doesmatch_sorted --------------------------------------
Suppose we wanted to recognise lists of numbers that are sorted in
descending order, instead of ascending order? What would we have to
change? Just the '>' test in the 'where' expression.
That's easy enough to do, but suppose we wanted to check if a list of
words is in alphabetical order, or in reverse alphabetical order.
Or suppose we had a mixed list of letters and numbers and wanted to make
sure that no vowel is followed by an odd number, what would we have to
change?
We can come back to that below. For now, lets notice that the generality
of the algorithm can be expressed by taking the '<' test out of the
procedure definition and instead requiring it to be given as an input to
a new version of doesmatch_sorted that takes a list of any type and an
ordering test for two successive elements.
We can then use it to do what doesmatch_any did by giving it the pop11
procedure '>' (which we have to refer to as 'nonop >' when it is not
actually being used, only referred to).
That's true of all the 'infix' operators, '+', '-', '*', '>' '<' '>='
etc. We can use them without 'nonop' when we want them to run, but if we
simply want to refer to them, e.g. by passing them as inputs to a
procedure, then we need to use 'nonop', as shown below.
If we have the generic procedure, then making it test for lists of
numbers in descending order, or lists of words alphabetically ordered,
or lists of varied types of objects with an ordering restraint, then all
we have to do is give it an appropriate ordering predicate as its second
argument.
First we define the generic procedure.
-- Procedure doesmatch_sorted_any -------------------------------------
*/
/*
PROCEDURE: doesmatch_sorted_any (list, wrong_order) -> result
INPUTS : list, wrong_order
Where :
list - is a list of any items
wrong_order - is a relation, or two-place predicate used to
identify items that are in the wrong order in a larger list.
OUTPUTS : result is a boolean
USED IN : Below
CREATED : 3 Dec 2011
PURPOSE : see above
TESTS:
See below.
*/
define doesmatch_sorted_any(list, wrong_order) -> result;
lvars item1, item2;
;;; true if no two items are in the wrong order
not(list doesmatch ![== ?item1 ?item2 ==] where wrong_order(item1, item2) )
-> result
enddefine;
/*
We can define a number of different subsidiary predicates to be given as
the second input to doesmatch_sorted_any
We don't need to define procedures for testing numerical order, as we
can use these as inputs to the new sorting procedure. Remember the input
procedure is one that checks for items in the WRONG order
-- -- Checking whether a list is sorted in increasing order:
USE nonop > (to specify the '>' test)
Use this to check that items are in increasing order, i.e.
any pair item1 > item2 means the test is failed.
doesmatch_sorted_any([], nonop >) =>
doesmatch_sorted_any([1 3 5], nonop >) =>
doesmatch_sorted_any([1 3 5 4 6], nonop >) =>
doesmatch_sorted_any([1 99 200 9999 100000], nonop >) =>
doesmatch_sorted_any([1 99 200 9999 100001 100000], nonop >) =>
-- -- Checking whether a list is sorted in decreasing order:
USE nonop < (to specify the '<' test)
Use this to check that items are in decreasing order, i.e.
any pair item1 < item2 means false
doesmatch_sorted_any([], nonop <) =>
;;; Remember doesmatch_sorted_any returns true if it finds NO pair
;;; if numbers satisfying the test predicate.
;;; decreasing should be false
doesmatch_sorted_any([1 3 5], nonop <) =>
;;; decreasing should be true
doesmatch_sorted_any([5 3 2 1], nonop <) =>
;;; decreasing should be true
doesmatch_sorted_any([6 5 4 3 3 2 1 1], nonop <) =>
;;; decreasing false
doesmatch_sorted_any([6 5 2 4 3 3 2 1 1], nonop <) =>
;;; decreasing should be true
doesmatch_sorted_any([100000 9999 200 88 1], nonop <) =>
;;; decreasing false
doesmatch_sorted_any([100000 100001 9999 200 88 1], nonop <) =>
;;; Make sure you understand all those result by identifying the items in
;;; increasing order that produce the result false.
-- -- subsidiary predicate alpha_ascends
Pop11 already includes a predicate 'alphabefore' that tests whether a
word (or string) is alphabetically prior to another string, so we can
also use that in our tests.
;;; The predicate alpha_ascends was called alpha_after in a previous
;;; version.
define alpha_ascends(word1, word2) -> result;
;;; true if word1 comes alphabetically after word2
;;; they are different words
word1 /= word2
;;; and word2 comes before word1
and
alphabefore(word1, word2) -> result;
enddefine;
We can use that as a recognizer for lists that are ordered in reverse
alphabetic order, i.e. descending alphabetic order. We used alpha_ascends
to look for violations. The test produces true if no violations are found.
doesmatch_sorted_any([pear fig apple], alpha_ascends) =>
** <true>
doesmatch_sorted_any([pear fig apple appm], alpha_ascends) =>
** <false>
doesmatch_sorted_any([pear fig apple banana], alpha_ascends) =>
** <false>
doesmatch_sorted_any([pear fig elephant apple], alpha_ascends) =>
** <true>
doesmatch_sorted_any([pear fig elephant apple banana], alpha_ascends) =>
** <false>
doesmatch_sorted_any([pear tomato fig elephant apple banana], alpha_ascends) =>
** <false>
;;; By tracing alpha_ascends we can see how much testing is done before an
;;; exception is found, if one is found.
trace alpha_ascends
;;; turn off tracing
untrace alpha_ascends
;;; Create some more test examples with words using upper and lower
;;; case, and see what happens.
*/
/*
-- -- A more abstract kind of ordering
Our tests so far have have checked a list by searching for two items that
violate some ordering requirement, e.g. the first item is alphabetically or
numerically earlier than or later than the second item. Finding such a pair
shows that a whole list fails to be ordered, and failing to find such a pair
shows that the whole list is ordered.
In all those cases the common process is searching along a list for two items
satisfying a condition, and such a pair is found the search terminates, and the
searching procedure returns false. If it gets to the end without finding such a
pair (the search as failed) then the procedure returns true.
The method used can be equally be applied to other kinds of test. Suppose we
have a list providing information about employees. The list has successive pairs
of items,
employee name, employee status, employee name, employee status,
where the status is one of paid, left, sacked, unpaid, and we want
to check that none of the employees is still unpaid.
If we can define a procedure that checks for that combination, when given a name
and a status we can use it to search a list:
*/
define employee_unpaid(employee, status) -> result;
if status = "unpaid" then
true -> result;
;;; print out the discovery
[^employee ^status] =>
else
false -> result
endif;
enddefine;
/*
This can be used with doesmatch_sorted_any to search for unpaid employees.
;;; this finds a problem employee and returns false
doesmatch_sorted_any([tom paid fred left mary unpaid sue sacked], employee_unpaid) =>
** [mary unpaid]
** <false>
;;; this finds all employees OK and returns true
doesmatch_sorted_any([tom paid fred left mary left sue sacked], employee_unpaid) =>
** <true>
-- -- subsidiary predicate vowel_odd
The procedure can also be used with a list of items of mixed type. Pop11 does
not require all list items to be of the same type. (See TEACH LISTS).
Suppose we have a list containing single letter words, e.g. "a", "f" "K", "z"
and numbers. And suppose that for some reason we want only lists where every
vowel is immediately followed by an even number. We don't care if there are no
vowels occur, and we don't care if some consonants are followed by an even
number. But if we find a vowel followed by an odd number we want our search to
return false. If there's no such case, the list is OK and it should return true.
We shall use the pop11 operator 'rem' to test whether a number is odd or
even by checking whether its remainder on division by 2 is 1 or 0.
'rem' takes two numbers and returns the remainder:
77 rem 10 =>
** 7
77 rem 5 =>
** 2
6 rem 2 =>
** 0
9 rem 2 =>
** 1
So 6 is even and 9 is odd.
In order to use the procedure doesmatch_sorted_any to perform the search task
just described we'll need to give it a predicate taking two items to test, with
result false only if the first item is a word containing a vowel and the second
is NOT an even number, i.e. it's an odd number. We can call the procedure
vowel_odd to indicate that it is being used to indicate the unwanted
combination.
(This example has been slightly modified since the video tutorial was created.)
*/
define vowel_odd(item1, item2) -> result;
;;; item1 is a word and item2 is an integer
isword(item1) and isinteger(item2)
;;; the word has only one character
and length(item1) = 1
;;; which is a vowel, not a consonant
and member(item1, [a e i o u A E I O U])
;;; the number is odd -- remainder on dividing by 2 is 1
and ( item2 rem 2 = 1 )
-> result
;;; so result will be true or false depending on the
;;; outcome of the four tests.
enddefine;
/*
;;; test it
;;; work out what the result should be in each case, and run the test.
vowel_odd("a", 4) =>
vowel_odd("e", 5) =>
vowel_odd("O", 4) =>
vowel_odd("A", 5) =>
vowel_odd("b", 5) =>
vowel_odd("b", 6) =>
;;; what about
vowel_odd("apple", 4) =>
vowel_odd("egg", 5) =>
Only two of those cases will indicate that our requirement, has been violated
because a vowel is followed by an odd number. If that's true any list containing
those two items in success is no good if our requirement is as stated above.
We can use that procedure to complain about lists where a word of length
one containing a vowel is followed by an even number, and accept all
others:
;;; Work out what the result should be for each of the following.
;;; Remember the result <true> means the list does NOT violate the
;;; requirement.
doesmatch_sorted_any([], vowel_odd ) =>
doesmatch_sorted_any([ 15 76 9 ], vowel_odd ) =>
doesmatch_sorted_any([ a b c d e ], vowel_odd ) =>
doesmatch_sorted_any([ a 3 b 4 c 5 d 6 e 7 ], vowel_odd ) =>
;;; turn on tracing for vowel_odd
trace vowel_odd;
;;; this tries many pairs before the vowel_odd procedure finds the
;;; exception, and returns true, so the whole thing returns false
doesmatch_sorted_any([ a 2 b 4 c 5 d 6 e 7 ], vowel_odd ) =>
> vowel_odd a 2
< vowel_odd <false>
> vowel_odd 2 b
< vowel_odd <false>
> vowel_odd b 4
< vowel_odd <false>
> vowel_odd 4 c
< vowel_odd <false>
> vowel_odd c 5
< vowel_odd <false>
> vowel_odd 5 d
< vowel_odd <false>
> vowel_odd d 6
< vowel_odd <false>
> vowel_odd 6 e
< vowel_odd <false>
> vowel_odd e 7
< vowel_odd <true>
** <false>
;;; this one stops much sooner because an exception is found quickly:
doesmatch_sorted_any([ a 5 b 4 c 9 d 6 e 7 ], vowel_odd ) =>
> vowel_odd a 5
< vowel_odd <true>
** <false>
;;; here no exception is found (all tests are false), so the procedure
;;; returns true
doesmatch_sorted_any([ a 6 b 4 c 9 d 6 e 2 g 2 i 8 ], vowel_odd ) =>
> vowel_odd a 6
< vowel_odd <false>
> vowel_odd 6 b
< vowel_odd <false>
> vowel_odd b 4
< vowel_odd <false>
> vowel_odd 4 c
< vowel_odd <false>
> vowel_odd c 9
< vowel_odd <false>
> vowel_odd 9 d
< vowel_odd <false>
> vowel_odd d 6
< vowel_odd <false>
> vowel_odd 6 e
< vowel_odd <false>
> vowel_odd e 2
< vowel_odd <false>
> vowel_odd 2 g
< vowel_odd <false>
> vowel_odd g 2
< vowel_odd <false>
> vowel_odd 2 i
< vowel_odd <false>
> vowel_odd i 8
< vowel_odd <false>
** <true>
;;; Now create some more tests of your own, and run them. In each case try
;;; to work out whether the result is true or false, and if false exactly
;;; which pair of numbers vowel_odd will return false for.
;;; untrace vowel_odd
untrace vowel_odd;
-- Partially applying doesmatch_sorted_any ----------------------------
This section is an optional extra. It illustrates a very useful feature of pop11
using the procedure doesmatch_sorted_any as an example to which the feature can
be applied.
A generic procedure that performs a task in different ways that depend
on one or more of its inputs can be used to construct a specific
procedure by constructing a 'closure' of the generic procedure.
In a closure the procedure is partially applied to the last argument it could be
given for doing something.
(The last two, or the last three, or four, etc. arguments could be frozen.
We'll illustrate only the simplest case.)
-- -- define predicates increasing and decreasing
define increasing = doesmatch_sorted_any(% nonop > %);
enddefine;
define decreasing = doesmatch_sorted_any(% nonop < %);
enddefine;
increasing([ 1 2 4 6 7 8 ]) =>
** <true>
increasing([ 1 2 4 6 3 7 8 ]) =>
** <false>
decreasing([ 1000 555 230 110 3]) =>
** <true>
decreasing([ 1000 555 600 230 110 3]) =>
** <false>
;;; Now show how doesmatch_sorted_any can be partially applied to two other
;;; procedures operating on words, to produce a procedure to detect whether
;;; a list of words is sorted in increasing alphabetic order and another to
;;; detect whether a list of words is in decreasing alphabetic order.
;;; Hint: for one case you can use the procedure alpha_ascends, defined above.
-- Exercise -----------------------------------------------------------
Can you define a procedure, partly modelled on doesmatch_sorted_any that takes
a list of numbers and checks both that all the numbers are in ascending order,
that there are no repetitions, and that no two adjacent numbers differ by more
than 6.
Can you define a procedure, partly modelled on doesmatch_sorted_any that takes
a list of numbers and checks both that all the numbers are in ascending order,
that there are no repetitions, and that no three successive numbers differ by
more than 6.
-- Further reading ----------------------------------------------------
TEACH DEFINE
TEACH STACK
TEACH SORT
creates a sorted copy of a list of words or numbers
HELP SYSSORT
explains a generic Pop11 sorting library.
TEACH * PERCENT
contains simple tutorial information on closures
HELP CLOSURES
More information on closures
--- $usepop/pop/teach/match_sorted
--- Copyright University of Birmingham 2011. All rights reserved.
*/