Algebraic Data Types (Functors, Monads, etc)

[Qqwy]

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!
• 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

• Many things are Functors (more generic, less powerful), fewer things are Monads (more specific, but more powerful).
• A list of common data types that fall in one of these categories can be found here.

####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

• Functors, Applicatives and Monads in Pictures
• List of other Monad tutorials on the Haskell Wiki.
• Monads in Functional Programming: a Practical Note

List of ADT related libraries in Elixir

• FunLand - topic - hex.pm - github
• A Freer Monad implemented in Elixir - topic - github
• Algae - Bootstrapped Algebraic Data Types for Elixir - hex.pm github
• Witchcraft A category library for Elixir - hex.pm - github

[DianaOlympos]

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

[bobbypriambodo]

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!).