Why won't SparseArray let me store values with the head List?

Question

When you attempt to define a SparseArray with elements that have the head List it complains:

SparseArray[{1 -> {1, 2, 3}, 2 -> {"a", "b"}}]

SparseArray::valnl: The value specified by the rule 1->{1,2,3} should not be a List. >>

SparseArray[{1 -> {1, 2, 3}, 2 -> {"a", "b"}}]

Nevertheless (other) arbitrary expressions are accepted:

SparseArray[{1 -> foo[1, 2, 3], 2 -> bar["a", "b"]}]

There does not appear to be any actual limitation of SparseArray that prevents it from storing List elements.

In fact with a bit of fiddling we can get SparseArray to hold List elements! First wrap the Lists an additional head so that SparseArray accepts them, then use Part to extract the first part of every element, essentially stripping the arbitrary extra heads (foo):

sa1 = SparseArray[{1 -> foo@{1, 2, 3}, 2 -> foo@{"a", "b"}}];

sa2 = sa1[[All, 1]];

We now have a SparseArray with List elements:

sa2 // Head
sa2[[1]] // Head
Head /@ Normal[sa2]
sa2["NonzeroValues"]

SparseArray

List

{List, List}

{{1, 2, 3}, {"a", "b"}}

However if we try to use the InputForm of the expression (as input) it does not work:

ToString[sa2, InputForm] // ToExpression

SparseArray[Automatic, {2}, 0, {1, {{0, 2}, {{1}, {2}}}, {{1, 2, 3}, {"a", "b"}}}]

Sadly this false equivalence breaks the use of Save and pattern-based manipulation of the object.

Why would SparseArray be blocking the use of List when apparently any other head is accepted, and when there is internal support for List itself?

Answer 1

The basic reason is that once you convert a tensor expression into a SparseArray, you've "given control" of all levels of that expression to SparseArray to manage on your behalf in an efficient way (the number of levels is the rank of the tensor, to mix jargon).

SparseArray will then try to maintain the illusion that those levels are still really there. But that illusion will fall apart if you're allowed to mess around with the rank of the SparseArray after it has been constructed. Putting lists inside an existing SparseArray is really telling you that you got the dimension of the SparseArray wrong (too small) to begin with.

So it's not a technical limitation, it's a conceptual one. If you start messing with the rank of the SparseArray, you're going to run into trouble at some point, e.g. Dimensions will give the wrong answer. So we do the best we can to enforce the rank stays the same by insisting you don't store lists (e.g., you're only storing 'scalars').