Hacker News Reader

Yeah I imagine an array write that changes the type of an index would be insanely expensive…

In practice, changing tag type is rarely done.

In any case it wouldn't be particularly expensive; you'd have to make a new member of the destination type which is as expensive as an append. The "hole" that remains in the original vector can be filled in constant time by taking the last member of it and moving it there, then shrinking its size by 1.

I'm sure there are classes of problem where that's not unusual. Even in the stated example of an AST, there are use-cases for code-fixers (eg lint fixers) that operate on the AST.

Don’t those things usually work on concrete syntax trees? And shouldn’t the solution be to use the right data structure for the job (using language feature to make this easy) rather than pushing one system (e.g. the compiler) to be worse for the sake of another tool (the linter)?

Reply on news.ycombinator.com