path: root/src/algebra/list.spad.pamphlet

\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{src/algebra list.spad}
\author{Michael Monagon, Manuel Bronstein}
\maketitle

\begin{abstract}
\end{abstract}
\tableofcontents
\eject

\section{domain ILIST IndexedList}

<<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, NULL, QCAR, QCDR, RPLACA, RPLACD
--   Those that are included for efficiency only
--   LIST, CAR, CDR, NCONC2, NREVERSE, LENGTH
--   Also REVERSE, since it's called in Polynomial Ring

 Qnull   ==> NULL$Lisp
 Qpush   ==> PUSH$Lisp
 
 Exports ==> ListAggregate S 
 Implementation ==>
  add
   import %nil: %                from Foreign Builtin
   import %makepair: (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
   
   #x                  == LENGTH(x)$Lisp
   concat(s:S,x:%)     == %makepair(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"
      %head RPLACA(x,s)$Lisp
   setelt(x,"first",s) ==
      empty? x => error "Cannot update an empty list"
      %head RPLACA(x,s)$Lisp
   setrest!(x,y)      ==
      empty? x => error "Cannot update an empty list"
      %tail RPLACD(x,y)$Lisp
   setelt(x,"rest",y)  ==
      empty? x => error "Cannot update an empty list"
      %tail RPLACD(x,y)$Lisp
   construct l         == l pretend %
   parts s             == s pretend List S
   reverse! x         == NREVERSE(x)$Lisp
   reverse x           == REVERSE(x)$Lisp
   minIndex x          == mn

   rest(x, n) ==
      for i in 1..n repeat
         if Qnull x then error "index out of range"
         x := %tail x
      x

   copy x ==
      y := empty()
      for i in 0.. while not Qnull x repeat
         if i = cycleMax and cyclic? x then error "cyclic list"
         y := %makepair(%head x,y)
         x := %tail x
      (NREVERSE(y)$Lisp)@%

   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 Qnull x and not Qnull y repeat
          %head x ~=$S %head y => return false
          x := %tail x
          y := %tail y
       Qnull x and Qnull y

     latex(x : %): String ==
       s : String := "\left["
       while not Qnull x repeat
         s := concat(s, latex(%head x)$S)$String
         x := %tail x
         if not Qnull x then s := concat(s, ", ")$String
       concat(s, " \right]")$String

     member?(s,x) ==
        while not Qnull 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:%) ==
      Qnull x => 
        Qnull y => x
        Qpush(first y,x)
        QRPLACD(x,rest y)$Lisp
        x
      z:=x
      while not Qnull %tail z repeat
        z:=%tail z
      QRPLACD(z,y)$Lisp
      x

   -- Then a quicky:
   if S has SetCategory then
     removeDuplicates! l ==
       p := l
       while not Qnull 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 Qnull (pr:=%tail pp) repeat
           if (%head pr)@S = f then QRPLACD(pp,%tail pr)$Lisp
           else pp:=pr
       l

   -- then sorting
   mergeSort: ((S, S) -> Boolean, %, Integer) -> %

   sort!(f, l)       == mergeSort(f, l, #l)

   merge!(f, p, q) ==
     Qnull p => q
     Qnull 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 Qnull p and not Qnull q repeat
       if f(%head p, %head q)
         then (QRPLACD(t, p)$Lisp; t := p; p := %tail p)
         else (QRPLACD(t, q)$Lisp; t := q; q := %tail q)
     QRPLACD(t, if Qnull p then q else p)$Lisp
     r

   split!(p, n) ==
      n < 1 => error "index out of range"
      p := rest(p, (n - 1)::NonNegativeInteger)
      q := %tail p
      QRPLACD(p,%nil)$Lisp
      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}
<<domain LIST List>>=
import Type
import ListAggregate
)abbrev domain LIST List
++ Author: Michael Monagan
++ Date Created: Sep 1987
++ Change History:
++ Basic Operations:
++   \#, append, concat, concat!, cons, construct, copy, elt, elt,
++   empty, empty?, eq?, first, member?, merge!, mergeSort, minIndex,
++   nil, null, parts, removeDuplicates!, rest, rest, reverse,
++   reverse!, setDifference, setIntersection, setUnion, setelt,
++   setfirst!, setrest!, sort!, split!
++ Related Constructors: ListFunctions2, ListFunctions3, ListToMap
++ Also See: IndexList, ListAggregate
++ AMS Classification:
++ Keywords: list, index, aggregate, lisp
++ 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}.
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.
  if S has OpenMath then OpenMath

 Implementation ==>
   IndexedList(S, LISTMININDEX) add
      import %nil: %                 from Foreign Builtin
      import %peq: (%,%) -> Boolean  from Foreign Builtin
      import %makepair: (S,%) -> S   from Foreign Builtin

      nil                      == %nil
      null l                   == %peq(l,%nil)
      cons(s, l)               == %makepair(s,l)
      append(l:%, t:%)         == APPEND(l, t)$Lisp

      if S has OpenMath then
        writeOMList(dev: OpenMathDevice, x: %): Void ==
          OMputApp(dev)
          OMputSymbol(dev, "list1", "list")
          -- The following didn't compile because the compiler isn't
          -- convinced that `xval' is a S.  Duhhh! MCD.
          --for xval in x repeat
          --  OMwrite(dev, xval, false)
          while not null x repeat
            OMwrite(dev,first x,false)
            x := rest x
          OMputEndApp(dev)

        OMwrite(x: %): String ==
          s: String := ""
          sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
          dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML())
          OMputObject(dev)
          writeOMList(dev, x)
          OMputEndObject(dev)
          OMclose(dev)
          s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
          s

        OMwrite(x: %, wholeObj: Boolean): String ==
          s: String := ""
          sp := OM_-STRINGTOSTRINGPTR(s)$Lisp
          dev: OpenMathDevice := OMopenString(sp pretend String, OMencodingXML())
          if wholeObj then
            OMputObject(dev)
          writeOMList(dev, x)
          if wholeObj then
            OMputEndObject(dev)
          OMclose(dev)
          s := OM_-STRINGPTRTOSTRING(sp)$Lisp pretend String
          s

        OMwrite(dev: OpenMathDevice, x: %): Void ==
          OMputObject(dev)
          writeOMList(dev, x)
          OMputEndObject(dev)

        OMwrite(dev: OpenMathDevice, x: %, wholeObj: Boolean): Void ==
          if wholeObj then
            OMputObject(dev)
          writeOMList(dev, x)
          if wholeObj then
            OMputEndObject(dev)

      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))

@

\section{package LIST2 ListFunctions2}

<<package LIST2 ListFunctions2>>=
import Type
import FiniteLinearAggregateFunctions2
)abbrev package LIST2 ListFunctions2
++ Author:
++ Date Created:
++ Change History:
++ Basic Operations: map, reduce, scan
++ Related Constructors: List
++ Also See: ListFunctions3
++ AMS Classification:
++ Keywords: list, aggregate, map, reduce
++ Description:
++   \spadtype{ListFunctions2} implements utility functions that
++   operate on two kinds of lists, each with a possibly different
++   type of element.
ListFunctions2(A:Type, B:Type): public == private where
  LA     ==> List A
  LB     ==> List B
  O2     ==> FiniteLinearAggregateFunctions2(A, LA, B, LB)

  public ==> with
    scan:    ((A, B) -> B, LA, B) -> LB
      ++ scan(fn,u,ident) successively uses the binary function
      ++ \spad{fn} to reduce more and more of list \spad{u}.
      ++ \spad{ident} is returned if the \spad{u} is empty.
      ++ The result is a list of the reductions at each step. See
      ++ \spadfun{reduce} for more information. Examples:
      ++ \spad{scan(fn,[1,2],0) = [fn(2,fn(1,0)),fn(1,0)]} and
      ++ \spad{scan(*,[2,3],1) = [2 * 1, 3 * (2 * 1)]}.
    reduce:  ((A, B) -> B, LA, B) -> B
      ++ reduce(fn,u,ident) successively uses the binary function
      ++ \spad{fn} on the elements of list \spad{u} and the result
      ++ of previous applications. \spad{ident} is returned if the
      ++ \spad{u} is empty. Note the order of application in
      ++ the following examples:
      ++ \spad{reduce(fn,[1,2,3],0) = fn(3,fn(2,fn(1,0)))} and
      ++ \spad{reduce(*,[2,3],1) = 3 * (2 * 1)}.
    map:      (A -> B, LA) -> LB
      ++ map(fn,u) applies \spad{fn} to each element of
      ++ list \spad{u} and returns a new list with the results.
      ++ For example \spad{map(square,[1,2,3]) = [1,4,9]}.

  private ==> add
    map(f, l)       == map(f, l)$O2
    scan(f, l, b)   == scan(f, l, b)$O2
    reduce(f, l, b) == reduce(f, l, b)$O2

@

\section{package LIST3 ListFunctions3}

<<package LIST3 ListFunctions3>>=
import Type
import Type
)abbrev package LIST3 ListFunctions3
++ Author:
++ Date Created:
++ Change History:
++ Basic Operations: map
++ Related Constructors: List
++ Also See: ListFunctions2
++ AMS Classification:
++ Keywords: list, aggregate, map
++ Description:
++   \spadtype{ListFunctions3} implements utility functions that
++   operate on three kinds of lists, each with a possibly different
++   type of element.
ListFunctions3(A:Type, B:Type, C:Type): public == private where
  LA     ==> List A
  LB     ==> List B
  LC     ==> List C

  public ==> with
    map: ( (A,B)->C, LA, LB) -> LC
      ++ map(fn,list1, u2) applies the binary function \spad{fn}
      ++ to corresponding elements of lists \spad{u1} and \spad{u2}
      ++ and returns a list of the results (in the same order). Thus
      ++ \spad{map(/,[1,2,3],[4,5,6]) = [1/4,2/4,1/2]}. The computation
      ++ terminates when the end of either list is reached. That is,
      ++ the length of the result list is equal to the minimum of the
      ++ lengths of \spad{u1} and \spad{u2}.

  private ==> add
    map(fn : (A,B) -> C, la : LA, lb : LB): LC ==
      empty?(la) or empty?(lb) => empty()$LC
      concat(fn(first la, first lb), map(fn, rest la, rest lb))

@

\section{package LIST2MAP ListToMap}

<<package LIST2MAP ListToMap>>=
import Type
import SetCategory
import List
)abbrev package LIST2MAP ListToMap
++ Author: Manuel Bronstein
++ Date Created: 22 Mar 1988
++ Change History:
++   11 Oct 1989   MB   ?
++ Basic Operations: match
++ Related Constructors: List
++ Also See:
++ AMS Classification:
++ Keywords: mapping, list
++ Description:
++   \spadtype{ListToMap} allows mappings to be described by a pair of
++   lists of equal lengths.  The image of an element \spad{x},
++   which appears in position \spad{n} in the first list, is then
++   the \spad{n}th element of the second list.  A default value or
++   default function can be specified to be used when \spad{x}
++   does not appear in the first list.  In the absence of defaults,
++   an error will occur in that case.
ListToMap(A:SetCategory, B:Type): Exports == Implementation where
  LA  ==> List A
  LB  ==> List B
  AB  ==> (A -> B)

  Exports ==> with
    match: (LA, LB   ) -> AB
      ++ match(la, lb) creates a map with no default source or target values
      ++ defined by lists la and lb of equal length.
      ++ The target of a source value \spad{x} in la is the
      ++ value y with the same index lb.
      ++ Error: if la and lb are not of equal length.
      ++ Note: when this map is applied, an error occurs when
      ++ applied to a value missing from la.
    match: (LA, LB, A) -> B
      ++ match(la, lb, a) creates a map
      ++ defined by lists la and lb of equal length, where \spad{a} is used
      ++ as the default source value if the given one is not in \spad{la}.
      ++ The target of a source value \spad{x} in la is the
      ++ value y with the same index lb.
      ++ Error: if la and lb are not of equal length.
    match: (LA, LB, B)    -> AB
      ++ match(la, lb, b) creates a map
      ++ defined by lists la and lb of equal length, where \spad{b} is used
      ++ as the default target value if the given function argument is
      ++ not in \spad{la}.
      ++ The target of a source value \spad{x} in la is the
      ++ value y with the same index lb.
      ++ Error: if la and lb are not of equal length.
    match: (LA, LB, A, B) -> B
      ++ match(la, lb, a, b) creates a map
      ++ defined by lists la and lb of equal length.
      ++ and applies this map to a.
      ++ The target of a source value \spad{x} in la is the
      ++ value y with the same index lb.
      ++ Argument b is the default target value if a is not in la.
      ++ Error: if la and lb are not of equal length.
    match: (LA, LB, AB)    -> AB
      ++ match(la, lb, f) creates a map
      ++ defined by lists la and lb of equal length.
      ++ The target of a source value \spad{x} in la is the
      ++ value y with the same index lb.
      ++ Argument \spad{f} is used as the
      ++ function to call when the given function argument is not in
      ++ \spad{la}.
      ++ The value returned is f applied to that argument.
    match: (LA, LB, A, AB) -> B
      ++ match(la, lb, a, f) creates a map
      ++ defined by lists la and lb of equal length.
      ++ and applies this map to a.
      ++ The target of a source value \spad{x} in la is the
      ++ value y with the same index lb.
      ++ Argument \spad{f} is a default function to call if a is not in la.
      ++ The value returned is then obtained by applying f to argument a.

  Implementation ==> add
    match(la, lb)             == match(la, lb, #1)
    match(la:LA, lb:LB, a:A)  == lb.position(a, la)
    match(la:LA, lb:LB, b:B)  == match(la, lb, #1, b)
    match(la:LA, lb:LB, f:AB) == match(la, lb, #1, f)

    match(la:LA, lb:LB, a:A, b:B) ==
      (p := position(a, la)) < minIndex(la) => b
      lb.p

    match(la:LA, lb:LB, a:A, f:AB) ==
      (p := position(a, la)) < minIndex(la) => f a
      lb.p

@

\section{domain ALIST AssociationList}

<<domain ALIST AssociationList>>=
import SetCategory
import List
import Reference
)abbrev domain ALIST AssociationList
++ Author:
++ Date Created:
++ Change History:
++ Basic Operations: empty, empty?, keys, \#, concat, first, rest,
++   setrest!, search, setelt, remove!
++ Related Constructors:
++ Also See: List
++ AMS Classification:
++ Keywords: list, association list
++ Description:
++   \spadtype{AssociationList} implements association lists. These
++   may be viewed as lists of pairs where the first part is a key
++   and the second is the stored value. For example, the key might
++   be a string with a persons employee identification number and
++   the value might be a record with personnel data.

AssociationList(Key:SetCategory, Entry:SetCategory):
 AssociationListAggregate(Key, Entry) == add
        Pair ==> Record(key:Key, entry:Entry)
        Rep := Reference List Pair

        dictionary()            == ref empty()
        empty()                 == dictionary()
        empty? t                == empty? deref t
        entries(t:%):List(Pair) == deref t
        parts(t:%):List(Pair)   == deref t
        keys t                  == [k.key for k in deref t]
        # t                     == # deref t
        first(t:%):Pair         == first deref t
        rest t                  == ref rest deref t
        concat(p:Pair, t:%)     == ref concat(p, deref t)
        setrest!(a:%, b:%)     == ref setrest!(deref a, deref b)
        setfirst!(a:%, p:Pair) == setfirst!(deref a,p)
        minIndex(a:%):Integer   == minIndex(deref a)
        maxIndex(a:%):Integer   == maxIndex(deref a)

        search(k, t) ==
          for r in deref t repeat
            k = r.key => return(r.entry)
          "failed"

        latex(a : %) : String ==
          l : List Pair := entries a
          s : String := "\left["
          while not empty?(l) repeat
            r : Pair := first l
            l        := rest l
            s := concat(s, concat(latex r.key, concat(" = ", latex r.entry)$String)$String)$String
            if not empty?(l) then s := concat(s, ", ")$String
          concat(s, " \right]")$String

--      assoc(k, l) ==
--        (r := find(#1.key=k, l)) case "failed" => "failed"
--        r

        assoc(k, t) ==
          for r in deref t repeat
            k = r.key => return r
          "failed"

        setelt(t:%, k:Key, e:Entry) ==
          (r := assoc(k, t)) case Pair => (r::Pair).entry := e
          setref(t, concat([k, e], deref t))
          e

        remove!(k:Key, t:%) ==
          empty?(l := deref t) => "failed"
          k = first(l).key =>
            setref(t, rest l)
            first(l).entry
          prev := l
          curr := rest l
          while not empty? curr and first(curr).key ~= k repeat
            prev := curr
            curr := rest curr
          empty? curr => "failed"
          setrest!(prev, rest curr)
          first(curr).entry

@

\section{License}

<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
-- Copyright (C) 2007-2010, Gabriel Dos Reis.
-- 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>>

<<domain ILIST IndexedList>>
<<domain LIST List>>
<<package LIST2 ListFunctions2>>
<<package LIST3 ListFunctions3>>
<<package LIST2MAP ListToMap>>
<<domain ALIST AssociationList>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}