Lists are a very flexible, powerful data type. One of Snap!’s ancestors, the famous Lisp language, was even entirely based on list processing (hence its name). In Snap!, lists can be used to represent arrays, ordinary lists of course, and any other non-atomic data type (or structure). Many of Snap!’s blocks take lists as input, and often report a list, too. For a general discussion of how lists can be used in Snap!, see chapter IV of the Snap! Reference Manual.
With power comes complexity. Except in trivial cases, list processing has its intricacies, and therefore requires a programmer’s special attention. As a self-confessed programming dilettante I make plenty if mistakes, and many if those are related to list handling. Here’s a list (!) of pits I fell into:
- Assign vs. copy
- Mutating an argument that is a list
- List vs. Input list
- Edge cases
- Numbering elements (0 .. / 1 ..)
- Order of items changed during iteration
- List (… ) vs. list (list (…) )
- Memory hogs
- Linked list, dynamic array, or a hybrid?
1 - Assign vs. copy
When you SET a variable (e.g. “var”) TO another variable (“original”) the value is copied. If you then change the value of one of the variables, the other is not affected. So far, so good:
If, however, “original” is a list, and you SET “var” TO “original”, the two variables become like one: - any change to one’s value will affect the other, as demonstrated by the following script:
The cause is that a variable to which a list is assigned does not actually hold the list’s value, but a reference to the list’s address in the computer memory. SET () TO () copies the address of the list from one variable to the other. So REPLACE ITEM (2) OF (original) WITH (thing) means: replace the 2nd item of the list whose address is kept by “original” with “thing”. And REPORT (var) means: report (the contents of) the list whose address is kept by “var”. Since both variables keep the same address, both blocks refer to the same list.
If you don’t want this (and often you don’t) you could make a full (or “deep”) copy of the original list. ID OF () creates a completely new and independent copy of the original list:
In some cases you my want to make not a deep but a ‘’shallow” copy: the top level of the original list is copied …
… while any deeper levels are shared with the original:
2 - Mutating an argument that is a list
A special case of mutating the original list is when a custom block performs operations on an argument that is a list.
When a (custom) block takes a value as an argument, the value is effectively copied for use within the block. When it is changed within the block, the original variable (outside of the block) is unaffected:
This may also work if the argument is a list:
However if within the block the list is manipulated using ADD, DELETE, INSERT, or REPLACE, the original list is affected:
(for this example, let's ignore that Snap! primitive works on lists as well)
This result (the original list is mutated through the custom block) may be intentional, but often it’s not (it’s definitely not good functional programming style). To prevent it from happening, make a copy of the argument before processing:
Even better, use a Higher Order Function working on lists:
3 - List vs. Input list
Another one of Snap!’s flexible features is “variadic input”, i.e. a block accepting any number of arguments:
The arguments of a variadic input may be replaced by an input list:
You designate an “input list” by dropping it onto the arrowheads that indicate a variable-input slot, rather than onto the first input slot. The latter makes a common error:
Even if - like me - you keep making this kind of mistake though you've heard about it, at least you'll be able to identify and repair it much quicker now.
See also: Snap! Reference Manual Ch. VII (Procedures as Data), section B (Writing Higher Order Procedures).
4 - Edge cases
Edge cases are another source of indexing errors. The following custom blocks reports all elements of a list, except for one, whose index is specified:
It works fine for most cases, e.g:
… but fails if the element to be discarded is either the first or last:
In this case, the issue is caused by NUMBERS FROM () TO (), which counts down if the second argument is greater than the first. So if “exception” = 1, “precursors” will be NUMBERS FROM (1) TO (0) = (1 0). Similar for exception = length of data.
The APL Primitives library offers a NUMBERS block that will only report ascending numbers. This is often an improvement. However it’s still not perfect in this particular case, since it will report nonsense if the EXCEPT value is outside of the range FROM () TO ().
A correct solution for this case is:
More generally put: take edge cases into consideration, and test if your code handles them correctly.
5 - Numbering elements (0 .. / 1 ..)
6 - Order of items changed during iteration
Take a look at this script, which is supposed to take all even-indexed items from a list (and as it happens all values correspond to their initial position.
What happens is that the 2nd item (value: 2) is deleted from the list, and so the 3rd item (3) moves to 2nd position. The item that was originally in 4th position (4) moves to 3rd, and is therefore, wrongly, not deleted. The 5th item (5) moves to 4th and is, again wrongly, deleted. The original item 6 (6) moves to position 4 while the index jumps to 5; therefore 6 is (wrongly) skipped.
A safer option is to create a new (empty) result list, traverse the original and add any items that you want to report to the result list, while leaving the original list intact:
Even better, Snap! has great (easy-to-use and really fast) list processing functions, such as MAP, COMBINE, and KEEP - all of them traversing the original list without changing it, and reporting a new list. KEEP is the to-go option here:
7 - List (…) vs. list (list (…) )
Sometimes you may want to initialize a list for adding elements. The standard way is to set the list to be the empty list.
However in some cases, e.g. where the list is a list of lists, you may need to initialize it such that it contains an empty list as first (and only) element of the list-of-lists.
Or look at this example:
It is OK to put a "simple" list IN FRONT OF a list of lists, but it doesn't worrk to append one - in the latter case you would have to use one more LIST block to make the appended list a list of lists, too. Also if you want to replace IN FRONT OF by APPEND you need to use an extra LIST block:
Failing to use that extra LIST block in such case is a common mistake.
8 - Memory hogs
Lists may grow really large, and if a list has been assigned to a global or local variable, all of it will be saved when you save the project, which may tale a lot of memory (slowing down the saving / opening of the project, or even exceeding Snap!’s cloud project file size limit (currently 10 MB, I think).
You can prevent this by clicking on the variable (in the Variables menu) and checking the “Transient” box; thus its contents will not be saved. Or you can use a script variable, which will automatically disappear when the script ends. Or, if you really must keep the list(-s), you can save the project file to your own (“Computer”) memory instead of Snap!’s project file cloud.
A slightly different issue is "Stack overflow". This is also associated with very large lists, especially of they are created or manipulated by a recursive procedure. In these cases, it's often possible to replace that with a HOF working on lists, such as , , , and
9 - Linked list or dynamic array?
The first Snap! list is internally represented (“under the hood”) by its value and the (computer memory) address of the next item. The second list is represented by a (contiguous) array of values. There’s supposed to be hybrids, too - butI haven’t spotted them in the wild, yet.
According to the Snap! Reference Manual (ch. iv: First Class Lists, section C: Functional and Imperative List Programming) …
“Snap! uses two different internal representations of lists, one (dynamic array) for imperative programming and the other (linked list) for functional programming. Each representation makes the corresponding built-in list blocks (commands or reporters, respectively) most efficient. It’s possible to mix styles in the same program, but if the same list is used both ways, the program will run more slowly because it converts from one representation to the other repeatedly.”
In my experience, supported by measurements, operations on linked lists are hardly ever faster than on dynamic arrays, while in some cases (much) slower. On the other hand a functional programming style, using primitives such as , - these primitives actually create linked lists -, , composition, recursion, etc. helps to code fast, and is less error-prone. Higher-order functions working on lists (like MAP, KEEP and COMBINE) are also very efficient at runtime.
You can test how a list is implemented through a hidden function block from the List utilities library - to let it be shown, select Hide blocks from the File menu, then uncheck: .
This is becoming a long story … So, why would you care about the underlying implementation of a Snap! list?
- If you really need optimum run time performance;
- If the list is so big that a “stack overflow” error is raised;
- If a function block somehow doesn’t work with one of the implementations.
You can make sure a Snap! list is implemented as dynamic array by using a copy, made with . Conversely, you can make a copy that is a linked list, using: (another hidden block from the List utilities library.) If you also want to convert sublists (on deeper levels), try: