Efficiently prepending to a list

[krader1961]

The recently introduced conj command provides an efficient means of appending to a list. There should also be a way to efficiently prepend items to a list. Exactly what such a command should be named is TBD. Also, whether it should be prepend items... $list or prepend $list items... is debatable but I'm inclined towards the latter. In fact, I'm also inclined to suggest renaming conj to append for symmetry and easier discoverability.

[wirelyre]

I'm confused why there's a conj function at all. Wouldn't it make more sense to give [$@list $items...] the O(m) guarantee? The notation's already there and it's shorter to type and there aren't any extra names to keep track of.

[krader1961]

@wirelyre The reason the [$@list $items...] formulation is potentially slow is the expansion of $list into its individual elements. Which then need to be appended to what starts as an empty list. Since Elvish lists (and maps) are immutable that means a new list is created as each element is appended. This is where lists are constructed. Compare that to the conj command implementation. Making the former as efficient as the latter would require modifying the compiler to recognize the first case and rewrite it into the second case. Which is theoretically possible but complicated to implement. And the complexity is increased when you add the prepend use case which would also need to be special-cased by the compiler.

So, yes, it does make more sense to have the general list construction syntax guarantee O(m) behavior. It's just a small matter of writing some complex code. Patches are welcome. But until someone writes that code builtins like conj (append) and prepend are simple to implement and useful. 😸

[xiaq]

It will make sense for Elvish to choose the conj implementation automatically when recognizing a specific list splicing pattern. I added conj both as a stopgap solution before the optimization is implemented, and because I feel it makes sense to expose this low level primitive directly even if it shouldn't be frequently used in future.

[da-tubi]

Why not adding a built-in function called: cons for prepending? see #1723

[krader1961]

Why not adding a built-in function called: cons for prepending?

Because cons as the name won't make any sense to 99.9% of Elvish users since they have never used Lisp and it will therefore be hard to discover and remember. And, as @xiaq points out, it is preferable to have the compiler recognize the pattern and automatically emit a more efficient solution that avoids the overhead of the current naive behavior. The prepend pattern is arguably not used often enough to justify a prepend (or cons) builtin which is why I haven't bothered to implement it.

P.S., Personally, I wish that conj was named append for the same reasons (and I've written a modest amount of Lisp code when I used Emacs as my editor).