![]() |
List Commands Library for 50g - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: List Commands Library for 50g (/thread-8555.html) |
List Commands Library for 50g - DavidM - 06-24-2017 12:54 AM (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 RE: List Commands Library for 50g - pier4r - 06-24-2017 10:11 AM 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) RE: List Commands Library for 50g - DavidM - 06-24-2017 01:51 PM 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. ![]() The next release will have these changes. RE: List Commands Library for 50g - Gilles59 - 06-24-2017 09:08 PM 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) RE: List Commands Library for 50g - pier4r - 06-24-2017 09:31 PM I agree. Having no results requires workarounds and it is not consistent. RE: List Commands Library for 50g - DavidM - 06-25-2017 04:52 PM (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 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 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? RE: List Commands Library for 50g - pier4r - 06-25-2017 05:33 PM 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). RE: List Commands Library for 50g - Luigi Vampa - 06-25-2017 10:21 PM 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) RE: List Commands Library for 50g - ttw - 06-25-2017 10:46 PM 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. RE: List Commands Library for 50g - DavidM - 06-26-2017 02:36 AM (06-25-2017 05:33 PM)pier4r Wrote: Maybe you can make even an extended LPOS then. Example: 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. ![]() (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. 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. RE: List Commands Library for 50g - pier4r - 06-26-2017 05:13 AM Afaik lists are powerful because one can iterate them (do list, do subs) , with arrays is not the same or not? RE: List Commands Library for 50g - Gilles59 - 06-26-2017 11:37 AM (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) RE: List Commands Library for 50g - DavidM - 06-26-2017 03:37 PM (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: [ Code: [ 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? RE: List Commands Library for 50g - DavidM - 06-26-2017 04:00 PM 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? RE: List Commands Library for 50g - pier4r - 06-26-2017 06:26 PM 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. RE: List Commands Library for 50g - DavidM - 06-27-2017 02:13 PM (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. RE: List Commands Library for 50g - DavidM - 06-27-2017 02:52 PM (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 ![]() 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. RE: List Commands Library for 50g - pier4r - 06-28-2017 05:15 AM 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. RE: List Commands Library for 50g - DavidM - 06-29-2017 01:16 AM (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. RE: List Commands Library for 50g - John Keith - 06-29-2017 01:42 AM 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 |