diff options
Diffstat (limited to 'src/algebra/setorder.spad.pamphlet')
-rw-r--r-- | src/algebra/setorder.spad.pamphlet | 186 |
1 files changed, 186 insertions, 0 deletions
diff --git a/src/algebra/setorder.spad.pamphlet b/src/algebra/setorder.spad.pamphlet new file mode 100644 index 00000000..198d8d85 --- /dev/null +++ b/src/algebra/setorder.spad.pamphlet @@ -0,0 +1,186 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra setorder.spad} +\author{Manuel Bronstein} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{package UDPO UserDefinedPartialOrdering} +<<package UDPO UserDefinedPartialOrdering>>= +)abbrev package UDPO UserDefinedPartialOrdering +++ Author: Manuel Bronstein +++ Date Created: March 1990 +++ Date Last Updated: 9 April 1991 +++ Description: +++ Provides functions to force a partial ordering on any set. +UserDefinedPartialOrdering(S:SetCategory): with + setOrder : List S -> Void + ++ setOrder([a1,...,an]) defines a partial ordering on S given by: + ++ (1) \spad{a1 < a2 < ... < an}. + ++ (2) \spad{b < ai for i = 1..n} and b not among the ai's. + ++ (3) undefined on \spad{(b, c)} if neither is among the ai's. + setOrder : (List S, List S) -> Void + ++ setOrder([b1,...,bm], [a1,...,an]) defines a partial + ++ ordering on S given by: + ++ (1) \spad{b1 < b2 < ... < bm < a1 < a2 < ... < an}. + ++ (2) \spad{bj < c < ai} for c not among the ai's and bj's. + ++ (3) undefined on \spad{(c,d)} if neither is among the ai's,bj's. + getOrder : () -> Record(low: List S, high: List S) + ++ getOrder() returns \spad{[[b1,...,bm], [a1,...,an]]} such that the + ++ partial ordering on S was given by + ++ \spad{setOrder([b1,...,bm],[a1,...,an])}. + less? : (S, S) -> Union(Boolean, "failed") + ++ less?(a, b) compares \spad{a} and b in the partial ordering induced by + ++ setOrder. + less? : (S, S, (S, S) -> Boolean) -> Boolean + ++ less?(a, b, fn) compares \spad{a} and b in the partial ordering induced + ++ by setOrder, and returns \spad{fn(a, b)} if \spad{a} + ++ and b are not comparable + ++ in that ordering. + largest : (List S, (S, S) -> Boolean) -> S + ++ largest(l, fn) returns the largest element of l where the partial + ++ ordering induced by setOrder is completed into a total one by fn. + userOrdered?: () -> Boolean + ++ userOrdered?() tests if the partial ordering induced by + ++ \spadfunFrom{setOrder}{UserDefinedPartialOrdering} is not empty. + if S has OrderedSet then + largest: List S -> S + ++ largest l returns the largest element of l where the partial + ++ ordering induced by setOrder is completed into a total one by + ++ the ordering on S. + more? : (S, S) -> Boolean + ++ more?(a, b) compares \spad{a} and b in the partial ordering induced + ++ by setOrder, and uses the ordering on S if \spad{a} and b are not + ++ comparable in the partial ordering. + + == add + llow :Reference List S := ref nil() + lhigh:Reference List S := ref nil() + + userOrdered?() == not(empty? deref llow) or not(empty? deref lhigh) + getOrder() == [deref llow, deref lhigh] + setOrder l == setOrder(nil(), l) + + setOrder(l, h) == + setref(llow, removeDuplicates l) + setref(lhigh, removeDuplicates h) + void + + less?(a, b, f) == + (u := less?(a, b)) case "failed" => f(a, b) + u::Boolean + + largest(x, f) == + empty? x => error "largest: empty list" + empty? rest x => first x + a := largest(rest x, f) + less?(first x, a, f) => a + first x + + less?(a, b) == + for x in deref llow repeat + x = a => return(a ^= b) + x = b => return false + aa := bb := false$Boolean + for x in deref lhigh repeat + if x = a then + bb => return false + aa := true + if x = b then + aa => return(a ^= b) + bb := true + aa => false + bb => true + "failed" + + if S has OrderedSet then + more?(a, b) == not less?(a, b, #1 <$S #2) + largest x == largest(x, #1 <$S #2) + +@ +\section{package UDVO UserDefinedVariableOrdering} +<<package UDVO UserDefinedVariableOrdering>>= +)abbrev package UDVO UserDefinedVariableOrdering +++ Author: Manuel Bronstein +++ Date Created: March 1990 +++ Date Last Updated: 9 April 1991 +++ Description: +++ This packages provides functions to allow the user to select the ordering +++ on the variables and operators for displaying polynomials, +++ fractions and expressions. The ordering affects the display +++ only and not the computations. +UserDefinedVariableOrdering(): with + setVariableOrder : List Symbol -> Void + ++ setVariableOrder([a1,...,an]) defines an ordering on the + ++ variables given by \spad{a1 > a2 > ... > an > other variables}. + setVariableOrder : (List Symbol, List Symbol) -> Void + ++ setVariableOrder([b1,...,bm], [a1,...,an]) defines an ordering + ++ on the variables given by + ++ \spad{b1 > b2 > ... > bm >} other variables \spad{> a1 > a2 > ... > an}. + getVariableOrder : () -> Record(high:List Symbol, low:List Symbol) + ++ getVariableOrder() returns \spad{[[b1,...,bm], [a1,...,an]]} such that + ++ the ordering on the variables was given by + ++ \spad{setVariableOrder([b1,...,bm], [a1,...,an])}. + resetVariableOrder: () -> Void + ++ resetVariableOrder() cancels any previous use of + ++ setVariableOrder and returns to the default system ordering. + == add + import UserDefinedPartialOrdering(Symbol) + + setVariableOrder l == setOrder reverse l + setVariableOrder(l1, l2) == setOrder(reverse l2, reverse l1) + resetVariableOrder() == setVariableOrder(nil(), nil()) + + getVariableOrder() == + r := getOrder() + [reverse(r.high), reverse(r.low)] + +@ +\section{License} +<<license>>= +--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. +--All rights reserved. +-- +--Redistribution and use in source and binary forms, with or without +--modification, are permitted provided that the following conditions are +--met: +-- +-- - Redistributions of source code must retain the above copyright +-- notice, this list of conditions and the following disclaimer. +-- +-- - Redistributions in binary form must reproduce the above copyright +-- notice, this list of conditions and the following disclaimer in +-- the documentation and/or other materials provided with the +-- distribution. +-- +-- - Neither the name of The Numerical ALgorithms Group Ltd. nor the +-- names of its contributors may be used to endorse or promote products +-- derived from this software without specific prior written permission. +-- +--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER +--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, +--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, +--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +@ +<<*>>= +<<license>> + +<<package UDPO UserDefinedPartialOrdering>> +<<package UDVO UserDefinedVariableOrdering>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |