aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ChangeLog6
-rw-r--r--src/algebra/prtition.spad.pamphlet129
2 files changed, 58 insertions, 77 deletions
diff --git a/src/ChangeLog b/src/ChangeLog
index 087e5c42..16c4db0a 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,9 @@
+2010-04-17 Gabriel Dos Reis <gdr@cs.tamu.edu>
+
+ * algebra/prtition.spad.pamphlet (Partition): Simplify
+ implementation. Reuse operations available from the
+ representation domain.
+
2010-04-08 Gabriel Dos Reis <gdr@cs.tamu.edu>
* algebra/boolean.spad.pamphlet (atoms$PropositionalFormula):
diff --git a/src/algebra/prtition.spad.pamphlet b/src/algebra/prtition.spad.pamphlet
index 5e70c34d..a340ef4d 100644
--- a/src/algebra/prtition.spad.pamphlet
+++ b/src/algebra/prtition.spad.pamphlet
@@ -20,22 +20,23 @@ import List
++ Domain for partitions of positive integers
++ Author: William H. Burge
++ Date Created: 29 October 1987
-++ Date Last Updated: 23 Sept 1991
+++ Date Last Updated: April 17, 2010
+++ Description:
+++ Partition is an OrderedCancellationAbelianMonoid which is used
+++ as the basis for symmetric polynomial representation of the
+++ sums of powers in SymmetricPolynomial. Thus, \spad{(5 2 2 1)} will
+++ represent \spad{s5 * s2**2 * s1}.
++ Keywords:
++ Examples:
++ References:
-Partition: Exports == Implementation where
- ++ Partition is an OrderedCancellationAbelianMonoid which is used
- ++ as the basis for symmetric polynomial representation of the
- ++ sums of powers in SymmetricPolynomial. Thus, \spad{(5 2 2 1)} will
- ++ represent \spad{s5 * s2**2 * s1}.
- L ==> List
- I ==> Integer
- OUT ==> OutputForm
- NNI ==> NonNegativeInteger
- UN ==> Union(%,"failed")
-
- Exports ==> Join(OrderedCancellationAbelianMonoid,
+Partition(): Exports == Implementation where
+ macro L == List
+ macro I == Integer
+ macro OUT == OutputForm
+ macro NNI == NonNegativeInteger
+ macro UN == Union(%,"failed")
+
+ Exports == Join(OrderedCancellationAbelianMonoid,
ConvertibleTo List Integer,CoercibleTo List Integer) with
partition: L I -> %
++ partition(li) converts a list of integers li to a partition
@@ -52,92 +53,66 @@ Partition: Exports == Implementation where
conjugate: % -> %
++ conjugate(p) returns the conjugate partition of a partition p
- Implementation ==> add
-
- import PartitionsAndPermutations
-
- Rep := List Integer
- 0 == nil()
-
- coerce (s:%): List Integer == s pretend List Integer
- convert x == copy(x pretend L I)
-
- partition list == sort(#2 < #1,list)
-
- x < y ==
- empty? x => not empty? y
- empty? y => false
- first x = first y => rest x < rest y
- first x < first y
-
- x = y ==
- EQUAL(x,y)$Lisp
--- empty? x => empty? y
--- empty? y => false
--- first x = first y => rest x = rest y
--- false
-
- x + y ==
- empty? x => y
- empty? y => x
- first x > first y => concat(first x,rest(x) + y)
- concat(first y,x + rest(y))
- n:NNI * x:% == (zero? n => 0; x + (subtractIfCan(n,1) :: NNI) * x)
-
- dp: (I,%) -> %
- dp(i,x) ==
- empty? x => 0
- first x = i => rest x
- concat(first x,dp(i,rest x))
+ Implementation == add
+ Rep == List Integer
+
+ 0 == per nil
+ coerce(s: %): List Integer == rep s
+ convert x == copy rep x
+ partition list == per sort(#2 < #1,list)
+ zero? x == empty? rep x
+ x < y == rep x < rep y
+ x = y == rep x = rep y
+ x + y == per merge(#2 < #1, rep x, rep y)$Rep
+
+ n:NNI * x:% ==
+ zero? n => 0
+ x + (subtractIfCan(n,1) :: NNI) * x
- remv: (I,%) -> UN
- remv(i,x) == (member?(i,x) => dp(i,x); "failed")
+ remv(i: I,x: %): UN ==
+ member?(i,rep x) => per remove(i, rep x)$Rep
+ "failed"
subtractIfCan(x, y) ==
- empty? x =>
- empty? y => 0
+ zero? x =>
+ zero? y => 0
"failed"
- empty? y => x
- (aa := remv(first y,x)) case "failed" => "failed"
- subtractIfCan((aa :: %), rest y)
+ zero? y => x
+ (aa := remv(first rep y,x)) case "failed" => "failed"
+ subtractIfCan((aa :: %), per rest rep y)
- li1 : L I --!! 'bite' won't compile without this
- bite: (I,L I) -> L I
- bite(i,li) ==
- empty? li => concat(0,nil())
+ bite(i: I,li: L I): L I ==
+ empty? li => [0]
first li = i =>
li1 := bite(i,rest li)
- concat(first(li1) + 1,rest li1)
- concat(0,li)
+ cons(first(li1) + 1,rest li1)
+ cons(0,li)
- li : L I --!! 'powers' won't compile without this
powers l ==
- empty? l => nil()
+ empty? l => nil
li := bite(first l,rest l)
- concat([first l,first(li) + 1],powers(rest li))
+ cons([first l,first(li) + 1],powers(rest li))
- conjugate x == conjugate(x pretend Rep)$PartitionsAndPermutations
+ conjugate x == per conjugate(rep x)$PartitionsAndPermutations
- mkterm: (I,I) -> OUT
- mkterm(i1,i2) ==
+ mkterm(i1: I,i2: I): OUT ==
i2 = 1 => (i1 :: OUT) ** (" " :: OUT)
(i1 :: OUT) ** (i2 :: OUT)
- mkexp1: L L I -> L OUT
- mkexp1 lli ==
+ mkexp1(lli: L L I): L OUT ==
empty? lli => nil()
li := first lli
empty?(rest lli) and second(li) = 1 =>
- concat(first(li) :: OUT,nil())
- concat(mkterm(first li,second li),mkexp1(rest lli))
+ [first(li) :: OUT]
+ cons(mkterm(first li,second li),mkexp1(rest lli))
coerce(x:%):OUT ==
- empty? (x pretend Rep) => coerce(x pretend Rep)$Rep
- paren(reduce("*",mkexp1(powers(x pretend Rep))))
+ empty? rep x => rep(x)::OUT
+ paren(reduce("*",mkexp1(powers rep x)))
pdct x ==
*/[factorial(second a) * (first(a) ** (second(a) pretend NNI))
- for a in powers(x pretend Rep)]
+ for a in powers rep x]
@
\section{domain SYMPOLY SymmetricPolynomial}
@@ -146,7 +121,7 @@ Partition: Exports == Implementation where
++ Description:
++ This domain implements symmetric polynomial
SymmetricPolynomial(R:Ring) == PolynomialRing(R,Partition) add
- Term:= Record(k:Partition,c:R)
+ Term == Record(k:Partition,c:R)
Rep:= List Term
-- override PR implementation because coeff. arithmetic too expensive (??)