6 ms·

Algebraic data types: things I wish someone had explained about FP (2019)

92 points by weatherlight 5y ago

VHRanger 5y ago
YOU DONT NEED TO SHOUT THE TITLE
- deleted 5y ago
  [deleted]
- hdjjhhvvhga 5y ago
  Using caps in titles is a centuries-long tradition. Labeling caps as shouting has just a few decades.
  - Zababa 5y ago
    Try your reasoning with how people call people with a different skin color and you'll understand the problem.
    - _dain_ 5y ago
      total non-sequitur
      - Zababa 5y ago
        Depends on how you see it. If you look only at the "usage" part, I think my point is fine. There's another part of the equation, which is the media. Internet and printed text (which was what used full caps titles) are not the same, so applying the printed text rules to internet text doesn't make sense. But my point about usage evolving still stands. Things change more quickly these days than before. So comparing simply the length of time something existed is a fallacy. I don't know if it's possible to compare this exactly, but I would suppose, in terms of "evolution of culture/usages", an internet year is worth at least a decade of printed text before the internet.
SahAssar 5y ago
Even if the title is shown in uppercase in the article it is handled with `text-transform: uppercase;` so I'm not sure how it became uppercased here unless the poster did it manually.
- weatherlight 5y ago
  I literally copied I except i shortened the functional programing bit to FP. (char length) I use the Grammarly Chrome plugin, which sometimes causes text to behave differently when it's copied and pasted.
tjpnz 5y ago
That site's beautiful.
- _dain_ 5y ago
  Sadly it's totally incompatible with dark mode so it's painful to read.
open-paren 5y ago
Discussed previously - https://news.ycombinator.com/item?id=21571938 https://news.ycombinator.com/item?id=21571938 (November 19, 2019 — 242 points, 112 comments)
ldiracdelta 5y ago
""" But, you might also notice a functional programmer over there. The one with a smug look and condescending smile on their face. And after bracing yourself, you ask them 'What’s so amusing?' [...] Now, let’s assume you manage to refrain from physical violence. """ Hilarious!
Smaug123 5y ago
I would add only one thing to the article. Algebraic data types are so great because they are so dumb. ADTs are inherently stateless, for example (as long as you don't put stateful things inside them). This makes them extremely easy to reason about: they're no harder to reason about than an integer is.
tunesmith 5y ago
Is the combination of sum types and product types... sufficient in some way that product types alone are not? I have the sense it is but I'm not putting my finger on how.
- truculent 5y ago
  Yes. Product types (i.e. tuples) force you to consider all possible combinations of things, and the types have to be the same across all variants. This means that there are certain states that may be impossible in practice, but possible to represent in your data. This can lead to unnecessary code at best, or undefined behaviour and bugs at worst. For example, let's say we want to model loading data from a server. With ADTs: type WebData = NoRequest | Loading | Failure HttpError | Success MyData With product types only (and enums), how would we reconcile that the request could return an error _or_ data? We could try something along the lines of: type WebDataStatus = NoRequest | Loading | Failure | Success type WebData = (WebDataStatus, Maybe HttpError, Maybe MyData) Where the error and data fields are optional. But in this case, it would be possible to have both error _and_ data fields populated. Not ideal!
  - bradrn 5y ago
    It gets worse — technically speaking, your second ‘WebDataStatus’ is also a sum type! Admittedly most non-functional programmers would call it an enumeration, but nonetheless, a language without support for any sum types at all would also necessarily need to lack enumerations. (I therefore prefer to think of most non-functional programming languages as having an incomplete implementation of sum types rather than having no sum types.)
    - truculent 5y ago
      Yes, agreed!
- contravariant 5y ago
  That's an interesting question, but one that doesn't seem to have a really well defined answer. The best I can come up with is that if you want to talk about the product of function types (A -> X) x (B -> X) then a sum type allows you to summarize this a single function type (A+B -> X). With just a product you could already do something similar for the type (X -> A) x (X -> B) which is equivalent to (X -> AxB), but with a sum type you have the dual variant as well. And I suppose that with sum and product types together you can kind of express BNF like rules directly in the type system. Which makes things like expressing syntax trees a hell of a lot cleaner. That said ultimately a type system is just a part of the language you can use to express certain rules, you can usually still decide on your own rules you'll just have to enforce them manually.
LandR 5y ago
I'm finding the code snippet colours and fonts really annoying to read. Actually, even the main text on the site with the `blotchy` background is hard to read for me. At least FF reader mode makes it readable.
- kevbin 5y ago
  I dig the Beagle Brothers’ aesthetic.
- alextheparrot 5y ago
  Was just going to say how much I loved it, guess that’s art.
IshKebab 5y ago
Typescript has a fairly official way to do sum types (less poncily known as tagged unions): https://www.typescriptlang.org/docs/handbook/unions-and-intersections.html https://www.typescriptlang.org/docs/handbook/unions-and-inte... Might make the example a bit clearer.
TheGoodBarn 5y ago
Never learned so much from a background image that looks like a tortilla
- tobr 5y ago
  I think it’s a depiction of the average skin tone of an FP programmer.
marcosdumay 5y ago
> And you’d be right. Arrays, Objects, Maps, WeakMaps, and Sets are all algebraic data types. Hum... I have a very strong impression that it's only the type system that can be algebraic. For single types, the name doesn't make any sense. It's like asking if "2" is a vector. You can have a vector space where it's an element, but without context, the question doesn't make sense.
- gmfawcett 5y ago
  You can think of data structures like arrays in an algebraic way. Consider the type of "arrays of booleans, of length 8." This type is in 1:1 correspondence with the type of "8-tuples of booleans", i.e., it's a product type. Like any algebraic type, we can compute its cardinality: there are 2^8 values in this type. Similar thinking can be applied to the other (abstract) types that you mentioned, although it helps to have information about their internal structure.
  - Hercuros 5y ago
    Although if you just consider 1-1 correspondence, then basically any type with a countable number of inhabitants is isomorphic to the integers (when the type is viewed as a set of inhabitants). And that makes sense, because we can always just take the binary representation of any data type in memory. And if you just have unit type, empty type, sums and products, then you can only make types with finitely many inhabitants. Adding the integers to that makes you able to make any countable type, but potentially in a trivial way as described above. Therefore just viewing the types as sets does not give a very satisfactory basis for determining whether a type is an "algebraic data type". Maybe we could do better if we consider some more aspects related to type safety, but it's not immediately obvious to me how.
    - gmfawcett 5y ago
      "Any type with a countable number of inhabitants is isomorphic to the integers" --> I assume you mean "countable" in the sense of "countably infinite." Clearly the finite types can't be put into correspondence with the integers. I agree that viewing the types just in terms of their cardinality isn't terribly insightful. But I do think it's helpful to realize that arrays aren't some other kind of thing that's separate from ADTs, and that you can bring the same algebraic reasoning tools to bear on arrays (and other pedestrian data types).
nybble41 5y ago
The 'class Digit' example has 11 possible values, not 10: > d = new Digit('') Digit { value: NaN }
AnonHP 5y ago
This needs (2019) in the title since the post was written/published in 2019.
deleted 5y ago
[deleted]

92 points by weatherlight 5y ago

VHRanger 5y ago

YOU DONT NEED TO SHOUT THE TITLE

deleted 5y ago
[deleted]
hdjjhhvvhga 5y ago
Using caps in titles is a centuries-long tradition. Labeling caps as shouting has just a few decades.
- Zababa 5y ago
  Try your reasoning with how people call people with a different skin color and you'll understand the problem.
  - _dain_ 5y ago
    total non-sequitur
    - Zababa 5y ago
      Depends on how you see it. If you look only at the "usage" part, I think my point is fine. There's another part of the equation, which is the media. Internet and printed text (which was what used full caps titles) are not the same, so applying the printed text rules to internet text doesn't make sense. But my point about usage evolving still stands. Things change more quickly these days than before. So comparing simply the length of time something existed is a fallacy. I don't know if it's possible to compare this exactly, but I would suppose, in terms of "evolution of culture/usages", an internet year is worth at least a decade of printed text before the internet.

SahAssar 5y ago

Even if the title is shown in uppercase in the article it is handled with `text-transform: uppercase;` so I'm not sure how it became uppercased here unless the poster did it manually.

weatherlight 5y ago
I literally copied I except i shortened the functional programing bit to FP. (char length) I use the Grammarly Chrome plugin, which sometimes causes text to behave differently when it's copied and pasted.

tjpnz 5y ago

That site's beautiful.

_dain_ 5y ago
Sadly it's totally incompatible with dark mode so it's painful to read.

open-paren 5y ago

Discussed previously - https://news.ycombinator.com/item?id=21571938 https://news.ycombinator.com/item?id=21571938 (November 19, 2019 — 242 points, 112 comments)

ldiracdelta 5y ago

""" But, you might also notice a functional programmer over there. The one with a smug look and condescending smile on their face. And after bracing yourself, you ask them 'What’s so amusing?' [...] Now, let’s assume you manage to refrain from physical violence. """ Hilarious!

Smaug123 5y ago

I would add only one thing to the article. Algebraic data types are so great because they are so dumb. ADTs are inherently stateless, for example (as long as you don't put stateful things inside them). This makes them extremely easy to reason about: they're no harder to reason about than an integer is.

tunesmith 5y ago

Is the combination of sum types and product types... sufficient in some way that product types alone are not? I have the sense it is but I'm not putting my finger on how.

truculent 5y ago
Yes. Product types (i.e. tuples) force you to consider all possible combinations of things, and the types have to be the same across all variants. This means that there are certain states that may be impossible in practice, but possible to represent in your data. This can lead to unnecessary code at best, or undefined behaviour and bugs at worst. For example, let's say we want to model loading data from a server. With ADTs: type WebData = NoRequest | Loading | Failure HttpError | Success MyData With product types only (and enums), how would we reconcile that the request could return an error _or_ data? We could try something along the lines of: type WebDataStatus = NoRequest | Loading | Failure | Success type WebData = (WebDataStatus, Maybe HttpError, Maybe MyData) Where the error and data fields are optional. But in this case, it would be possible to have both error _and_ data fields populated. Not ideal!
- bradrn 5y ago
  It gets worse — technically speaking, your second ‘WebDataStatus’ is also a sum type! Admittedly most non-functional programmers would call it an enumeration, but nonetheless, a language without support for any sum types at all would also necessarily need to lack enumerations. (I therefore prefer to think of most non-functional programming languages as having an incomplete implementation of sum types rather than having no sum types.)
  - truculent 5y ago
    Yes, agreed!
contravariant 5y ago
That's an interesting question, but one that doesn't seem to have a really well defined answer. The best I can come up with is that if you want to talk about the product of function types (A -> X) x (B -> X) then a sum type allows you to summarize this a single function type (A+B -> X). With just a product you could already do something similar for the type (X -> A) x (X -> B) which is equivalent to (X -> AxB), but with a sum type you have the dual variant as well. And I suppose that with sum and product types together you can kind of express BNF like rules directly in the type system. Which makes things like expressing syntax trees a hell of a lot cleaner. That said ultimately a type system is just a part of the language you can use to express certain rules, you can usually still decide on your own rules you'll just have to enforce them manually.

LandR 5y ago

I'm finding the code snippet colours and fonts really annoying to read. Actually, even the main text on the site with the `blotchy` background is hard to read for me. At least FF reader mode makes it readable.

kevbin 5y ago
I dig the Beagle Brothers’ aesthetic.
alextheparrot 5y ago
Was just going to say how much I loved it, guess that’s art.

IshKebab 5y ago

Typescript has a fairly official way to do sum types (less poncily known as tagged unions): https://www.typescriptlang.org/docs/handbook/unions-and-intersections.html https://www.typescriptlang.org/docs/handbook/unions-and-inte... Might make the example a bit clearer.

TheGoodBarn 5y ago

Never learned so much from a background image that looks like a tortilla

tobr 5y ago
I think it’s a depiction of the average skin tone of an FP programmer.

marcosdumay 5y ago

> And you’d be right. Arrays, Objects, Maps, WeakMaps, and Sets are all algebraic data types. Hum... I have a very strong impression that it's only the type system that can be algebraic. For single types, the name doesn't make any sense. It's like asking if "2" is a vector. You can have a vector space where it's an element, but without context, the question doesn't make sense.

gmfawcett 5y ago
You can think of data structures like arrays in an algebraic way. Consider the type of "arrays of booleans, of length 8." This type is in 1:1 correspondence with the type of "8-tuples of booleans", i.e., it's a product type. Like any algebraic type, we can compute its cardinality: there are 2^8 values in this type. Similar thinking can be applied to the other (abstract) types that you mentioned, although it helps to have information about their internal structure.
- Hercuros 5y ago
  Although if you just consider 1-1 correspondence, then basically any type with a countable number of inhabitants is isomorphic to the integers (when the type is viewed as a set of inhabitants). And that makes sense, because we can always just take the binary representation of any data type in memory. And if you just have unit type, empty type, sums and products, then you can only make types with finitely many inhabitants. Adding the integers to that makes you able to make any countable type, but potentially in a trivial way as described above. Therefore just viewing the types as sets does not give a very satisfactory basis for determining whether a type is an "algebraic data type". Maybe we could do better if we consider some more aspects related to type safety, but it's not immediately obvious to me how.
  - gmfawcett 5y ago
    "Any type with a countable number of inhabitants is isomorphic to the integers" --> I assume you mean "countable" in the sense of "countably infinite." Clearly the finite types can't be put into correspondence with the integers. I agree that viewing the types just in terms of their cardinality isn't terribly insightful. But I do think it's helpful to realize that arrays aren't some other kind of thing that's separate from ADTs, and that you can bring the same algebraic reasoning tools to bear on arrays (and other pedestrian data types).

nybble41 5y ago

The 'class Digit' example has 11 possible values, not 10: > d = new Digit('') Digit { value: NaN }

AnonHP 5y ago

This needs (2019) in the title since the post was written/published in 2019.

deleted 5y ago

[deleted]