moonbitlang
[Refactor] migrate `immut/list` to destination passing style
Motivation
In short: avoid stack overflow for operations such as map.
Solution
Make the structure mutable while not exposing the mutability to the outside world by using pub constructor (instead of pub(all).
Ref: tail modulo constructor Impl: Stack Safe List
Migration
- [x] add a new
listpackage - [ ] deprecate the
immut/listpackage
This will break a lot of code. Can we support mut(priv) so that mutability is only allowed in package level? /cc @bobzhang
What's the use case of immut/list, while there's immut/array, except for tutorial? It's less efficient and has fewer utilities, and suffers from the overflow.
In Scala for example I think the majority people would use Vector instead of List.
What's the use case of
immut/list, while there'simmut/array, except for tutorial? It's less efficient and has fewer utilities, and suffers from the overflow.
immut/list has guaranteed O(1) complexity for cons and uncons instead of amortized, and it has pattern matching.
I've tested list that performs nearly identical to array on iter and cons if it's elements constructed in a batch.
So the current plan would be adding a new list package and deprecate the immut/list afterwards because:
- It's impossible to migrate gradually since the new constructor would contain labelled argument and would break everything
- We want to make it easier to access
List constructing without cons operator is painful. Will we consider add a cons operator for list like data structures?
Solution
Make the structure mutable while not exposing the mutability to the outside world by using
pubconstructor (instead ofpub(all).
User can use @list.unfold to construct list from left to right.
