Algebraic Data Types (Functors, Monads, etc)

Lately there have been multiple discussions on the forum about algebraic data types (monads, and the likes).
Because this is a concept that is new or foreign to a lot of people (and widely considered tricky to understand), I thought it would be a good idea to make a topic that:

  1. is a Wiki where guides that explain how ADTs work and why they are useful can be placed.
  2. Can be used as a general discussion topic about them.

Qqwy’s 5-minute explanation using fruits and cupcakes:

  • Don’t panic. They are not scary! :slight_smile:
  • Algebraic Data Type is just a fancy way of saying ‘container’ (as in: ‘compound structure’).
  • You are using ADTs and their interfaces even if you do not know it.
  • Recognizing them can help you to write more generic (reusable) code.

Quick summary:

| Interface name              | 'Kitchen' example                                                                                                                                                                     | Formal Kitchen syntax                                                          | Fully formal syntax      |
| Normal Function Application | Given `an apple`, and something to do with that apple such as `cut`, return the result of that: `cut(apple)`                                                                          | Apple -> (Apple -> CutApple ) CutApple                                         | a -> (a -> b) -> b       |
| `map`                       | Given `a box of apples`, and something to do with each apple, such as `cut`, return `a box of cut(apple)s`                                                                            | Box Apple -> (Apple -> CutApple) -> Box CutApple                               | f a -> ( a -> b) -> f b  |
| `apply`                     | Given `a box of cupcakes to decorate` and `a box of decorations`, return `a box of decorated cupcakes`                                                                                | Box (Decoration -> DecoratedCupcake) -> Box Decoration -> Box DecoratedCupcake | f (a -> b) -> f a -> f b |
| `wrap/pure`                 | Given `an apple`, return `a box filled with one apple`.                                                                                                                               | Apple -> Box Apple                                                             | a -> f a                 |
| `chain`                     | Given `a taco filled with salad` and `a function that takes 'something', puts some sauce on top and then wraps in a tortillia returning a taco`, return `a taco with salad and sauce` | Taco Salad -> (Salad -> Taco SaladWithCheese) -> Taco SaladWithCheese          | f a -> (a -> f b) -> f b |

ADT Names

  • (Function application can be used on everything without needing extra syntax.)
  • A Functor is a container for which you can define map.
  • An Applicative Functor is a container for which you can define map, apply and wrap for.
  • A Monad is a container for which you can define map, apply, wrap and chain for.

Some notes

####About naming in different contexts:

  • map is also known as fmap and <$> and in Haskell.
  • apply is also known as <*> in Haskell.
  • wrap is also known as pure and return in Haskell, and as unit in Scala.
  • chain is also known as >>= in Haskell, and also known under the name bind in Scala and Rust.

List of other explanations of Algebraic Data Types

List of ADT related libraries in Elixir


Do not mix Abstract Data Type with Algebraic one. They both use ADTs as a short name. Yes i know…


I have written an article a while back that tries to explain monads (in Haskell mostly) from a practical point of view: by focusing on what they solve. I conflate many stuff from Applicatives and Functors into it that I’m sure I have technical mistakes here and there, but I hope I didn’t stray from the general idea.

You can read it here: Monads in Functional Programming: a Practical Note (feedbacks are welcome!).

1 Like