Please, make the statement "Monoid is not []" true

[Anton-Latukha]

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

[Anton-Latukha]

nikita-volkov/acc#1 (comment)

nikita-volkov:

There is a common pattern to construct data structures in two phases: first build, then freeze. With that in mind it helps to separate data structures into modification-optimized and frozen.

The first category is your builders, maps, sets, lists and what not, all optimized for various kinds of modification operations. Frozen types are optimized for querying operations and compact representation in memory, their examples are monolithic types like vectors, text, bytestring and ADTs around them.

Your NExprF and NString seem to fall into the frozen category. That's why I recommend using Vector instead of list or Acc in it.

Since Vector is not optimized for any sort of modification, you'll need a data structure optimized for building it. Acc paired with Int (for the vector size) would do for such purpose, however I've already released a package dedicated to building vectors and it is optimized even better for the task: "vector-builder".

I sense the way you construct is by parsing. It is a typical case for the build/freeze approach. More so, you'll find utilities like many and some in the "vector-builder" package that are particularly useful in parsing.

[Anton-Latukha]

The codebase got refactored. It maximally uses polymorphic one for singletons & conversion to NonEmpty started. HLint guards for people not to put [s] singletons in code - so part of the work is done & protected.

It is now should be easier to convert [] to chosen types.

[Anton-Latukha]

Use OverloadedLists:
https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/overloaded_lists.html

[Anton-Latukha]

Added a DList & Acc benchmarks into: https://github.com/haskell-perf/sequences

Encouraging.

[Anton-Latukha]

Talked with Nikita (the Acc author), and become sure & understood that Acc is really to be used.

Also because of the published benchmarks he updated Acc & it is even faster now, & fromList does additional optimization of the structure, so [] became more costly, but that is amortization to have effective Acc monoid construction phase.