List Commands Library for 50g

[DavidM]

(The most recent version of the ListExt library is available at hpcalc.org)

Pier4r recently started a thread containing a variety of challenges designed to encourage the use of lists for solving problems in calculator programs. Working on those challenges gave me some ideas for a set of new RPL commands that would augment the built-in list processing features of the 50g, and I soon found that I had enough to start building a library for more generalized use.

In an effort to avoid hijacking Pier's thread, I thought it might be best to have a separate one to discuss the implementation of some of the commands (it's a "work in progress", and not quite ready for the General Software Library). Note that while there is a small amount of overlap with the GoferList library, this one is intended to complement it as opposed to replacing it.

It is my hope that anyone interested in list processing on the 50g will be able to make use of this, and will offer suggestions for improvements and new ideas for commands that would be useful.

For more background on some of the commands, including some comparisons with GoferList and performance benchmarks, see the following posts:

First post
Performance and GoferList comparisons
A thread pertaining to the implementation of LSHF, the "shuffling" command

Edit 2017-09-10: From this point forward I'll edit this first post with the latest version to make it easier to find.

Edit 2018-09-17: 1.2.1 release.

ListExt Release Notes

Version 1.2.1
2018-08-17

- LDDUP bug fixed: sublists weren't handled properly as of the last update.
- LDDUP adjusted to better balance performance in cases where lists have mostly duplicates.
- LPICK replaced with a faster version, especially for smaller lists.


______________________________________________________________________________
COMMAND SUMMARY

List Creation (CREAT menu)
LSEQ - creates a list of <count> integers as a sequence from 1..<count>
LSEQR - creates a list of integers for the range specified
LASEQ - creates a numeric sequence by repetitive addition of a constant
LMSEQ - creates a numeric sequence by repetitive multiplication by a constant
LDSEQ - creates a numeric sequence by repetitive division by a constant
LMRPT - repeats list contents as indicated by count

List Editing (EDIT menu)
LDDUP - removes duplicates from a list
LPOP - retrieves the first element in a list while leaving the rest on the stack
LPOPR - retrieves the last element in a list while leaving the rest on the stack
LPUSH - adds object to front of list
LPSHR - adds object to end of list
LPICK - returns a list containing identified elements in specified order

LREPL - replaces list elements with a substitute object as indicated
LINSR - inserts 1 or more elements into a list as indicated
LRMOV - removes 1 or more elements from a list as indicated
LFRST - returns the first <n> elements of a list
LLAST - returns the last <n> elements of a list
LRCL - recalls objects identified by variables in a list

Element Arrangement (ARRNG menu)
LROLL - rolls the list (equivalent to 1 LROT)
LRLLD - "roll down" the list (equivalent to -1 LROT)
LROT - rotates list elements left or right as indicated by count
LSWAP - swaps the positions of two list elements
LSSR - reverses the order of a sub-sequence within a list
LSHUF - shuffles the contents of a list

KSORT - Sorts a list based on keys from a separate list
REV - Reverses the individual elements of a list, string, or number

Element Grouping (GROUP menu)
LCLLT - collates a list of sublists
LDIST - distributes list items into sublists (reciprocal of LCLLT)
LGRP - replaces repeated elements with a single instance
LRPCT - list with LGRP elements and another list of the count of each element
LRPC→ - restores a list that was grouped with LRPCT
LSDIV - subdivides a list into <count> sublists

SPLIT - splits a list, string, or number as indicated into two parts
RSPLT - splits a list, string, or number as indicated from the right into two parts
LXIL - explodes inner sublists into individual elements (non-recursive)
LXILR - recursive version of LXIL
SLST→ - LIST→ that avoids Garbage Collection issues for large lists

List Testing (TEST menu)
LCNT - counts objects in a list
LEQ - checks list items to see if any do not match
MPOS - returns a list of all positions of an object in a list, or a substring in a string
MPOSL - returns a list of all positions of an object in a list or its sublists
LNRML - substitutes ROM opcodes in a list for numeric natural numbers in the range -9..9
LSAME - Executes LNRML on two lists then SAME

Combinatorics (COMB menu)
DOCOMB - feeds indicated combinations of a list to a user-supplied program
DOPERM - feeds indicated permutations of a list to a user-supplied program

List Math (LMATH menu)
LSUM - ΣLIST that also accepts lists with 0 or 1 element
LPROD - ΠLIST that also accepts lists with 0 or 1 element
LMAX - returns the maximum value contained in a list
LMIN - returns the minimum value contained in a list

String/Number Conversion (STRNG menu)
CHR+ - adds an offset to the CHR value of each character of a string
LCASE - converts upper case characters in a string to lower case
UCASE - converts lower case characters in a string to upper case
RPTCHR - creates a string of repeated characters
I→NL - converts an integer to a list of numbers
NL→I - converts a list of numbers to an integer

S→NL - converts a string to a list of numbers
NL→S - converts a list of character numbers to a string
S→SL - converts a string to a list of characters
SL→S - converts a list of characters to a string
I→BL - converts an integer into a list of remainders after repeated division by constant
BL→I - converts a list of remainders from base conversion into an exact integer

Stack Operations (STACK menu)
NMDUP - replicates a group of stack levels as indicated
NMROT - rotates stack items as indicated
SWPXY - swaps the indicated stack levels
DRPXY - drops the stack levels indicated in the range from X to Y
REVN - reverses the order of N stack levels
REVXY - reverses the order of stack levels X through Y

About1423 - Library short description and version information
Unins1423 - Detaches and deletes the ListExt library

Not included in the menu:
MENU1423 - activates the ListExt menu

[pier4r]

Nice! More list processing to do then! (it is actually a very small topic covered on the 50g,since it has a lot of other functions, but it is big enough to keep one busy)

[DavidM]

After trying out DOCOMB and DOPERM on a few tests, I've come to the conclusion that it would be better to have them return their results in list form instead of as individual items on the stack. Exploding the list (if needed) is trivial, but imploding it after the fact is more problematic, especially if you aren't sure in advance how many items will be in the result. So it makes sense to me to return the results as a list instead.

That also makes the commands more like the built-in ones, so that's a plus. I draw the line at returning no results, though. DOCOMB and DOPERM will return an empty list instead of nothing if there are no results.

The next release will have these changes.

[Gilles59]

Woo! That looks great... I need some time to test ;D

Quote:So it makes sense to me to return the results as a list instead

;D Very good choice !

Quote:DOCOMB and DOPERM will return an empty list instead of nothing if there are no results.

;D I agree !
In my opinion, the "nothing return" instead of {} with DOLIST and DOSUBS was a big mistake (and a strange mistake)

[pier4r]

I agree. Having no results requires workarounds and it is not consistent.

[DavidM]

(06-24-2017 10:11 AM)pier4r Wrote:  Nice! More list processing to do then! (...but [it] is big enough to keep one busy)

I've started looking at some of your other requests...

#1 - "listHeadIterate" -- your description was:

Quote:...it is all for iterations instead of using DOLIST
{ 1 2 3 4 5 } { 1 2 3 4 5 }
2 @num list
2 @pick elements from head and rotate lists
listHeadIterate

output
{3 4 5 1 2}
{3 4 5 1 2}
1
1
2
2

The more I looked at that, the more I realized that the basic pieces for doing this are already in place, and in fact it can be done fairly easily (and quickly) with a few simple commands. So rather than making a separate command for this, I'd suggest using the following instead:

Code:

listHeadIterate
\<<
  @ local variables on stack upon entry
  \->
  numList   @ expected number of lists to process
  numElem   @ number of elements to retrieve
  \<<
    @ collect all source lists together and then collate them
    numList \->LIST LCLLT

    @ determine the number of elements to split off, then split the list
    numElem numList * LSPLT

    @ explode the resulting (split) list
    LIST\-> DROP

    @ recombine all elements with the retrieved elements at the end,
    @ then redistribute
    OVER + numList LDST

    @ explode the retrieved elements
    LIST\-> 1 + ROLL LIST\-> DROP
  \>>
\>>

The comments make that look longer than it really is. I believe it does what you are looking for, and its performance should be about as good as a dedicated function would be.

#2 - A new "POS"-like function to return a list of all matching objects. I like this idea, and I believe I've got a working version of what you have in mind. As I am not very imaginative with names, I'm suggesting it simply be called "LPOS" to denote that the results are in list form. It will be in the next release.

#3 - "listContains" (list of elements in L2 present in L1). If I am not mistaken, that is exactly what the GoferList "Intersect" command does, and it handles duplicates in the same way that you mentioned in your request. I'm not keen to reinvent GoferList commands unless there is something wrong with them or substantial performance improvements are possible. I don't see either of those in this case.

#4 - "given a list made of sublists, return the sublist positions that contain a given element"

Still thinking about this one. It doesn't seem like it would be difficult to do, but this feels like a problem that can be generalized a bit further. For example, if I think of this as some sort of "membership" function, I could see returning a list of truth elements (0 or 1) that denote if the given argument is a member of the corresponding list element, which could be either a sublist or another object. Something like this:

{ { 1 2 3 } { 3 4 5 } 1 2 3 }
3
LMEMB (or some better command name )

output:
{ 1 1 0 0 1 }

You would then have to do further processing to get the list of positions, but with the new LPOS command that could be done quite easily:

1 LPOS

output:
{ 1 2 5 }

What do you think?

[pier4r]

Thanks for the answers (and for the grammar police, I appreciate).

#3: yes intersect should work as I expect, I need to test it (surely the challenge #34 will help a lot)

#4. Yes why not. For me it is always: "start small then generalize", if you can generalize from the start, even better. How you described the command works for lists of lists, so it is consistent.

Maybe you can make even an extended LPOS then. Example:

{ { 1 2 3 } { 3 4 5 } 1 2 3 }
3
LPOSR (recursive)

Output:
{ 1 2 5 }
{ 1 3 }
{ 2 1 }
{ 5 }

Explanation: all the elements where the value was found. If an elements is a sublist, it is recursively checked. The result is:
{ element_positions_with_value }
{ position_of_element_with_value_that_is_a_list inner_positions_with_value}

The problem is, how to visualize 3 or more nested lists? (I am not sure how many nesting levels are allowed)

But it may be not so easy to explain to the user.


Also I did not check the new release, but I hope you mention in the about page (that is pretty cool) that your library is intended as complement of the libraries L1, L2, L3... (in this case Goferlist and 50g commands, but one does not know if other useful libraries will be found in the future).

[Luigi Vampa]

David, I just wanted to say thanks for this new library, it is a very fine job.
As soon as I read the list of commands, I realized I could use it at work, in order to solve a problem I hadn't been able to tackle with HP50g's regular commands yet.
It is brilliant people like you, who make this forum a great place... and make me feel like a leech :./ ;O)

[ttw]

Another useful routine could be LPROD in analogy with LSUM. A single element list should yield its element and an empty list should return 1. There are a couple of other end-cases that are of interest: an scalar numeric value could be treated as a single-element list and an empty stack could be interpreted as an empty list.

There is an extension that comes to mind. Treat a one-dimensional array as a list. This would help in writing some linear algebra programs. Of course, a list of matrices or a matrix of lists can be left to the future.

[DavidM]

(06-25-2017 05:33 PM)pier4r Wrote:  Maybe you can make even an extended LPOS then. Example:

{ { 1 2 3 } { 3 4 5 } 1 2 3 }
3
LPOSR (recursive)

Output:
{ 1 2 5 }
{ 1 3 }
{ 2 1 }
{ 5 }

Explanation: all the elements where the value was found. If an elements is a sublist, it is recursively checked. The result is:
{ element_positions_with_value }
{ position_of_element_with_value_that_is_a_list inner_positions_with_value}

The problem is, how to visualize 3 or more nested lists? (I am not sure how many nesting levels are allowed)

But it may be not so easy to explain to the user.

I believe there is no limit to the nesting of lists, other than memory considerations. I'm not positive about that, though, as there could be an unpublished limit based on the tracking that has to take place during "skipping" of nested lists. The system has to keep a running count of levels when determining list sizes, since the result only includes the "top level" elements of a list.

I was originally thinking that the solution to the issue of checking elements of sublists might be an alternate version of LPOS, but I backed away from that idea because the result starts to lose coherency as you add layers of levels. What position does the result represent -- the sublist's index, or the sublist of the sublist (etc., etc.)? How would those results be reported? Your examples show how confusing this could become. Keeping the focus "one level deep" seemed to make more sense, which then leaves it up to the user to deal with the meaning of matches at various depths.

(06-25-2017 05:33 PM)pier4r Wrote:  Also I did not check the new release, but I hope you mention in the about page (that is pretty cool) that your library is intended as complement of the libraries L1, L2, L3... (in this case Goferlist and 50g commands, but one does not know if other useful libraries will be found in the future).

I haven't updated the "about" text in a while. I'm not really following the pattern of GoferList, but I suppose it wouldn't hurt to put in a plug for it. It really is a great set of commands.

(06-25-2017 10:21 PM)Luigi Vampa Wrote:  David, I just wanted to say thanks for this new library, it is a very fine job.
As soon as I read the list of commands, I realized I can use it at work, in order to solve a problem I hadn't been able to tackle with HP50g's regular commands yet.
It is brilliant people like you, who make this forum a great place... and make me feel like a leech :./ ;O)

Gracias por las amables palabras, aunque estoy seguro de que no las merezco.

I'm pleased you are able to make use of the library in some way! That's perhaps the best outcome of the exercise. Please feel free to make suggestions for other features that might make it even more useful.

(06-25-2017 10:46 PM)ttw Wrote:  Another useful routine could be LPROD in analogy with LSUM. A single element list should yield its element and an empty list should return 1. There are a couple of other end-cases that are of interest: an scalar numeric value could be treated as a single-element list and an empty stack could be interpreted as an empty list.

The current implementation of LSUM simply handles the "exceptions" for lists of 0 or 1 elements, then passes anything else to ΣLIST. Do you feel that a similar treatment for ΠLIST would be appropriate here? At least as a starting point. That should be easy enough to implement, and it would seem to have the same value as LSUM.

(06-25-2017 10:46 PM)ttw Wrote:  There is an extension that comes to mind. Treat a one-dimensional array as a list. This would help in writing some linear algebra programs. Of course, a list of matrices or a matrix of lists can be left to the future.

On several occasions I have thought that it would be better to use arrays instead of lists when the contents are known to be numeric, but the added flexibility of some of these commands applying to non-numeric elements is a nice bonus. But that's definitely something to keep in mind, even if only finding ways to make the conversions transparent in the process.

[pier4r]

Afaik lists are powerful because one can iterate them (do list, do subs) , with arrays is not the same or not?

[Gilles59]

(06-25-2017 10:46 PM)ttw Wrote:  There is an extension that comes to mind. Treat a one-dimensional array as a list. This would help in writing some linear algebra programs. Of course, a list of matrices or a matrix of lists can be left to the future.

You can use the AXL command for this (change an array in list or a list in array)

[DavidM]

(06-26-2017 05:13 AM)pier4r Wrote:  Afaik lists are powerful because one can iterate them (do list, do subs) , with arrays is not the same or not?

You can still use GET and PUT to access individual elements of arrays, and as Gilles mentions, converting them to a list (and back) is easy with AXL. So processing a single-dimension array isn't drastically different than a list, it just requires a bit of transformation at key points.

More care is needed when dealing with matrices, as the distinction between a multi-dimensional array and a matrix is something the user (or programmer in this case) has to keep in mind. It may make perfect sense in the context of a multi-dimensional array to expect

Code:

[
  [ 1 2 ]
  [ 3 4 ]
]
[
  [ 1 1 ]
  [ 1 1 ]
]
*

to result in

Code:

[
  [ 1 2 ]
  [ 3 4 ]
]

But of course, that's not what's going to happen if you actually execute that on a 50g. So transforming those matrices to list form could facilitate a different contextual meaning.

(06-25-2017 10:46 PM)ttw Wrote:  There is an extension that comes to mind. Treat a one-dimensional array as a list. This would help in writing some linear algebra programs. Of course, a list of matrices or a matrix of lists can be left to the future.

Which commands (either old or new) do you see as candidates for such treatment?

[DavidM]

I've been thinking about the previously-mentioned "membership" test. Considering what it means for something to be a "member" of something else is a bit more complicated than I originally thought. For example...

It seems fairly straightforward to say:
1 is a member of { 1 2 3 }
and
"a" is a member of { "a" "b" "c" }.

But is "a" a member of "bat"? Or "bat" a member of "battery"?

How about:
is 3 a member of [ 1 2 3 ]? 'x+3-5'?

If I'm to attempt this type of command, there definitely needs to be some clarity of what membership truly means. Otherwise it's probably a good indicator that I've chosen something too general to be useful.

I should probably also mention that looking at the various object types in this context has reminded me of the need to re-emphasize that, in the context of this library's commands, 1 ≠ 1. (or 1,).

Another potential "gotcha" that I've thought about is that, similar to the above, a tagged value won't be treated as equal to its untagged counterpart. This doesn't match the "==" model, and may in fact be an issue for people. As an example, { :myvalue:1 1 } LEQ => 0. Is this a problem?

[pier4r]

I think if it is specified that the operations are tested with int and or reals and the rest is wip, then it is all ok.

[DavidM]

(06-26-2017 06:26 PM)pier4r Wrote:  I think if it is specified that the operations are tested with int and or reals and the rest is wip, then it is all ok.

It's not really so much an issue of "I haven't completed it yet", but rather "which method is the proper/expected one". I already know how to strip the tags and compare the real/zint values, but doing so will impact the overall performance of all commands that need to do comparisons (and there's lots of them).

The question then becomes: Which is more important -- speed or "forgiving" comparisons?

When this question was raised before, we were only talking about the real/zint part. Now that tags have also been identified as a potential problem, I'm thinking the issue needs further assessment.

[DavidM]

(06-26-2017 04:00 PM)DavidM Wrote:  I've been thinking about the previously-mentioned "membership" test. Considering what it means for something to be a "member" of something else is a bit more complicated than I originally thought. For example...

After putting more thought into this, I've come to the conclusion that trying to establish some form of "membership" concept would be too vague to be useful. We could attempt to come up with all sorts of specific cases where an object is part of some other object, but two things would happen as a result:

- You'd have to look at the documentation every time you wanted to use the command just to see what might happen.
- The code would have so many special cases that it would be a nightmare to maintain, and would probably be very slow as well.

So that brings me full circle back to the concept of a modified form of LPOS, and that's what I'm now suggesting (and have a working copy of ). I've created a function I'm calling LPOSL (List Position/Sublists) which is essentially the same as LPOS with one difference: if the list element being compared to the target is a another list, it is considered a match if it contains the target value (regardless of where it is in that sublist). If the list element isn't a sublist, it is simply compared as normal for equality.

To illustrate, here's a sample of how the two commands give different results:

{ { 1 2 3 } 2 1 } 1 LPOS => { 3 }

{ { 3 2 1 } 2 1 } 1 LPOSL => { 1 3 }

LPOSL isn't recursive; it simply checks "one level down".

This seems to be more in line with what you originally were seeking anyway, and hopefully is still general enough to be used in a variety of different scenarios.

[pier4r]

Yes it should be already great. I mean, better than nothing. I may have not so much time to try it with the #34 until the mid of July though.

[DavidM]

(06-25-2017 10:46 PM)ttw Wrote:  Another useful routine could be LPROD in analogy with LSUM. A single element list should yield its element and an empty list should return 1. There are a couple of other end-cases that are of interest: an scalar numeric value could be treated as a single-element list and an empty stack could be interpreted as an empty list.

While working on LPROD for the next release, I encountered an issue related to ΠLIST (capital-pi LIST). ΠLIST is designed to take a list and repeatedly execute the multiply function (*) on each element in succession after "priming" the stack with the first element. Like ΣLIST with "+", it is designed around repeatedly calling the same function that is activated when you press the "x" (multiply) key. This would lead you to believe that the same function overloading should occur for ΠLIST that occurs with *, so different object types would be handled appropriately.

That's not the case for at least one specific situation, though. Namely, any multiplication where at least one of the arguments is a list will fail with ΠLIST. It's easy to replicate this bug (yes, I consider it a bug). On any of the RPL calculators that have ΠLIST, enter this from the keyboard:

{ 2 } { 3 } *

The result should be { 6 } (at least it is on my 49g+/50g/48gx). This is the normal and expected answer for multiplying two lists in that manner on those machines.

{ { 2 } { 3 } } ΠLIST, however, results in "Bad Argument Type". This is a side effect of the way the dispatch mechanism is being altered during the looping for *, and I don't believe this error was intended to have worked that way. It wouldn't surprise me if this is documented as a known issue somewhere, though I haven't seen a reference to it after searching around a bit. It's probably that it was never considered important enough to fix. Interestingly, this issue has been around at least since the Rev. R version of the 48g/x (the oldest machine I can personally verify it on).

I attempted to work around this for LPROD. { { 2 } { 3 } } LPROD will correctly return a result of { 6 }, as should other LPROD invocations that include one or more sublists. If an error occurs while determining the product of a list containing sublists, however, the original stack contents won't be returned the way they normally are for a command that errors out. Instead, you'll end up with the "offending" arguments on the stack that generated the error. This might actually be a good thing, as it will clearly show what caused the problem. But it's not consistent with the usual way errors are handled. Short of recreating the entire dispatch sequence for *, I've yet to find a good way to provide the normal error handling if a sublist is involved. So hopefully this will suffice for now.

[John Keith]

I'm not sure it's a * vs. + issue, or even a bug. Rather, I think it is a side-effect of how + is used to concatenate lists, necessitating the rather clunky ADD function for adding list elements.

Your example of multiplying, {2} {3} *, works analogously for -, /, and ADD as well.

{2} {3} + returns {2 3} due to the behavior of +.

I do not know what the correct solution is but I am following the development of the ListExt library with great interest.

John