Post Reply 
List Commands Library for 50g
06-24-2017, 12:54 AM (This post was last modified: 10-31-2017 01:26 PM by DavidM.)
Post: #1
List Commands Library for 50g
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 2017-10-31: The final version has now been posted in the General Software Library.
Find all posts by this user
Quote this message in a reply
06-24-2017, 10:11 AM (This post was last modified: 06-25-2017 05:20 PM by pier4r.)
Post: #2
RE: List Commands Library for 50g
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)

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
06-24-2017, 01:51 PM
Post: #3
RE: List Commands Library for 50g
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. Smile DOCOMB and DOPERM will return an empty list instead of nothing if there are no results.

The next release will have these changes.
Find all posts by this user
Quote this message in a reply
06-24-2017, 09:08 PM (This post was last modified: 06-24-2017 09:21 PM by Gilles59.)
Post: #4
RE: List Commands Library for 50g
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)
Find all posts by this user
Quote this message in a reply
06-24-2017, 09:31 PM
Post: #5
RE: List Commands Library for 50g
I agree. Having no results requires workarounds and it is not consistent.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
06-25-2017, 04:52 PM
Post: #6
RE: List Commands Library for 50g
(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 Smile)

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?
Find all posts by this user
Quote this message in a reply
06-25-2017, 05:33 PM (This post was last modified: 06-25-2017 05:36 PM by pier4r.)
Post: #7
RE: List Commands Library for 50g
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).

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
06-25-2017, 10:21 PM (This post was last modified: 06-26-2017 01:44 PM by Luigi Vampa.)
Post: #8
RE: List Commands Library for 50g
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)

Saludos Saluti Cordialement Cumprimentos MfG BR + + + + +
Luigi Vampa +
Free42 BlackviewA7 '<3' I + + +
Find all posts by this user
Quote this message in a reply
06-25-2017, 10:46 PM
Post: #9
RE: List Commands Library for 50g
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.
Find all posts by this user
Quote this message in a reply
06-26-2017, 02:36 AM
Post: #10
RE: List Commands Library for 50g
(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. Smile 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.
Find all posts by this user
Quote this message in a reply
06-26-2017, 05:13 AM
Post: #11
RE: List Commands Library for 50g
Afaik lists are powerful because one can iterate them (do list, do subs) , with arrays is not the same or not?

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
06-26-2017, 11:37 AM
Post: #12
RE: List Commands Library for 50g
(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)
Find all posts by this user
Quote this message in a reply
06-26-2017, 03:37 PM
Post: #13
RE: List Commands Library for 50g
(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?
Find all posts by this user
Quote this message in a reply
06-26-2017, 04:00 PM
Post: #14
RE: List Commands Library for 50g
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. Smile

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?
Find all posts by this user
Quote this message in a reply
06-26-2017, 06:26 PM
Post: #15
RE: List Commands Library for 50g
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.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
06-27-2017, 02:13 PM
Post: #16
RE: List Commands Library for 50g
(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.
Find all posts by this user
Quote this message in a reply
06-27-2017, 02:52 PM (This post was last modified: 06-27-2017 02:56 PM by DavidM.)
Post: #17
RE: List Commands Library for 50g
(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 Smile). 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.
Find all posts by this user
Quote this message in a reply
06-28-2017, 05:15 AM (This post was last modified: 06-28-2017 05:20 AM by pier4r.)
Post: #18
RE: List Commands Library for 50g
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.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
06-29-2017, 01:16 AM
Post: #19
RE: List Commands Library for 50g
(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.
Find all posts by this user
Quote this message in a reply
06-29-2017, 01:42 AM
Post: #20
RE: List Commands Library for 50g
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
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 2 Guest(s)