Using backtracking to undo transactions in Haskell | Hacker News Reader

Using backtracking to undo transactions in Haskell

fpcomplete.com

15 pointsagocorona9 comments

For me, this is the money quote:

The monad instance defines what each kind of computation has to do with these continuations.

A bind has two parameters: a closure and a continuation.

    x >>=(f1>>=(f2 >>=f3))

Serious light-bulb moment. I'm very used to thinking about and leveraging closures in imperative languages, but the above finally connected the idea that I can deliberately build abstractions/DSLs like this in Haskell for purposes such as action history manipulation. Computation as data! Love it!

Many in the Haskell community don't like the "do" syntax because it obscures the fact that you're actually generating a closure per <-. One of the best ways to really get the utility of the various implementations of the monad interface is simply to notice that the typeclass permits an implementation to call the resulting closure as many or as few times at is chooses. The way the "Maybe" implementation of the Monad interface "short-circuits" a computation is that when it encounters a "Nothing", it chooses to call the closure zero times and simply return "Nothing" back up the stack. The way the standard "List" implementation of the Monad implements its cartesian closure behavior is that it takes the closure and calls it once on each element of the list. The "do" notation is superficially easier to read, but it obscures the underlying mechanics.

More complexly, the STM implementation for monad also uses it for backtracking; should something fail it can simply roll back all the function calls it has made and restart. It's not magic, it's a huge, huge pile of closures that the implementing type can use to do all sorts of things.

This is also one of the major reasons why good implementations of the monad typeclass in other languages often end up very painful to use; without some sort of friendly syntax that makes it incredibly easy to generate a new closure, you get a lot of "line noise" as you keep typing function (...) { ... function (...) { ... function (...) { ... function (...) {...

I'm still in the "I use it" camp personally, but I am sympathetic to the idea that you should start by manually writing out the bind calls on manually-written closures, and only go to the "do" syntax when you understand it thoroughly.

Oh, and to set your mind at ease: }}}}.

Many Haskell books and tutorials tell what the "do" really does. People should read more.

In STM the backtracking is a bit different. It has a single backtracking point and usually it is implemented by killing the thread and restarting it anew. That is because doing IO actions is really unsafe under STM. Really it is not implemented in Haskell but in C, at least the last time that I looked at it).

This backtracking is different since it permits different backtracking points. It is possible to implement a more "civilized" version of the STM semantics this way, with more respect for IO actions.

Very glad that you appreciate it. I think that there is a gold mine of applications under this simple realization.

Actually, the gold mine is monad transformer. There aren't many things you can do with monads (and the OP's one is nothing new). The real power is in the combination of monads.

I added the backtracking effect in this article without stacking a new transformer. In a way somewhat similar in which a new interpreter can add a new effect to a free monad.

Do you have seen the monad of the article before? I would like to know your reference, please.

Sorry, i haven't checked in the last days.

I haven't seen exactly the same corresponding monad. But I would compare it with existing backtracking monads used for logic programming. My point is, that a backtracking monad in general is a well known concept. Your special point is the rollback, which isn't included in the monads i saw. I think that people, who worked with backtracking monads, know that they could implement a rollback if needed.

Reply on news.ycombinator.com