Lists.hpp File Reference

Plans for Maxima-components regarding operations on lists. More...

Go to the source code of this file.

Detailed Description

Plans for Maxima-components regarding operations on lists.

Generating list of elements 1 to n
  • One must often generate the list of elements 1 to n:
  • "create_list" is too long for such a simple task.
  • Also, it makes the simple statement of "1..n" hard to read. The reader must apply more thought to realise what is meant.
  • For sets, we have setn and setmn. These functions provide the functionality for sets.
  • We should provide some function like setn for lists.
  • There is a Maxima-function for this task:
    1. This function is not documented and not included by default. It needs to be identified. Ask Maxima mailing-list.
    2. Then we need to check whether it is not slower than create_list.
    3. If it is slower, then we do not use it, but possibly write our own wrapper.
    4. Finally, once a replacement is in place, all occurrences of create_list have to be sifted and possibly replaced (but only if a test exists --- otherwise a test needs to be provided).
  • Better if Maxima would correct "apply" so that we don't need to worry about it --- ask on the mailing list!
  • We need docus on the use of apply, uaapply:
    1. "apply" iff the operator is like "+", or we have at most 63 arguments (guaranteed).
    2. DONE (for this better use the dedicated functions in SetSystems.mac) "uuapply" iff the operator is like "union, intersection, cartesian_product".
    3. "uaapply" otherwise.
Correct implementation of some_s and every_s
  • We can get erroneous results if for example "_x" is used in the application context.
  • Can this be avoided?
In-place modification
  • It seems that for example handling of loops would often be simplified if in-place modifications of lists would be available.
  • This needs to be provided at the Lisp-level.
    1. Stavros Macrakis on the Maxima mailing list showed
      (defun $set_rest (l new)
        (cond ((or (atom l)
                   (not (eq (caar l) 'mlist))
                   (not (cdr l)))
               (merror "Can only replace rest of non-null lists: ~:M" l))
              ((or (atom new) (not (eq (caar new) 'mlist)))
               (merror "Can only replace rest with a list: ~:M" new))
              (t (rplacd (cdr l) (cdr new))
      for replacing the rest of a list by another list.
  • On the other hand, we would introduce some performance-oriented aspects, which should be avoided.
  • Nevertheless, a sort of an "abstract data type" for lists should be considered.
    1. One needs to get an overview on the list-functionality.
    2. Providing clear guidelines for all the basic usage scenarios.
    3. Better support for index-oriented operations (instead of value-oriented) seems to be needed.
  • More problematic: What to do with sets?
    1. Here it would require a rather large effort to enable more powerful and efficient operations, since the set-structure needs to be maintained.
    2. Making list-operations more efficient than set-operations would introduce an incentive to use the former even if the latter are more appropriate.
    3. So careful planning is needed, always with emphasise on providing meaningful operations, which actually also improve readability of the programs.
    4. The removal of an element from a set should be doable, and should also increase readability.
    5. Perhaps all the basic operations are offered in "accumulator-mode", which provides in-place modification of the main operand.
Improving sort_length
  • Functionality should be merged with partition_list_eq and partition_list (where the notion of "partitioning" is not appropriate).
  • Is using the array A improving efficiency?
  • In case we have many different lengths, then likely just applying a a *stable* sorting w.r.t. length should be more efficient.
Improve partition_list_eq
  • This function is very slow.
  • Since only internal hash-maps are needed, the use of hash-arrays needs to be investigated.
  • If they are faster here, then they should be used.
  • And the use of such hash-arrays must be documents at ComputerAlgebra/plans level.
Correct split_list and split_list_epo
  • split_list has no specification at all.
  • The specification of split_list_epo is nonsensical.
    1. The current sentence can not be parsed (just an unstructured sequence of words).
    2. It also does not constitute meaning.
    3. And "epo" does not make any sense here.
  • *Splitting* of a list always means that the concatenation of the lists obtained yields the original list (as a special case of partitioning).
    1. This is the true functionality which should be provided.
    2. A new name is needed for the current functions.
    3. Also a splitting function is needed which compares two neighbouring elements.
  • The implementation is very inefficient: the Maxima mailing-list should be asked how to make a linear-time operation out of it (first creating a copy, and then splicing this copy, without further copying).

Definition in file Lists.hpp.