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
> definitions.
>
> > 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.
Huh?
Well if I write it... ;^)
(define <?
(lambda list-of-numbers
(assert (list? list-of-numbers))
(assert (for-all number? list-of-numbers))
(monotonic? < list-of-numbers)
) )
(define char-<?
(lambda list-of-char
(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)] )
(and list-of-pairs
(for-all
(lambda (pair) (ordered? (car pair) (cdr pair)))
list-of-pairs))
) )
(define (pairs-in seq)
(assert (list? seq))
(if (or (null? seq)
(null? (cdr seq)))
#f
(let loop ( [pairs (list (cons (car seq) (cadr seq)))]
[next (cadr seq)]
[rest (cddr seq)]
)
(if (null? rest)
pairs
(loop (cons (cons next (car rest)) pairs)
(car rest)
(cdr rest)))
) ) )
...
> > 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
well-ordered set.
Every element, except a possible greatest element, has a unique successor
(next element).
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"
should read:
Ken's definition => "a singleton or empty list is _not_ ordered".
Cheers,
-KenD
_______________________________________________
r6rs-discuss mailing list
[email protected]
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
