Ask HN: What's the word for when your type 'compactly' represents your state? | Hacker News Reader

Ask HN: What's the word for when your type 'compactly' represents your state?

6 pointssidedishes4 comments

Hi HN, types-ish / FP-ish question. I've asked around and not found a good answer so I wanted to ask here.

When I represent a system's state, I am often searching for a type that neatly bijects to it. A dumb example is maybe, with a stoplight I might use a tagged union with 3 states (Red | Yellow | Green) over a struct with 3 booleans isRed, isYellow, isGreen, because the latter admits invalid states. A more realistic example is say, in a platformer when I see a boolean isJumping (in the air) and isFalling (in the air and also falling) when a union of (Grounded | Rising | Falling) might be more compact.

Likewise I might want to avoid a type having multiple values representing the same state. If I have a time series for temperature from a thermometer that's only sometimes on, I might prefer a list<optional<int>> over a list<pair<bool,int>> where the bool is the on state, since the int doesn't matter if when it's off.

I'm not saying that the compact representation is always better but there's certainly some utility or at least aesthetic quality. Is there a word for this? The words I've been using here have just been pulled out of the air.

In category theory this is called an initial algebra for a signature. It is the minimal structure that satisfies some specification and maps uniquely to every other structure that satisfies the same specification but it's not clear if that's what you're looking for: http://tunes.org/wiki/initiality_20and_20finality.html.

Compact is a fine description. If you can pin down exactly what benefit you expect a more compact representation to offer, that might suggest a word that better communicates the intent of the encoding.

One potential benefit is that the number of invalid states that can be represented is reduced or eliminated. If a compact choice of type prevents the representation of invalid states, then that chops away some useless part of the state space you would otherwise need to carefully guard against with validation logic and test cases. Especially useful for structures that can potentially be edited or transformed outside of your control in ways that do not preserve the invariants you have in mind ("a stoplight value is always exactly one of the three colours").

Another potential benefit is that the number of bits needed to encode the values may be reduced. This probably doesn't matter unless you have extreme memory limitations or are writing a game engine and trying to squeeze the most work out of memory bandwidth by avoiding wasting the cache on bytes that don't contain information.

Yet another potential benefit (if no invalid states can be represented) would mean that if the value of two representations are different, then they correspond to two distinct states in your state space.

There are probably some settings where this kind of encoding is counterproductive. E.g. when fitting a linear regression model to predict a response from the input state, if there is no ordering between your states then it might be more natural to model the response variable as a function of n binary indicator variables instead of a single enum variable taking n integer values.

What you're describing sounds a lot like Functional Domain Modeling[0]

You mention "compactness" and "invalid states". FDM places great emphasis on ensuring your data model cannot represent illegal/impossible states. I think this is the essence of what you are describing, and the "compactness" is the result.

[0] https://www.47deg.com/blog/functional-domain-modeling/

Your question is related to the concept of full abstraction in programming language semantics. This page [1] is a more trustworthy explanation of it than mine. TL;DR: if you picture a set whose elements are program fragments and you construct another set whose elements are "meanings" of program fragments (according to you), and you cleverly arrange for a bijective (one-to-one) mapping between those sets (in other words, one that associates a unique meaning with every fragment and vice-versa), then you can say your semantic model is fully abstract. I don't know if anyone uses the term in reference to types, but maybe you could start a trend.

[1] https://plato.stanford.edu/entries/games-abstraction/#ProgEq...

Reply on news.ycombinator.com