11 ms·
Sum Types Are Coming (2015)
- taneq 9y agoDo we really need a new name for this? It's basically "safe C-style unions", but pretty much everything in C is unsafe, so you might as well just call it "unions".
- Fufjeudndh 9y agoIt's not a new name, just one you're unfamiliar with.
- saurik 9y agoThis is not a new name... in the theory of algebraic data types there is a model of what it means to add and multiply types, resulting in "sum" and "product" types. I am not 100% sure but I believe these terms have been used since the early 70s. The term "union" as used in C is highly related but not quite the same. If you add a tag to the union (and so have a "tagged union", often represented in C as a struct with an enum and a union) then you are equivalent in an information sense (but the usage is still different, as a C union says something very specific about how memory is used).
- Taniwha 9y agoas mentioned elsewhere 'union' originally came from Algol68 where (eventually) they were implemented exactly as described in the article
- nixpulvis 9y agoNames are evil, abolish yourself of all naming and achieve true enlightenment!
- Fufjeudndh 9y agoI sure hope so
- nixpulvis 9y agosame <3
- bcherny 9y agoNote that TypeScript and Flow have implemented sum types since this post was published.
- catnaroek 9y agoNo, they haven't. Union types and sum types are semantically very different from each other.
- pianom4n 9y agoYes, Flow has. https://flow.org/en/docs/types/unions/#toc-disjoint-unions https://flow.org/en/docs/types/unions/#toc-disjoint-unions
- catnaroek 9y agoSum types are a universal construction: you take any two types, and produce yet another type. In particular, you can sum a type with itself. Disjoint unions give you nothing of the sort. In other words: learn to mathematics.
- dang 9y ago> In other words: learn to mathematics That breaks the HN guidelines by crossing into incivility. You'd stopped doing that on HN, which is great, so please don't resume. This comment would be better if it (a) dropped the rude bit and (b) made the distinction from disjoint unions more clearly. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- xelxebar 9y agoThe tone of the parent comment is a bit aggressive, but the content is relevant. Just in case it's not clear, the union of sets "merges" elements that are identical whereas in the (direct) sum each element gets tagged with where it comes from. Formally, we have a set that indexes over the sets we want to sum and then we just Cartesian product each set with it's index before unioning. In abstract nonsense we usually write A ⊕ B = (A × {0}) ∪ (B × {1}) where ⊕ is the direct sum operator. So there direct sum of a set with itself is quite different from a plain union. For more than two sets we just index over things in the obvious way and write ⨁ᵢ Aᵢ = ∪ᵢ (Aᵢ × {i}) What parent means by universal property is that any that collection of functions {fᵢ : Aᵢ → C} can be decomposed into functions {gᵢ : Aᵢ → ⨁ᵢ Aᵢ} and a single, uniquie g: ⨁ᵢ Aᵢ → C where fᵢ = g ∘ gᵢ. With a little thought, the universal property above seems obvious, and with a little more work, you can see that it is actually equivalent to the definition of direct sum above. Thus we can actually take this universal property as the definition of direct sum and derive the original. The cool thing is that the universal property doesn't refer to set-specific operations---just functions/maps---so we actually have a definition for the direct sum of things more general than sets. That is, we can form the direct sum of things like monoids, groups, certain classes of differential functions, etc. I could go on, but this road leads to madness^W category theory.
- nixpulvis 9y agoSum types are one of the best things, as they empower very good `match` style conditionals.
- sevensor 9y agoI can attest to this. I've just done a project in F# -- my first experience using a statically typed functional language beyond messing around in a REPL -- and the expressive power of this combination is intoxicating. I may have gone overboard; I found it hard to write procedural code in F#, so I split up my procedures into steps, with a type to model each step and a sum type to model the whole procedure. Coming from C / Python, where I was used to procedural code mostly working most of the time and then failing in hilarious ways, this was a revelation. A language where I can make the compiler check my procedural logic for me! Liberating!
- yetanotheruser 9y agoDoes f# have a good repl? What ml style language has the closest thing approaching a lisp style repl?
- tom_mellior 9y agoNot saying it's the closest to what you have in mind, but you could look at the Emacs Tuareg mode for OCaml. Here is a reference card: http://www.ocamlpro.com/files/tuareg-mode.pdf http://www.ocamlpro.com/files/tuareg-mode.pdf If you are a SLIME fan, you might notice that some of the key bindings to interact with the toplevel (the OCaml word for "REPL") are identical in Tuareg. That said, although this will sound tongue-in-cheek: Having used Isabelle and Coq with their interactive editors, I find their approach better than a REPL. In these systems, you execute code directly from your source file, as opposed to (conceptually) sending snippets of code to a REPL. There is no concept of code you have written in the source (or the REPL) which is not synced up with the state of the REPL (or the source code, respectively). I wish other languages had modes like this. There seems to be one for Prolog, but I've never used it and don't know how well it works in practice: https://www.metalevel.at/ediprolog/ https://www.metalevel.at/ediprolog/
- Cieplak 9y agoOnce you get the hang of algebraic data types (ADTs), definitely check out generalized ADTs (GADTs). They reduce the amount of code required to express a solution, make the type system do a ton of work for you to prevent bugs from compiling, and make it easier to embed domain-specific languages in your code. A lot of the GADT tutorials out there are a little abstract for my taste and I wish there were more examples with tangible applications, but this one is decent: http://joeyh.name/blog/entry/making_propellor_safer_with_GADTs_and_type_families/ http://joeyh.name/blog/entry/making_propellor_safer_with_GAD...
- tom_mellior 9y agoI also liked this one: https://blog.janestreet.com/why-gadts-matter-for-performance/ https://blog.janestreet.com/why-gadts-matter-for-performance...
- Peaker 9y agoWhy do they reduce the amount of code? They add the ability for constructors to carry constraints, which aids expressivity in some cases. But the majority of GADT uses purely add safety. Can use ordinary ADT without a type-variable that is correlated with the data constructor, and crash at runtime if the constructors don't match.
- tom_mellior 9y ago> Why do they reduce the amount of code? [...] crash at runtime if the constructors don't match. You answered yourself: If you cannot have these runtime type mismatches, you don't need to write the corresponding bookkeeping and checking code.
- Peaker 9y agoYou don't have to write it - you just have to avoid -Wall :-)
- dpwm 9y agoI thought GADTs would be useless to me when I first heard the explanation of GADTs as imposing additional constraints on ADTs. Whilst technically true, it feels like it's missing the point. The real power of GADTs comes from the fact that you can use the type at compile time. This means that in OCaml I can do something like: type 'a t = | Int : int t | Float : float t let print : type a. a t -> (a -> string) = function | Int -> string_of_int | Float -> string_of_float I can the do (print Float) and receive string_of_float. I can do (print Int) and receive string_of_int. Both have drastically different types, but due to the constraints that the GADT imposes it is fully type safe and the type is known at compile time. Although this is a slightly contrived and useless example, there are scenarios where this can prove immensely useful that are not that far away and really aren't so useful when done with ADTs. Think serializing -- you would have to convert to the ADT first which isn't so useful. If you're interested in something useful, take a look at [0] (shameless plug), a very early alpha version of a similar idea allowing conversion from and to JSON. EDIT: this is not inlined as I recall. False memory. The reason it isn't is probably because you can use existential types in which case the type would not be known at compile time. [0] https://github.com/dpwm/typespec https://github.com/dpwm/typespec
- fermigier 9y agoFor Python (as a library, not a core language construct): https://github.com/radix/sumtypes/ https://github.com/radix/sumtypes/ (Same year - 2015 - as the original post ;)
- fphilipe 9y agoIf you're looking for a simple sum type without associated value, the standard library's enum works quite well: https://docs.python.org/3/library/enum.html https://docs.python.org/3/library/enum.html
- philpee2 9y agoIf you're using mypy, there's also the Union type https://mypy.readthedocs.io/en/latest/kinds_of_types.html#union-types https://mypy.readthedocs.io/en/latest/kinds_of_types.html#un...
- platz 9y agosum types are are not all that different from subtyping+inheritance, it's simply the other side of the expression problem.
- nixpulvis 9y agoOther side?
- platz 9y agohttp://wiki.c2.com/?ExpressionProblem http://wiki.c2.com/?ExpressionProblem > The "expression problem" is a phrase used to describe a dual problem that neither ObjectOrientedProgramming nor FunctionalProgramming fully addresses. "dual problem", meaning you choose ObjectOrientedProgramming or FunctionalProgramming, which neither fully address. neither "side" is able to resolve the ExpressionProblem
- nixpulvis 9y agoInteresting, though I'm not sure I like the notion that it's a two sided coin. I've also never been a fan of the OO vs FP argument.
- yen223 9y agoUnlike subtyping, sum types are bounded - you can't add new variants without modifying the originally-defined type. That's a huge difference in terms of code architecture - it enables things like exhaustive pattern matching, and allows the programmer to enforce stronger invariants in the code.
- rbehrends 9y agoSubtyping can be closed, too (see Scala's sealed classes, for example) and algebraic data types can be open (see OCaml's extensible variants [1] or polymorphic variants [2]). This is simply a distinction between closed and open sum types. [1] https://caml.inria.fr/pub/docs/manual-ocaml/extn.html#s%3Aextensible-variants https://caml.inria.fr/pub/docs/manual-ocaml/extn.html#s%3Aex... [2] http://caml.inria.fr/pub/docs/manual-ocaml-400/manual006.html#toc36 http://caml.inria.fr/pub/docs/manual-ocaml-400/manual006.htm...
- okket 9y agoWhat is the difference between these 'sum types' and Swifts enum type? Also I think the name 'sum type' is bad. Nothing gets added or summed up, just combined and selectively chosen. For this reason I find supercharging 'enum', like Swift does, a more logical solution.
- silluk 9y agoA sum type is the more general name for a Swift/Rust enum.
- matt_kantor 9y agoThe numbers of values in the types are what get summed up. The sum type `Boolean | Byte` has 2 + 256 unique values while the product type `(Boolean, Byte)` has 2 * 256 unique values
- dbaupp 9y agoSwift enums are sum types. Various languages use different keywords to access the same concept: - Rust: 'enum' - Swift: 'enum' - Haskell: 'data' - F#: 'type' - Ocaml: 'type' > Also I think the name 'sum type' is bad. Nothing gets added or summed up, just combined and selectively chosen. For this reason I find supercharging 'enum', like Swift does, a more logical solution. They're the same solution... In any case, the name sum comes from viewing types "algebraically" as the article discusses. Doing addition of types with a sum type has a lot of similar properties to doing addition of numbers, and similarly doing multiplication of types with a product type (tuple, struct or class, in Swift) has a lot of similar properties to doing multiplication of numbers.
- gavinlynch 9y agowhy would you want to view a programming language algebraically?
- yorwba 9y agoIt lets you reuse your existing knowledge about algebra to transform programs. For example if you have a data type that has two different cases (= sum) each of which has a bunch of fields (= factors in a product) some of which are shared (= common factors in a sum of products) then you can literally factor them out, just like you can factor A * B * C + A * D * C into A * (B + D) * C.
- reacweb 9y agoAre they really coming? When I was a student, I have encountered them the first time in Ada83 (discriminant records) in 1990, then in gofer (a variant of Haskell developed at Oxford) in 1992, then in Caml light (the ancestor of OCaml) the same year.
- Crespyl 9y agoI think maybe "coming to the mainstream" fits better. I too saw it in Ada in school, and of course Haskell and friends have had them for ages. There does seem to be recent trend of popular, highly visible languages that are adding the feature though. I think the biggest thing though is really that the pattern matching syntax that makes them so easy to use is becoming more common. You can have Sum types without pattern matching, and vice versa, but it seems to be much more common now to expect any new language to include pattern matching.
- s-kim 9y agoHi everyone, similar to the link, I wrote a tech memo about an algebraic data type to share what I have learned while studying the data type. https://kstreee.github.io/techmemo/algebraic.pdf https://kstreee.github.io/techmemo/algebraic.pdf
- ManDeJan 9y agoI prever the c++ name variant, super usefull and new addition to c++17
- humanrebar 9y agoAlso, std::optional, which is analogous to Maybe. Of course, both have been in boost for some time now. C++ so far has been doing this at the library level. But it remains to be seen if they will make their way into actual interfaces, for example in standard algorithms.
- IshKebab 9y agoHopefully flow typing will be next. It's a really cool idea and I'm surprised it hasn't caught on more. https://en.wikipedia.org/wiki/Flow-sensitive_typing https://en.wikipedia.org/wiki/Flow-sensitive_typing
- girvo 9y agoOne of my favourite features of Flow is the ‘*’ type and having Flow handle the given type based on control flow via “if” checks. You can achieve it somewhat in TypeScript too, IIRC. Neither are quite as powerful as I would like, but then what I would like is basically magic!
- majewsky 9y agoOooh, that concept has a name! This has been on the list of features of my dream programming language for a long time, but I didn't know this has a name and Wikipedia article and everything.
- Taniwha 9y agoOf course there's nothing new under the sun, this is one of the features of Algol68 (1968) that Wirth discarded when he made Pascal They're not coming, they've been and gone, probably a couple of times
- tom_mellior 9y agoAll I know about Algol 68 is what I just gleaned from Wikipedia, but there I got the impression that what it had was a limited form. Namely, the type indexed things mentioned in the featured article as present in C++ and D, where you don't have tags and thus cannot usefully distinguish different variants with the same underlying type.
- Taniwha 9y agonope, A68 unions had hidden tags (strictly speaking the spec didn't say they had tags but it was the only obvious implementation) it did have a case statement to switch on the tags and extract the values as described above
- jstimpfle 9y agoOne thing I really need is getting at "the type field". This is useful information by itself, and I want it most of the time - but I think in Haskell it's not possible to get at it without manually defining a "type type" and a function that computes that type from a given sum-typed data. I don't think that lambdas/closures have such a problem in most programming languages. It's still unclear how to handle function pointers for lambdas/closures, but it should be a lot easier to make a lambda into a real function than changing a datatype definition when it's already used across the codebase. So, I think sum types are really another one of those ideas which may prevent some bugs sometimes, but in the end are not generally super useful, and are just a little too clever and end up causing a more work than they save. At least unless there's a well-defined representation from which we can extract the type information, in which case I'd probably be happy to use them.
- tom_mellior 9y agoCould you give an example in a (possibly hypothetical) programming language of your choice of what you mean by "the type field", and what you would do with it? Maybe we could point you to something that does what you want. Though I do wonder if reflection on type information (at runtime?) would be useful and easy for you if you find basic algebraic data types "a little too clever" and "causing more work than they save".
- jstimpfle 9y agoRegarding the type field, look for "enum EventType type;" in the article. (In practice I would not use "enum EventType", but simply "int" - but anyway). What I would do with it? Like the result of (x+y), or any type of data, I can use it for whatever I need. I might simply want to count the number of occurences of each "type". Often I'm simply not interested in the data besides the "type", and in these cases I find that case-matching is a lot of boilerplate. And it doesn't reify the "type" to authoritative runtime values. Which, as you say, might be done with reification support from the language, but I don't want to bother with that -- and it would not allow me to choose the possible values of the type field, which might be a requirement if the options are defined somewhere else.
- gameswithgo 9y agoThe last couple of years I've been doing a lot of exploring different languages and language features. Sum types are one of the few features I've come across that seem to have the potential for large, practical benefit. Not only do you get the potential to eliminate null from a language with Option or Maybe types, but many cases where you might use multiple classes and files to express some hierarchy, can be replaced with just a few lines of code that is so easy to read you can even show it directly to the non programmers working on the project, to work through the definition together. This especially happens nicely when the syntax is built into the language in a succinct way as in F# / OCaml (possibly others as well!)
- masklinn 9y agoIt's also a convenient way to implement "value-based" state machines (where the entire machine is a single type with a value for each state, as opposed to type-based where each state is implemented as a different — and possibly completely incompatible — static state).
- tomjakubowski 9y ago+1. They are a huge help for managing things like connection state. You can create powerful, statically-enforced invariants, like that a lifetime of a socket is 1:1 with a state of your state machine.
- gumby 9y agoSince this article was written c++17 has added std::variant and things like std:any. But his complaint about c++ matching being verbose is really AI complaint that c++ typically doesn’t have a first class type system (unless rtti is used, and even then you can’t create new types at runtime). This lack is either a limitation or benefit depending on your objectives for the program you are developing. There isn’t a One True Approach; I do all my work in Common Lisp or C++ and although both are multi-paradigm languages they aren’t substitutable for each other.