## Collapsing Types vs Monads (followup)

Last week’s post about an automatically flattening future type received a lot of feedback. One of the running themes in the discussion was how collapsing types relate to monads:

“Type operators that collapse when you nest them inside of themselves”, along with some conditions to actually work as you would expect, precisely describe the idea of monad.

[...] This is the textbook definition of a monad.

monads, anyone?

So the article and discussion here bring up a key question: what are the monads such that m (m a) and m a are isomorphic?

Given the mix of confusion and interest, I want to clear up how monads relate to collapsing types.

### Different

Collapsing types aren’t the same thing as monads, and neither is a subset of the other. They are attributes that can apply independently.

A collapsing type is a type that satisfies the property that nesting it inside itself has no effect. A must act identically to a under all circumstances, for to be a collapsing type.

A monad is a type that supports three operations: wrapping, transforming, and flattening (more typically called , , and respectively). The operations must also satisfy a few work-in-the-obvious-way-please rules.

If you tell me that is a collapsing type, I still don’t know if the type supports the operations necessary to make it a monad. Collapsing types *technically* support flattening, in that a proper method doesn’t have to make any changes. However, collapsing types are not required to support wrapping or transforming.

Conversely, if you tell me that is a monadic type, I still don’t know if it satisfies the condition needed to qualify it as a collapsing type. Monads are not required to have operations that change nothing.

### Examples

There are non-collapsing non-monadic types, collapsing non-monadic types, non-collapsing monadic types, and collapsing monadic types. Just to really drive home that “collapsing” is separate from “monadic”, lets go over an example of each.

An example of a collapsing monadic type is , from last week’s post.

An example of a non-collapsing monadic type is . You can wrap anything into a list, transform the items in a list, and flatten lists of lists *but* a list of lists of integers is not the same as a list of integers.

An example of a collapsing non-monadic type is a type representing an unknown value stored on a remote server, where the details of the server potentially using a further-remote server are hidden (meaning you treat a exactly like a ). If the server doesn’t allow you to apply arbitrary operations to remote values, or create arbitrary remote values, then is not a monad.

An example of a non-collapsing non-monadic type is . It’s not a collapsible type, because a matrix of matrices of booleans is distinct from a matrix of booleans. It’s not a monad unless you specify a flattening operation, but you’ll find there aren’t any nice ones to pick because you can’t preserve the number of values. For example, properly flattening would require that seven be a square number (it’s not).

*Side note*: *Technically* you could make SquareMatrix into a monad by specifying a poor flattening operator, and so you might be tempted to say SquareMatrix is a monad. Don’t do it. Under that view, every type ever is a monad. Given a type T, you can make it a useless monad by picking a value v of type T and defining join, fmap and return to all unconditionally return v.

### Similar

Monads and collapsing types are different, but still related.

*In practice*, collapsing types you encounter will probably be monads. Mainly because most of them will be related to eventual results (e.g. promises/A+ in JavaScript, Twisted Python in Python, ppltasks for windows store apps in C++).

*In theory*, you can start from any monad (which may not be a collapsing type) and *derive* a related collapsing+monadic type by making the application of automatic. It’s what I did with last week. All the methods on did internal checks to see if flattening was necessary or not, to make a act exactly like a . This derivation makes more practical sense with some types (, , , ) than it does with others (, , , ).

Warning: a potential issue with the above derivation is the creation of self-referencing flattening cycles, where you end up with a type nested inside itself infinitely many times and keep trying to unwrap it. For example, adding the following three lines to my collapsing future’s python fiddle causes a flattening cycle:

```
cycle = Future()
cycle.trySetResult(cycle)
cycle.continueWith(out) #never halts
```

It’s probably a good idea to have runtime checks for this issue. Compile-time checks would be even better, but beware accidentally solving the halting problem.

### Summary

Collapsing types are not the same thing as monads.

You can transform any monadic type into a collapsing monadic type.

Next week: less type theory.

—

### Discuss on Reddit

—

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

## Archive

- strilanc
- What Quantum Computers Do Faster, with Caveats
- Naming Things: Fail-Useful
- Detecting Simple Cycles Forming, Faster
- Third Party Bit Commitment
- Angular Velocity is Simple
- Collection Equality is Hard
- Deadlocks in Practice: Don’t Hold Locks While Notifying
- Brute Force Parallelization
- A Year’s Worth of Opinions about Objective-C
- Referencing Substrings Faster, without Leaking Memory
- Not Crying Over Old Code
- Exploring Universal Ternary Gates
- Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
- Achieving Exponential Slowdown by Enumerating Twice
- Using Immortality to Kill Accidental Callback Cycles
- Cancellation Tokens (and Collapsing Futures) for Objective-C
- Visualizing the Eigenvectors of a Rotation
- Collapsing Futures in Objective-C
- Bug Hunting #1: Garbled Audio from End to End
- Impractical Experiments #1: Representing Numbers as Polynomials
- Implementing Quantum Pseudo-Telepathy
- Turn On Your Damn Warnings
- Big-O Made Trivial
- Unfathomable Bugs #7: The Broken Oven
- Solomonoff’s Mad Scientist
- Yearly Blogging Roundup #1
- What isn’t a Monad
- Searching a Sorted Matrix Faster
- How to Read Nested Ternary Operators
- Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
- My Bug, My Bad #4: Reading Concurrently
- Whole API Testing with Reflection
- Optimizing a Parser Combinator into a memcpy
- Don’t Treat Paths Like Strings
- Breaking a Toy Hash Function
- Counting Iterators Lazily
- Unfathomable Bugs #6: Pretend Precision
- My Bug, My Bad #3: Accidentally Attacking WarCraft 3
- Collapsing Types vs Monads (followup)
- Collapsing Futures: Easy to Use, Hard to Represent
- Eventual Exceptions vs Programming in a Minimal Functional Style
- The Mystery of Flunf
- Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation
- Computer Science Blows My Mind
- A visit to Execution Labs in Montréal
- Transmuting Dice, Conserving Entropy
- Rule of Thumb: Ask for the Clock
- Rule of Thumb: Use Purposefully Weakened Methods
- Rule of thumb: Preconditions Should be Checked Explicitly
- Intersecting Linked Lists Faster
- Mouse Path Smoothing for Jack Lumber
- My Bug, My Bad #2: Sunk by Float
- Repeat Yourself Differently
- Grover’s Quantum Search Algorithm
- Followup to Non-Nullable Types vs C#
- Optimizing Just in Time with Expression Trees
- When One-Way Latency Doesn’t Matter
- Determining exactly if/when/where a moving line intersected a moving point
- Emulating Actors in C# with Async/Await
- Making an immutable queue with guaranteed constant time operations
- Improving Checked Exceptions
- Perishable Collections: The Benefits of Removal-by-Lifetime
- Decoupling shared control
- Decoupling inlined UI code
- Linq to Collections: Beyond IEnumerable<T>
- Publish your .Net library as a NuGet package
- When null is not enough: an option type for C#
- Unfathomable Bugs #5: Readonly or not
- Minkowski sums: examples
- My Bug, My Bad #1: Fractal Spheres
- Working around the brittle UI Virtualization in Windows 8
- Encapsulating Angles
- Unfathomable Bugs #4: Keys that aren’t
- How would I even use a monad (in C#)?
- Useful/Interesting Methods #1: Observable.WhenEach
- Unfathomable Bugs #3: Stringing you along
- Anonymous Implementation Classes – A Design Pattern for C#
- Tasks for ActionScript 3 – Improving on Event-Driven Programming
- Minkowski sums and differences
- Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
- Unfathomable Bugs #2: Slashing Out
- Script templates and base classes
- Unity font extraction
- Abusing “Phantom Types” to Encode List Lengths Into Their Type
- Constructive Criticism of the Reactive Extensions API
- Quaternions part 3
- Quaternions part 2
- Quaternions part 1
- Unfathomable Bugs #1: You can have things! You can have things IN things! You can have …
- Coroutines – More than you want to know
- Asset Bundle Helper
- The Visual Studio goes away
- .Net’s time traveling StopWatch
- Introducing Catalyst