The Tardis Monad

45 points by isaac21259 4 years ago | 9 comments

People often say state is hard in functional programming, but things like the Tardis monad have convinced me that (semantically speaking) functional programming is even better at state than the imperative/OOP paradigms. Imperative programs are essentially restricted to one global monad implicitly hardcoded into the language semantics, whereas with functional programming you have the freedom to choose the most appropriate monad for the task at hand. You want state? Use the state monad. You want continuations? Use that monad. You want time traveling? Yep, there's a monad for that too. IO, randomness, nondeterminism, parallelism, environment variables, failure, backtracking, software transactional memory, you name it. Many problems are best solved with a custom monad, rather than one of the standard ones; for example, using a monad that allows your code to emit constraints to be solved (this is a common technique for implementing type inference in compilers). Satisfyingly, reifying effects with monads preserves referential transparency and is therefore compatible with laziness, unlike traditional side effects which are sensitive to evaluation order.

mhitza 4 years ago | |

State management, for me, is hard in Haskell because monads are a pain to compose, and transformer stacks types give me a headache (anything that's wrapping over (->) tends to confuse me anyway when composed).

I've been reading about effectful systems that would remove the pain points around transformers all the way back to 2016, or earlier. Yet there still doesn't seem to be any to overtake the library ecosystem.

Of course this is where the "write your own custom monad"/free monad interpreter might come into play in practice.

rssoconnor 4 years ago |

Unbelievably, I actually used this in a project when I found myself thinking that I needed a combination of a forward and backward propagating state monad.

[1] https://github.com/ElementsProject/simplicity/blob/35627fc49...

cwillu 4 years ago |

Time travel is all well and good, but it's not a Tardis if it's not bigger on the inside.

jasonincanada 4 years ago |

I just coded an example usage of this monad last week:

https://github.com/jasonincanada/kattis/blob/master/src/Pivo...

This tests each element of a list to see if it's a pivot, meaning it's between the maximum to the left and the minimum to the right. In a single logical traversal it shouldn't be able to see the minimum yet, since it hasn't visited those elements. With reverse state you pretend you can anyway and let Haskell figure out the dependencies during execution

isaac21259 4 years ago |

Se also: https://tech-blog.capital-match.com/posts/5-the-reverse-stat...

lacrosse_tannin 4 years ago |

what the heck is the reverse state monad

chowells 4 years ago | |

It passes state backwards, so that changes are visible to previous reads. If this sounds like it has problems with causality - it can. You can end up in an infinite loop when a calculation ends up depending on its own result. But sometimes it solves a problem very neatly. Being able to express it is one of the advantages of making evaluation order independent of declaration order.

dmead 4 years ago |

Isnt this just a lens?