Item (0) of (all but first of (...))

Let's start with some trivial stuff:

untitled script pic - 2023-07-17T163303.880

untitled script pic - 2023-07-17T163403.914

... so far, so good - but: ... !

untitled script pic - 2023-07-17T163413.581 - :astonished:

Apart from the latter result being wrong, it also goes against the principle that it doesn't matter how an argument originated.

This strange behavior has not (yet) been solved in version 9.0, either.

A workaround is: untitled script pic - 2023-07-17T165148.097, but of course that should not be necessary.

O, and I didn't "ïnvent" the whole issue; actually encountered it while debugging a custom block (still under construction).

It seems that "item(0)" for linked lists is the source of the problem.
untitled script pic (13)
Probably dictionary indices went wrong this time...

Perhaps the "linked list" implementation in Snap! should be abolished (in practice it has no advantages anyway).

Actually, it is useful.
My file system blocks use this feature.

How does your file system profit from the “linked list” (vs. dynamic array) implementation of lists?

It's even worse untitled script pic - 2023-07-17T231206.261

It seems that @ threads.js doesn't check the index range.

When it reports a part of the "file system" it uses linked lists so that you can put together multiple blocks like so:

File System script pic

File System script pic (1)

thanks for this bug report! Amazing that it's gone unnoticed for so long. I've just fixed it for the impending release of v9.

Yep, it’s been solved (in v. 9.0.0-rc18):

Thx to @dardoro for the analysis, and @jens for the super-fast resolution!

Perhaps because linked lists are only created when using Speed test array vs. linked list script pic 2 or Speed test array vs. linked list script pic - my guess is many Snap! users don’t apply those at all - and are subsequently converted to dynamic arrays by some other operations, so they often won’t survive very long.

In Snap!, a linked list is merely one of two implementations of the list data type (dynamic array being the other one). It’s all “under the hood”: ordinary users like you and I won’t notice the difference, except for manipulation of dynamic arrays being generally somewhat faster.

Disclaimer: speculative

From what I’ve understood @bh, who is a trained mathematics educator, has been a proponent of linked lists - being a very elegant concept, quite memory-efficient, and supposed to pre-eminently support data insertion at the head of a list, such as applied in many recursive functions.

In practical use operations on dynamic arrays are nearly always as fast as on linked lists, or in several cases (e.g. COMBINE), much faster. Only when very large lists are involved (like 10,000 items or so) creating a linked list item-by-item through recursion may be a little faster than creating a dynamic array in similar fashion.

The linked list implementation is only reported by IN FRONT OF and ALL BUT FIRST OF. Some other operations subsequently manipulating the same list will report a list implemented as dynamic array.

I know what a linked list is.

I think all reporters in the list category should report a new list.

I wonder if you (@joecooldoo ) and I are speaking the same language (and I don’t mean Snap! :wink:).

That makes two of us.

I guess they already do.

What I was trying to convey:

  • Snap! lists are implemented as either linked lists or dynamic arrays;
  • This is mostly inconsequential for users and their applications (including your file system), except for speed differences;
  • IMO the dynamic array implementation will suffice for practical purposes; Snap!’s developers better discard the linked lists.

It is a useful feature, though, for some purposes. I think the best possible solution would be relegating the linked lists to a library rather than completely discarding them.

Yes. Except for the memory-efficient part; a linked list takes ≈ twice the storage of an array (dynamic or otherwise) because of the pointers.

It's only when writing a recursive reporter that linked lists are more efficient than arrays. In practice nobody writes recursive reporters that traverse lists, and rightly so, because arrays+iteration is way faster. Recursion is important in practice only when traversing a tree or other branched structure.

But understanding recursion is important in education (which is really the business we're in) because you don't really understand procedure calling or scope of variables until you thoroughly understand recursion. And because it's beautiful, one control structure to rule them all.

IN FRONT OF always returns a linked list. LIST always returns an array. The others mostly return the same kind of list you give them as input.

The above paragraph, though, is complicated by the fact that a list can be mixed format, with linked pairs at the beginning of the list, but with a cdr (an ALL BUT FIRST) that points to an array. (This happens when you IN FRONT OF an array.)

At least in theory linked lists are memory efficient insofar as they may use multiple fragments of available memory ("leftovers"). On the other hand - again: theoretically - total memory requirement of a linked list is about twice the size of an array's, because of the pointers. But I'm not sure of either assumption as to how it is actually implemented in Snap! ... (to be completely honest: I had asked our mutual ai-cquantance ChatGPT for advantages of linked lists, and simply :parrot:~ed that)

I guess it varies, even though it's really hard to say because (linked list vs. dynamic array) is "under the hood" for us ordinary users. What a user can do is apply 0 TEST script pic as a test tool, since with large lists execution is significantly faster if one is implemented as a dynamic array.
As far as I have been able to measure, untitled script pic - 2023-07-19T113822.583 and untitled script pic - 2023-07-19T113920.492 report (at least partially) linked lists. I thought I understood how other reporters implement output lists, but I tested some of these assumptions just now and I'm at a complete loss. :slightly_frowning_face:

I suppose any branched structure must use at least as many pointers as there are branches. But I'm not even convinced a structure fully implemented through linked lists is more efficiently processed than the same logical structure implemented as dynamic arrays wherever possible and only necessary pointers.

The List Utilities library has a hidden block
untitled script pic
that will check for you. (Technically it just checks whether the first item is linked to the second one, so it reports True for a mixed-format list as described above.

You're trading off testing for "necessary" on each node with following pointers. The latter is a trivial fixed cost, so you're not likely to come out ahead, except maybe in situations in which the analysis can be done ahead of time.