Examples of a monad whose Applicative part can be better optimized than the Monad part

Another example is a strict left fold. You can write an applicative instance which allows you to compose folds so that the resulting fold can be performed on the data in a single pass and constant space. However, the monad instance needs to re-iterate from the beginning of the data for each bind and keep … Read more

Constructing efficient monad instances on `Set` (and other containers with constraints) using the continuation monad

Monads are one particular way of structuring and sequencing computations. The bind of a monad cannot magically restructure your computation so as to happen in a more efficient way. There are two problems with the way you structure your computation. When evaluating stepN 20 0, the result of step 0 will be computed 20 times. … Read more

Can a `ST`-like monad be executed purely (without the `ST` library)?

tl;dr: It’s not possible without adjustments to the definition of PT. Here’s the core problem: you’ll be running your stateful computation in the context of some sort of storage medium, but said storage medium has to know how to store arbitrary types. This isn’t possible without packaging up some sort of evidence into the MkRef … Read more

Why can Haskell exceptions only be caught inside the IO monad?

One of the reasons is the denotational semantics of Haskell. One of the neat properties of (pure) Haskell functions is their monotonicity — more defined argument yields more defined value. This property is very important e.g. to reason about recursive functions (read the article to understand why). Denotation of exception by definition is the bottom, … Read more

What is the difference between a Functor and a Monad?

Let me explain my understanding without going into category theory: Functors and monads both provide some tool to wrapped input, returning a wrapped output. Functor = unit + map (i.e. the tool) where, unit = something which takes raw input and wraps it inside a small context. map = the tool which takes a function … Read more