6 ms·
Being able to build good representations of things is important. So many programming languages lack something as basic as sum types, which puts them behind the
by lmm 6y ago
Being able to build good representations of things is important. So many programming languages lack something as basic as sum types, which puts them behind the state of the art in the 1970s. Yes, Haskell has some fancier stuff in it as well, but a lot of the value comes from simply having a good way to represent "this or that" and applying it properly.
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 (i.e. a pair of integers, but two pairs are equivalent when ...) can't be expressed except in an ad-hoc way.
I appreciate the author's enthusiasm for offering a large standard library of datatypes - I certainly think things like decimals and trees ought to be more available than they are - but I don't think we can even start on that until we actually have good tools for defining datatypes. And actually the best way to get there might be to have fewer built-in datatypes, and force ourselves to go through the work of defining numbers and strings and so on "in userspace", using the normal language facilities. That would quickly highlight a lot of quite basic things that a lot of languages are missing - e.g. literals for user-defined types are incredibly painful in a lot of algol-family languages.
- enriquto 6y ago> 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?
- hiker 6y agoIf 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 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.
- zozbot234 6y ago> 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.
- Smaug123 6y agoQuotients 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.
- gonzo41 6y agoI 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.
- TazeTSchnitzel 6y agoSum types are simpler, and harder to misuse, than the common alternatives (unions or dynamic typing).
- mtzet 6y agoWhat 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.
- rm445 6y agoScheme has rational numbers in its number tower, is that the kind of thing you mean? (= 22/7 44/14) #t
- Smaug123 6y agoNo. 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.
- choeger 6y agoI 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.
- Smaug123 6y agoI 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).
- tmcw 6y ago(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.
- sillysaurusx 6y agoHey, 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/ 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."
- legobmw99 6y ago(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”
- dragonwriter 6y ago> 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.
- jan_Inkepa 6y agoI 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).
- dragonwriter 6y agoIsn'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.
- jacobolus 6y agoIn 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.
- 6y ago