[r6rs-discuss] Comparison procedures' number of arguments
Ken.Dickey at whidbey.com
Tue Oct 21 15:53:19 EDT 2008
On Tuesday 21 October 2008 12:53:32 Thomas Lord wrote:
> Ken Dickey wrote:
> > Comparison is taught in kindergarden. Comparison is fundamental.
> And in algebra. Things I didn't see taught in high school
> were definitions for relation, transitive relation, reflexive
> relation, symmetric relation, partial order, total order,
> and equivalence along with proof techniques that use those
> > In 40 years of software development I have never seen a sequence outside
> > the classroom. I write code which compares quantities all the time.
> Surely you do see and use sequences (and their properties)
> all the time. It's probably just automatic and stays in the
> back of your mind rather than something you explicitly
> think about. For example, you know that if you raise a total
> ordering of characters to a lexical ordering of strings that the
> resulting lexical order is a total order.
> > Given multiple models, isn't it more natural to define something more
> > abstract (e.g. num-seq, see below) which models the properties you want
> > rather than trying to overgeneralize comparison predicates?
> Well, remember, you earlier convinced me that (it is at least
> one reasonable approach) to have all of the numeric relation
> predicates be binary -- arity 2. So, (< 1) is an error
> and so is (< 1 2 3).
> I think that does raise the question of how one can
> write a generic "sequence-pairwise?" rather than
> having to use "numeric-sequence-pairwise?" but that's
> a whole separate question.
Well if I write it... ;^)
(assert (list? list-of-numbers))
(assert (for-all number? list-of-numbers))
(monotonic? < list-of-numbers)
(assert (list? list-of-char))
(assert (for-all char? list-of-char))
(monotonic? char<? list-of-char)
(define (monotonic? ordered? sequence)
(let ( [list-of-pairs (pairs-in sequence)] )
(lambda (pair) (ordered? (car pair) (cdr pair)))
(define (pairs-in seq)
(assert (list? seq))
(if (or (null? seq)
(null? (cdr seq)))
(let loop ( [pairs (list (cons (car seq) (cadr seq)))]
[next (cadr seq)]
[rest (cddr seq)]
(if (null? rest)
(loop (cons (cons next (car rest)) pairs)
) ) )
> > Because
> > () is monotonically decreasing and
> > () is monotonically increasing and
> > () is a desert topping and a floor wax
> > () is the pope
> > (2) is monotonically decreasing and
> > (2) is monotonically increasing
> > ???
> > Doesn't it make more sense to require existence for comparison?
> And then we could look at how relations are normally
> defined: as ordered pairs. For example, in this way of
> talking about it, "<" is a name for the class of all pairs
> of numbers where the first number is less than the second.
Quibble: In Scheme, "<" is the name of a function.
A "relation on a pair" implies that there must be a pair to be a relation.
When I look up "binary relation" in Wikipedia I find:
The statement (x,y) ∈ R is read "x is R-related to y", and is denoted by xRy
or R(x,y). The latter notation corresponds to viewing R as the characteristic
function of the _set of pairs_ G. [emphasis mine]
There is no mention of a binary relation on non-pairs.
If I look up "well ordered" I find:
In mathematics, a well-order relation (or well-ordering) on a set S is a total
order on S with the property that every _non-empty subset_ of S has a least
element in this ordering. Equivalently, a well-ordering is a well-founded
total order. The set S together with the well-order relation is then called a
Every element, except a possible greatest element, has a unique successor
I.e. the null sequence/set is explicitly excluded. Given that S must be
ordered, it follows from the (binary) order relation such a set must have at
least two elements to relate [my reading].
> Std definition => "a singleton or empty list is well ordered"
> Ken's definition => "a singleton or empty list is neither well
> ordered or not ordered"
Ken's definition => "a singleton or empty list is _not_ ordered".
More information about the r6rs-discuss