From c868015d912449eb551ff379031b4fe4b3fab255 Mon Sep 17 00:00:00 2001 From: dos-reis Date: Sat, 10 Sep 2011 22:15:52 +0000 Subject: Remove IndexedList. * algebra/list.spad.pamphlet (IndexedList): Fold definition into List. Remove. * algebra/exposed.lsp.pamphlet: Don't expose ILIST. * algebra/Makefile.in: Adjust. --- src/algebra/list.spad.pamphlet | 505 +++++++++++++++++++---------------------- 1 file changed, 228 insertions(+), 277 deletions(-) (limited to 'src/algebra/list.spad.pamphlet') diff --git a/src/algebra/list.spad.pamphlet b/src/algebra/list.spad.pamphlet index 1d5a8522..6e60ef80 100644 --- a/src/algebra/list.spad.pamphlet +++ b/src/algebra/list.spad.pamphlet @@ -2,7 +2,7 @@ \usepackage{open-axiom} \begin{document} \title{src/algebra list.spad} -\author{Michael Monagon, Manuel Bronstein} +\author{Michael Monagon, Manuel Bronstein, Gabriel Dos Reis} \maketitle \begin{abstract} @@ -10,211 +10,6 @@ \tableofcontents \eject -\section{domain ILIST IndexedList} - -<>= -import Type -import ListAggregate -)abbrev domain ILIST IndexedList -++ Author: Michael Monagan -++ Date Created: Sep 1987 -++ Change History: -++ Basic Operations: -++ \#, concat, concat!, construct, copy, elt, elt, empty, -++ empty?, eq?, first, member?, merge!, mergeSort, minIndex, -++ parts, removeDuplicates!, rest, rest, reverse, reverse!, -++ setelt, setfirst!, setrest!, sort!, split! -++ Related Constructors: List -++ Also See: -++ AMS Classification: -++ Keywords: list, aggregate, index -++ Description: -++ \spadtype{IndexedList} is a basic implementation of the functions -++ in \spadtype{ListAggregate}, often using functions in the underlying -++ LISP system. The second parameter to the constructor (\spad{mn}) -++ is the beginning index of the list. That is, if \spad{l} is a -++ list, then \spad{elt(l,mn)} is the first value. This constructor -++ is probably best viewed as the implementation of singly-linked -++ lists that are addressable by index rather than as a mere wrapper -++ for LISP lists. -IndexedList(S:Type, mn:Integer): Exports == Implementation where - cycleMax ==> 1000 -- value used in checking for cycles - --- The following seems to be a bit out of date, but is kept in case --- a knowledgeable person wants to update it: --- The following LISP dependencies are divided into two groups --- Those that are required --- CONS, EQ, NIL, --- Those that are included for efficiency only --- LIST, NCONC2, LENGTH --- Also REVERSE, since it's called in Polynomial Ring - - Qpush ==> PUSH$Lisp - - Exports ==> ListAggregate S - Implementation ==> - add - import %nil: % from Foreign Builtin - import %pair: (S,%) -> % from Foreign Builtin - import %peq: (%,%) -> Boolean from Foreign Builtin - import %lempty?: % -> Boolean from Foreign Builtin - import %head: % -> S from Foreign Builtin - import %tail: % -> % from Foreign Builtin - import %lreverse: % -> % from Foreign Builtin - import %lreverse!: % -> % from Foreign Builtin - import %llength: % -> NonNegativeInteger from Foreign Builtin - - #x == %llength x - concat(s:S,x:%) == %pair(s,x) - eq?(x,y) == %peq(x,y) - first x == SPADfirst(x)$Lisp - elt(x,"first") == SPADfirst(x)$Lisp - empty() == %nil - empty? x == %lempty? x - rest x == %tail x - elt(x,"rest") == %tail x - setfirst!(x,s) == - empty? x => error "Cannot update an empty list" - %store(%head x,s)$Foreign(Builtin) - s - setelt(x,"first",s) == - empty? x => error "Cannot update an empty list" - %store(%head x,s)$Foreign(Builtin) - s - setrest!(x,y) == - empty? x => error "Cannot update an empty list" - %store(%tail x,y)$Foreign(Builtin) - %tail x - setelt(x,"rest",y) == - empty? x => error "Cannot update an empty list" - %store(%tail x,y)$Foreign(Builtin) - %tail x - construct l == l pretend % - parts s == s pretend List S - reverse! x == %lreverse! x - reverse x == %lreverse x - minIndex x == mn - - rest(x, n) == - for i in 1..n repeat - if empty? x then error "index out of range" - x := %tail x - x - - copy x == - y := empty() - for i in 0.. while not empty? x repeat - if i = cycleMax and cyclic? x then error "cyclic list" - y := %pair(%head x,y) - x := %tail x - %lreverse! y - - if S has CoercibleTo(OutputForm) then - coerce(x):OutputForm == - -- displays cycle with overbar over the cycle - y := empty()$List(OutputForm) - s := cycleEntry x - while not %peq(x, s) repeat - y := concat((first x)::OutputForm, y) - x := rest x - y := reverse! y - empty? s => bracket y - -- cyclic case: z is cylic part - z := list((first x)::OutputForm) - while not %peq(s, rest x) repeat - x := rest x - z := concat((first x)::OutputForm, z) - bracket concat!(y, overbar commaSeparate reverse! z) - - if S has SetCategory then - x = y == - %peq(x,y) => true - while not empty? x and not empty? y repeat - %head x ~=$S %head y => return false - x := %tail x - y := %tail y - empty? x and empty? y - - latex(x : %): String == - s : String := "\left[" - while not empty? x repeat - s := concat(s, latex(%head x)$S)$String - x := %tail x - if not empty? x then s := concat(s, ", ")$String - concat(s, " \right]")$String - - member?(s,x) == - while not empty? x repeat - if s = %head x then return true else x := %tail x - false - - -- Lots of code from parts of AGGCAT, repeated here to - -- get faster compilation - concat!(x:%,y:%) == - empty? x => - empty? y => x - Qpush(first y,x) - %store(%tail x,rest y)$Foreign(Builtin) - x - z:=x - while not empty? %tail z repeat - z:=%tail z - %store(%tail z,y)$Foreign(Builtin) - x - - -- Then a quicky: - if S has SetCategory then - removeDuplicates! l == - p := l - while not empty? p repeat --- p := setrest!(p, remove!(#1 = %head p, %tail p)) --- far too expensive - builds closures etc. - pp:=p - f:S:=%head p - p:=%tail p - while not empty? (pr:=%tail pp) repeat - if (%head pr)@S = f then - %store(%tail pp,%tail pr)$Foreign(Builtin) - else pp:=pr - l - - -- then sorting - mergeSort: ((S, S) -> Boolean, %, Integer) -> % - - sort!(f, l) == mergeSort(f, l, #l) - - merge!(f, p, q) == - empty? p => q - empty? q => p - %peq(p, q) => error "cannot merge a list into itself" - if f(%head p, %head q) - then (r := t := p; p := %tail p) - else (r := t := q; q := %tail q) - while not empty? p and not empty? q repeat - if f(%head p, %head q) - then (%store(%tail t, p)$Foreign(Builtin); t := p; p := %tail p) - else (%store(%tail t, q)$Foreign(Builtin); t := q; q := %tail q) - %store(%tail t, if empty? p then q else p)$Foreign(Builtin) - r - - split!(p, n) == - n < 1 => error "index out of range" - p := rest(p, (n - 1)::NonNegativeInteger) - q := %tail p - %store(%tail p,%nil)$Foreign(Builtin) - q - - mergeSort(f, p, n) == - if n = 2 and f(first rest p, first p) then p := reverse! p - n < 3 => p - l := (n quo 2)::NonNegativeInteger - q := split!(p, l) - p := mergeSort(f, p, l) - q := mergeSort(f, q, n - l) - merge!(f, p, q) - -@ - \section{domain LIST List} <>= import Type @@ -222,7 +17,7 @@ import ListAggregate )abbrev domain LIST List ++ Author: Michael Monagan ++ Date Created: Sep 1987 -++ Change History: +++ Date Last Changed: September 9, 2011. ++ Basic Operations: ++ \#, append, concat, concat!, cons, construct, copy, elt, elt, ++ empty, empty?, eq?, first, member?, merge!, mergeSort, minIndex, @@ -236,76 +31,233 @@ import ListAggregate ++ Description: ++ \spadtype{List} implements singly-linked lists that are ++ addressable by indices; the index of the first element -++ is 1. In addition to the operations provided by -++ \spadtype{IndexedList}, this constructor provides some -++ LISP-like functions such as \spadfun{null} and \spadfun{cons}. +++ is 1. this constructor provides some LISP-like functions +++ such as \spadfun{null} and \spadfun{cons}. List(S:Type): Exports == Implementation where - LISTMININDEX ==> 1 -- this is the minimum list index - - Exports ==> ListAggregate S with - nil : % - ++ \spad{nil} is the empty list. - null : % -> Boolean - ++ null(u) tests if list \spad{u} is the - ++ empty list. - cons : (S, %) -> % - ++ cons(element,u) appends \spad{element} onto the front - ++ of list \spad{u} and returns the new list. This new list - ++ and the old one will share some structure. - append : (%, %) -> % - ++ append(u1,u2) appends the elements of list \spad{u1} - ++ onto the front of list \spad{u2}. This new list - ++ and \spad{u2} will share some structure. - if S has SetCategory then - setUnion : (%, %) -> % - ++ setUnion(u1,u2) appends the two lists u1 and u2, then - ++ removes all duplicates. The order of elements in the - ++ resulting list is unspecified. - setIntersection : (%, %) -> % - ++ setIntersection(u1,u2) returns a list of the elements - ++ that lists \spad{u1} and \spad{u2} have in common. - ++ The order of elements in the resulting list is unspecified. - setDifference : (%, %) -> % - ++ setDifference(u1,u2) returns a list of the elements - ++ of \spad{u1} that are not also in \spad{u2}. - ++ The order of elements in the resulting list is unspecified. - - Implementation ==> - IndexedList(S, LISTMININDEX) add - import %nil: % from Foreign Builtin - import %peq: (%,%) -> Boolean from Foreign Builtin - import %pair: (S,%) -> % from Foreign Builtin - import %lconcat: (%,%) -> % from Foreign Builtin - - nil == %nil - null l == %peq(l,%nil) - cons(s, l) == %pair(s,l) - append(l:%, t:%) == %lconcat(l,t) - - if S has SetCategory then - setUnion(l1:%,l2:%) == removeDuplicates concat(l1,l2) - - setIntersection(l1:%,l2:%) == - u :% := empty() - l1 := removeDuplicates l1 - while not empty? l1 repeat - if member?(first l1,l2) then u := cons(first l1,u) - l1 := rest l1 - u - - setDifference(l1:%,l2:%) == - l1 := removeDuplicates l1 - lu:% := empty() - while not empty? l1 repeat - l11:=l1.1 - if not member?(l11,l2) then lu := concat(l11,lu) - l1 := rest l1 - lu - - if S has ConvertibleTo InputForm then - convert(x:%):InputForm == - convert concat(convert('construct)@InputForm, - [convert a for a in (x pretend List S)]$List(InputForm)) + Exports == ListAggregate S with + nil : % + ++ \spad{nil} is the empty list. + null : % -> Boolean + ++ null(u) tests if list \spad{u} is the + ++ empty list. + cons : (S, %) -> % + ++ cons(element,u) appends \spad{element} onto the front + ++ of list \spad{u} and returns the new list. This new list + ++ and the old one will share some structure. + append : (%, %) -> % + ++ append(u1,u2) appends the elements of list \spad{u1} + ++ onto the front of list \spad{u2}. This new list + ++ and \spad{u2} will share some structure. + if S has SetCategory then + setUnion : (%, %) -> % + ++ setUnion(u1,u2) appends the two lists u1 and u2, then + ++ removes all duplicates. The order of elements in the + ++ resulting list is unspecified. + setIntersection : (%, %) -> % + ++ setIntersection(u1,u2) returns a list of the elements + ++ that lists \spad{u1} and \spad{u2} have in common. + ++ The order of elements in the resulting list is unspecified. + setDifference : (%, %) -> % + ++ setDifference(u1,u2) returns a list of the elements + ++ of \spad{u1} that are not also in \spad{u2}. + ++ The order of elements in the resulting list is unspecified. + + Implementation == add + import %nil: % from Foreign Builtin + import %peq: (%,%) -> Boolean from Foreign Builtin + import %pair: (S,%) -> % from Foreign Builtin + import %lconcat: (%,%) -> % from Foreign Builtin + import %lempty?: % -> Boolean from Foreign Builtin + import %head: % -> S from Foreign Builtin + import %tail: % -> % from Foreign Builtin + import %lreverse: % -> % from Foreign Builtin + import %lreverse!: % -> % from Foreign Builtin + import %llength: % -> NonNegativeInteger from Foreign Builtin + import %icst0: NonNegativeInteger from Foreign Builtin + import %icst1: NonNegativeInteger from Foreign Builtin + import %idec: Integer -> Integer from Foreign Builtin + + Qpush ==> PUSH$Lisp + cycleMax ==> 1000 -- value used in checking for cycles + + nil == %nil + null l == %peq(l,%nil) + cons(s, l) == %pair(s,l) + append(l:%, t:%) == %lconcat(l,t) + + #x == %llength x + concat(s:S,x:%) == %pair(s,x) + eq?(x,y) == %peq(x,y) + first x == SPADfirst(x)$Lisp + elt(x,"first") == SPADfirst(x)$Lisp + empty() == %nil + empty? x == %lempty? x + rest x == %tail x + elt(x,"rest") == %tail x + setfirst!(x,s) == + empty? x => error "Cannot update an empty list" + %store(%head x,s)$Foreign(Builtin) + s + setelt(x,"first",s) == + empty? x => error "Cannot update an empty list" + %store(%head x,s)$Foreign(Builtin) + s + setrest!(x,y) == + empty? x => error "Cannot update an empty list" + %store(%tail x,y)$Foreign(Builtin) + %tail x + setelt(x,"rest",y) == + empty? x => error "Cannot update an empty list" + %store(%tail x,y)$Foreign(Builtin) + %tail x + construct l == l pretend % + parts s == s pretend List S + reverse! x == %lreverse! x + reverse x == %lreverse x + minIndex x == 1 + + rest(x, n) == + for i in %icst1..n repeat + if empty? x then error "index out of range" + x := %tail x + x + + copy x == + y := empty() + for i in %icst0.. while not empty? x repeat + if i = cycleMax and cyclic? x then error "cyclic list" + y := %pair(%head x,y) + x := %tail x + %lreverse! y + + if S has CoercibleTo(OutputForm) then + coerce(x):OutputForm == + -- displays cycle with overbar over the cycle + y := empty()$List(OutputForm) + s := cycleEntry x + while not %peq(x, s) repeat + y := concat((first x)::OutputForm, y) + x := rest x + y := reverse! y + empty? s => bracket y + -- cyclic case: z is cylic part + z := list((first x)::OutputForm) + while not %peq(s, rest x) repeat + x := rest x + z := concat((first x)::OutputForm, z) + bracket concat!(y, overbar commaSeparate reverse! z) + + if S has SetCategory then + x = y == + %peq(x,y) => true + while not empty? x and not empty? y repeat + %head x ~=$S %head y => return false + x := %tail x + y := %tail y + empty? x and empty? y + + latex(x : %): String == + s : String := "\left[" + while not empty? x repeat + s := concat(s, latex(%head x)$S)$String + x := %tail x + if not empty? x then s := concat(s, ", ")$String + concat(s, " \right]")$String + + member?(s,x) == + while not empty? x repeat + if s = %head x then return true else x := %tail x + false + + -- Lots of code from parts of AGGCAT, repeated here to + -- get faster compilation + concat!(x:%,y:%) == + empty? x => + empty? y => x + Qpush(first y,x) + %store(%tail x,rest y)$Foreign(Builtin) + x + z:=x + while not empty? %tail z repeat + z:=%tail z + %store(%tail z,y)$Foreign(Builtin) + x + + -- Then a quicky: + if S has SetCategory then + removeDuplicates! l == + p := l + while not empty? p repeat + -- p := setrest!(p, remove!(#1 = %head p, %tail p)) + -- far too expensive - builds closures etc. + pp:=p + f:S:=%head p + p:=%tail p + while not empty? (pr:=%tail pp) repeat + if (%head pr)@S = f then + %store(%tail pp,%tail pr)$Foreign(Builtin) + else pp:=pr + l + + -- then sorting + mergeSort: ((S, S) -> Boolean, %, Integer) -> % + + sort!(f, l) == mergeSort(f, l, #l) + + merge!(f, p, q) == + empty? p => q + empty? q => p + %peq(p, q) => error "cannot merge a list into itself" + if f(%head p, %head q) + then (r := t := p; p := %tail p) + else (r := t := q; q := %tail q) + while not empty? p and not empty? q repeat + if f(%head p, %head q) + then (%store(%tail t, p)$Foreign(Builtin); t := p; p := %tail p) + else (%store(%tail t, q)$Foreign(Builtin); t := q; q := %tail q) + %store(%tail t, if empty? p then q else p)$Foreign(Builtin) + r + + split!(p, n) == + n < %icst1 => error "index out of range" + p := rest(p, %idec(n)::NonNegativeInteger) + q := %tail p + %store(%tail p,%nil)$Foreign(Builtin) + q + + mergeSort(f, p, n) == + if n = 2 and f(first rest p, first p) then p := reverse! p + n < 3 => p + l := (n quo 2)::NonNegativeInteger + q := split!(p, l) + p := mergeSort(f, p, l) + q := mergeSort(f, q, n - l) + merge!(f, p, q) + + if S has SetCategory then + setUnion(l1:%,l2:%) == removeDuplicates concat(l1,l2) + + setIntersection(l1:%,l2:%) == + u :% := empty() + l1 := removeDuplicates l1 + while not empty? l1 repeat + if member?(first l1,l2) then u := cons(first l1,u) + l1 := rest l1 + u + + setDifference(l1:%,l2:%) == + l1 := removeDuplicates l1 + lu:% := empty() + while not empty? l1 repeat + l11:=l1.1 + if not member?(l11,l2) then lu := concat(l11,lu) + l1 := rest l1 + lu + + if S has ConvertibleTo InputForm then + convert(x:%):InputForm == + convert concat(convert('construct)@InputForm, + [convert a for a in (x pretend List S)]$List(InputForm)) @ @@ -623,7 +575,6 @@ AssociationList(Key:SetCategory, Entry:SetCategory): <<*>>= <> -<> <> <> <> -- cgit v1.2.3