Little problem(s) July 2022

[DavidM]

Please note that I'm talking about some HP 49/50 RPL specifics here, not general computing approaches.

(07-07-2022 01:16 PM)Albert Chan Wrote:  For elements of varying size, I would guess array just stored pointer. (like Python list)

That's not the case for RPL symbolic arrays (type 29 -- the only kind that can contain varying-length elements). As an example, the only difference between { 12 3456 } and [ 12 3456 ] internally is the initial 5-nibble prologue that defines the array/list type. All other data (elements and epilogue) is encoded in exactly the same way.

List { 12 3456 }:
47A20 41620 80000 210 41620 A0000 65430 B2130

Type 29 symbolic array [ 12 3456 ]:
68620 41620 80000 210 41620 A0000 65430 B2130

(07-07-2022 01:16 PM)Albert Chan Wrote:  I think list really meant linked list.
Each cell stored pointer to element, and pointer to next cell.

Cells are not stored as continuous block in memory, thus cannot do O(1) lookup.
We have to walk the links, to get to elements, thus O(n) lookup

UserRPL does not support any kind of linked list. The address of a particular non-firmware object can never be assumed as stable, so pointers to the objects aren't maintainable at the UserRPL level. But the result is the same as you describe -- other than type 3/4 arrays, GET has to step through each preceding object to reach the targeted one.

Side note: RPL does define an "internal only" array type (DOLNKARRY) that encodes offsets for each element in its data structure. There's no way to create such an array using User RPL, though, and the only use for it I've ever seen is for encoding built-in arrays of strings used for system messages. That allows firmware code to quickly access those varying-length strings as needed.