API breaking refactoringgood first issue
Repository metrics
- Stars
- (835 stars)
- PR merge metrics
- (No merged PRs in 30d)
Description
One of the core stones HNix stumbles on is pretty pervasive String (as exceptions that gather provenance info, and in REPL) and, especially, List being used across the whole project.
The List is famously a one-directionally linked chain structure.
That means that per every cell used there is a cell that holds a pointer. And there is no way to append to list without traverse of the whole list.
Appending x meaning traverse every time, which is doing x^2 actions, so indeed - exponential append.
The most frequent thing the structure builder does is appending.
So, lets look at what actions happen with the Monoid, and most probably replace the List with an efficient Monoid, for example: https://hackage.haskell.org/package/acc