search

nikita-volkov / acc

Sequence optimized for monoidal construction and folding
http://hackage.haskell.org/package/acc
MIT License
7 stars 3 forks source link

More instances; or how to use the Acc properly #1

Open Anton-Latukha opened 3 years ago

Anton-Latukha commented 3 years ago

Encountered right away that the {Eq, Ord, Typeable, Data, Hashable} instances are needed.

P.S.

https://github.com/haskell-nix/hnix/issues/880 Planning to use the Acc for HNix at the nearest time, should fit perfectly for what we do (parsing the language, growing the expressions, contexts, derivations etc.

nikita-volkov commented 3 years ago

Acc lacks those instances essentially for the same reasons as bytestring builder does. It is an intermediate data-structure which helps you accumulate a sequence of elements and finalise into some other representation by means of folding. That's it. That is its only purpose. It is not optimised for other things including equality comparison and hashing.

Yes, you can hack your way to having such instances, e.g., the way they've done with Seq, but it's likely to induce incorrect use based on false assumptions.

IOW, if you need these instances it may be a sign that you're trying to use acc for a purpose that it is not intended for. Can you describe your use case?

Anton-Latukha commented 3 years ago

Ok.

Yes.

Had second thought are they may be needed to be wrapped in a builder. But the core of HNix is sort-of the builder of expressions by itself, and so far I never created a builder pattern, only used it, so IDK how to do it properly here.

Basically started working with Acc by replacing the lists in:

https://github.com/haskell-nix/hnix/blob/7ac94bb24d625dfec6760892359c9e863369614a/src/Nix/Expr/Types.hs#L415-L419.

There are a simpler starting points, for example, NString in the same module:

https://github.com/haskell-nix/hnix/blob/7ac94bb24d625dfec6760892359c9e863369614a/src/Nix/Expr/Types.hs#L181-L203.

Anton-Latukha commented 3 years ago

Currently the project in the design reorganization stage: https://github.com/haskell-nix/hnix/blob/master/ChangeLog.md So can squeeze any changes in this release, and after that I going to help a couple of projects that depend on us (mainly just dhall-nix & update-nix-fetchgit) to follow.

HNix language builtins set almost works, and that "almost" state means "just barely still not working", so since HNix base is still technically not working machine, this state allows give it a year of "after creation clean-up & reorganization" of the design & structure which allows minimizing future tech debt (which also means migrate from Lists and Strings) and alike.

So any design improvements can be considered.

nikita-volkov commented 3 years ago

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 commented 3 years ago

Ok.

Understood.

I would think a bit here next:

  1. So Acc is for the parser, and project nicely packs the parser module: Parser.hs, for more simplicity - its Haddock header.

    NExprF is what is called a base functor for NExpr. It is recursion schemes, brief explanation.

    So thinking. Ok. Acc fits into Parser, again, for example where the lists are used there, to grow stuff and then freeze it into the other type.

  2. Parser mainly works on NExprF & NExprLocF (main and annotated expression primitives, Nix (pure lazy language) expressions are of course monoidal (& commutative)), so thinking maybe Acc fits for the NExprF and NExprLocF which are there to be used by parser and when done are converted into NExpr and NExprLoc.

    It seems that some of the NExprF & NExprLocF type classes I tried to upstream here - were put there "just because" in the first place.

    So maybe put the freeze data type before this transition.

    Sorry for trying to figuring-out it here and maybe asking your mind on it. Largely without guardrails from others, frequently by myself in the project, so at least trying to have the idea of where it fits, before doing core changes.

Ok, thank you. Got some basic idea.