List language item and stdlib implementation is highly flawed

[simvux]

The List language item is currently implemented as a lang-item trait.

pub trait Listable a
  @[precedence 1000]
  fn : as a, self -> self
  fn new as self = Listable(self as self, a as a):with_capacity 0
  fn with_capacity as int -> self
  fn split as self -> Maybe (a, self)

And the default implementation is defined as

pub type List a = Slice (Slice a) | Concat self self | Singleton a | Nil

However; this implementation has a lot of flaws.

1. List literals are de-sugared into inefficient cons-lists.
2. The functions provided in std:list are not tail recursive.
3. The desugared List a vs sugared [a] types have strange rules.
4. List mappers such as enumerate would not be lazy and be rather inefficient.
5. Manually performing operations such as match | [x : xs] will not be optimized, and quickly create a fragmented inefficient cons-list.

How to address these problems is currently unclear. But what I'd suggest experimentation with is instead having [a] be a dynamic Listable a trait object.

If this does not add significant performance overhead compared to our current tagged union, then it'd solve 3 and 4.

Solving 5 is important but the trickiest. It'd likely require an LIR optimization pass of it's own to automatically detect fold/map code and convert them into Listable:map to then take advantage of optimizations. The obvious optimization is to have Listable:map use a size hint to vectorize the result. It'd also be possible to do mutability optimization via some builtin:is_unique checks.

Alternatively; just defining List as a finger tree and adding more methods to Listable for it to take advantage of could help as well.