Hacker News Reader

> The other thing that we do all the time in everyday life is a quotient, and as far as I know no programming language has a good way to represent that: something as basic as a fraction

Er, fractions are a directly-supported (core or stdlib) type in many languages. Including:

Scheme family languages (numbers work this way by default, unless you introduce irrational numbers), Ruby (doesn't default to rational math by default generally for numbers, but has syntax for rational literals and rationals use rational math), Raku, Python, Clojure, Go, Haskell, and, well, lots of languages have core/stdlib support even if they don't have a literal syntax or Scheme-style default-to-exact-rational behavior.

I pretty sure the poster meant the general 'fraction' (quotient) construction (set 'a' is like set 'b' but with certain elements to be regarded as the same - 'a rational number is a pair of numbers, where you regard (ax,ay) to be the same as (x,y)'. ), rather than rational numbers exactly. (Similarly, Actionscript 3 had generic lists, but not generic types generally IIRC).

Isn't this usually trivial to inplement, but pointless because you'll never want to abstract over it?

It's basically a type characterized by a base type and a canonicalization function that maps all values in that type to a subset of the same type, with those values that have the same canonicalized value being equal.

In order to deal with quotients it is not necessary to normalize to a single representative for each equivalence class (though sometimes that can be useful).

The more important part is a facility for detecting whether two objects are equivalent, and a guarantee that all other operations respect the structure.

> In order to deal with quotients it is not necessary to normalize to a single representative for each equivalence class

I may have been thinking about too close of an analogy with mathematical quotients where there are other operations and you are going to want to apply those to the canonical form generally, but, sure, I can see that.

My point was in languages where you can construct user-defined generics types, a general implementation is usually straightforward but not particularly useful, because it's an abstraction you'd almost never consume except in defining concrete types. General operations on quotient-like types aren't something that there is much call for. And I think that's just as true with or without canonicalization.

I would suspect that that is why, unlike say iterables (or in languages with more powerful type systems, monads) it's not something you see supported out of the box in type systems.

I'm not sure what distinction you're making? https://docs.python.org/3/library/fractions.html

The same but for non-numbers.

Ah, sure. What use might that have?

Quotients are a bit of an unsolved problem even in Agda. Cubical Agda makes the definition easier but makes it much harder to work with the resulting datatype, while if you don't use higher inductive types you end up in setoid hell where the language can't do any of the obvious things you should be able to do automatically.

(author)

I appreciate Haskell's power in this domain, and apparently sum types are life-changing (they get mentioned in so many language conversations).

That said, I'm mostly concerned with types like columns, rows, tables, colors, urls, documents, or images. These are implementable in lots of languages, but many languages just have a lot of ad-hoc implementations of them, of the same concept but with slightly different tilts on it. I'm saying that it would be interesting if a language focused on that part of the ecosystem, so that things could connect together.

Haskell might have a very nice type system, but it does not seem like it has many universally-accepted standard types for everything to use. For example, as soon as it gets up to the complexity of a "text" type, there are lots of slightly-different flavors of text.

Hey, you're the author! I just wanted to thank you for writing this. I saw it yesterday, actually, and it set me off on an adventure: you mentioned seaborn, so I went and learned that (it's beautiful), which mentioned xarray (http://xarray.pydata.org/en/stable/) which is the generalized solution to the problem you mention!

I'm a bit skeptical, but, xarray's demos are very impressive. They do all kinds of geospatial modeling on ocean salinity, ozone, etc, and the data model seems general enough to create beautiful plots automatically (for various reasons, but mostly because of what you were saying in your post: simplicity enforced by constraints).

I'd love your thoughts on xarray, since it was such a serendipitous discovery in relation to your post. (If you're not impressed with xarray, then that's probably a useful signal that perhaps it's a step in the wrong direction on the ladder of complexity.) But either way, thanks for reminding me that "the solution is elegance, not a battalion of special cases."

(Not the OP) I’ve been using xarray for the better part of a year now on some serious scientific projects. It certainly has some pain points and places to grow (it’s still a 0.x release after all), but when it works it’s truly excellent to use. So many things “just work”

Thanks for the review! I'll give it a serious try then.

Does your code happen to be available anywhere? I'd love to learn by example from someone who's used it for so long on real work. (Feel free to DM me on twitter: https://twitter.com/theshawwn if you'd like to share it privately.)

Have a great night!

Sadly it’s internal.

I’ve found the xarray docs to be fairly comprehensive, and GitHub issues/stackoverflow fill the gaps.

"of the same concept but with slightly different tilts on it"

The answer is, they aren't the same concept. In English, we may look at multiple implementations and say "hey, those are all an 'image'", but in reality, each of these is a distinct concept:

A representation of the image meant for manipulation by pixel, such as for a 2d image editor.

A representation of the internal structure of the image format, such as giving access to the PNG or JPG frames.

The raw bytes of the specific serialization, such as for shipping around a network.

Representations of the image in a display context, such as the display driver might use.

Representation of the image from the point of view of metadata, such as a file explorer may need.

Representation of an image from the point of view of editing, where it may be disassembled into frames or layers for later reconstruction after applying edits, such as Photoshop may use.

You can't create an "image" class/package/library that will fit all those needs, to say nothing of the ways those needs may interact with other things (i.e. I may need metadata for that file explorer that includes non-images as well, even there are image-specific elements to it like a thumbnail).

Moreover, the lack of connectivity between this sort of object isn't even my top 25 programming problems... I'm almost always several layers composed on top of these sorts of things anyhow with my own local data concerns. Even if I've got an "image" I've also got a ton of other things with it that nothing else can be expected to understand (like which user this is a avatar for or where the image came from or any number of other things).

It's sometimes annoying to deal with too many color types or something, but that's a local concern for an ecosystem, not a universal problem a general-purpose language should be spending valuable design budget trying to dictate. (DSLs can, if appropriate, precisely because they are domain-specific languages.)

I think this is the same kind of misguided as "every app has its own ad-hoc implementation of login, it's the same concept with just a slightly different tilt on it, so the language should offer a login function". The essence of programming is properly representing similarities between similar things but also properly representing the sometimes quite subtle differences. So most mature languages, rather than offering us a bunch of premade functions, try to offer us some low-level building blocks and make it easy to compose them together to suit our purposes (and I think this is why giant class libraries have gone out of fashion - even though classes are sort of extensible, customising someone else's class turns out to be a lot harder than using someone else's function). And I think that's the part that's really missing in data-land (and I'd say even Haskell is barely any way along this road) - not a bunch of predefined datatypes but really easy ways of composing basic datatypes and building them up into more complex datatypes that meet our needs. Having lots of similar but subtly distinct datatypes isn't actually a problem if your language is good at dealing with it, just as having lots of similar but subtly distinct functions isn't actually a problem.

I'd just like to point out some examples of things that are implemented incompatibly commonly, not because they are different:

Colors:

    (r{0.0-255.0}, g{0.0-255.0}, b{0.0-255.0}, a{0.0-255.0})

vs

    { red = r{0.0-1.0}, green = g{0.0-1.0}, blue={0.0-1.0}, opacity = o{0.0-1.0} }

That is tuple vs record, different scaling factor, opacity vs transparency, but these representations are equivalent.

Or geopoint:

    (lat, lng)

vs

    (lng, lat)

I could go on...

https://macwright.com/lonlat/

If transfer size isn't an (important) consideration, then the one true answer is: just use a record, which doesn't enforce an ordering and is explicit about which coordinate is which.

The color ones are not (unambiguously) equivalent, you're ignoring bit depth and assuming 8-bit color values in one of them.

I am not, both are floats. They are represented only in that range, because that's customary in web dev circles.

Floats? What does R=255.0, etc. mean when the other example has R=1.0?

Precision has nothing to do with it, the scale isn't even defined... which was my point.

I think you have a point, but the situation you describe is largely because things are in flux - that is certainly the case for web pages.

When consensus is reached, things settle down - so most new languages give you associative arrays out of the box. On the other hand, there was a time when exceptions seemed to be the consensus on runtime error handling, but there has been some rethinking on that...

Then there is APL, which seems to exemplify what you are asking for. It is very well-regarded by those who get it, but it seems to have been just too difficult (or alien) for most of the engineers whose purpose it addresses.

Haskell may not be the best example to make a case from, as it is still, to a large extent, an experimental language. Spreadsheets are also something of an outlier, as they are a system of data manipulation already developed before it was practical to computerize them.

Scheme has rational numbers in its number tower, is that the kind of thing you mean?

(= 22/7 44/14) #t

No. To satisfy the complaint, you would have to be able to create the rational-number type yourself in userspace, and moreover it would have to be built in such a way that you didn't need to worry much about cancellation.

Analogously, Rust or F# have type systems which allow you to build the Option type yourself easily: there is no magic behind them, and you can just write down whatever sum type you want. Similarly, we want to be able to build arbitrary quotient types (not just of numbers, but of general sets with equivalence relations) ourselves.

I don't think I have ever seen a mainstream language letting you design data types with a built-in normalization. The reason is that you normally have algebraic, i.e., sum and product, types. In such constructions you would expect construction and deconstruction to compose to the identity function. The closest that comes to mind are languages that marry algebraic data types with OO programming (scala, maybe OCaml, F#). There you can have constructing functions but the normalized result would still be expressed as a plain ADT. I also don't think that GADT's help here, but I might be wrong.

In any case, it is an interesting proposition. In order to be non-trivial the type system would have to be able to express the constraints of the normal form.

I think the most interesting design space is around not requiring normalisation. After all, if you have a normal form, you can probably represent it with sum and product types. Cubical Agda gives you this ability but it's really hard to use (as you might expect from one of the first attempts to create the functionality).

> The other thing that we do all the time in everyday life is a quotient, and as far as I know no programming language has a good way to represent that: something as basic as a fraction

How would the implementation of a general equivalence relation work? Just defining the equivalence relation does not yield a method for chosing a representative. Would you check the equivalence at each operation?

If the focus is on finite data structures only and the equivalence relation is "are the types isomorphic", then each type is isomorphic to the ordinary generating functor with some coefficients C : N->N:

  -- ogf(c,x) = Σ n:ℕ, cₙ xⁿ
  def ogf (c : ℕ → ℕ) (α : Type) :=
  Σ n:ℕ, fin (c n) × (fin n → α)

(fin n is finite type with exactly n elements)

For example list has coefficients Cn = {1,1,1,1...}

  inductive list (α : Type)
  | nil : list
  | cons (hd : α) (tl : list) : list

and binary trees

  inductive bin_tree (α : Type)
  | leaf : bin_tree
  | branch (x : α) (left : bin_tree) (right : bin_tree) : bin_tree

have coefficients the Catalan numbers {1,1,2,5,14,42,132,429,...}.

Computing those coefficients from a type definition is not always trivial though (see the symbolic method http://algo.inria.fr/flajolet/Publications/AnaCombi/book.pdf).

This can be extended to infinite data structures too by switching the natural numbers to ordinal numbers in the ogf definition.

> Just defining the equivalence relation does not yield a method for chosing a representative. Would you check the equivalence at each operation?

Choosing a canonical representative is not feasible in the general case, so yes one would need to prove that every operation respects the equivalence relation.

What do you mean by "respects the equivalence relation"?

Do you demand that f(x) ~ x implies that f(x) = x ? (~ being the equivalence and = being identity).

We demand that x ~ y implies f(x) ~ f(y).

I don't think the addition of sum types broadly will be the panacea that people think. Software does need to be maintained, simpler things are easier to maintain.

Sum types are simpler, and harder to misuse, than the common alternatives (unions or dynamic typing).

What simpler alternative is there? The OOP way would be to always hide data. This certainly has a different set of trade-offs, and sometimes requires the visitor pattern. Maintainable and simple are not words I would use to describe these cases.

The other alternative is to emulate sum types through run-time type information or using code generation like protobuf. I also fail to see how these approaches are simpler or more maintainable.

Sum types are not a panacea for all software development ills, but they're the simplest and most direct solution to a concrete problem: My data is either this type or that type.