Backtracking, Interleaving, and Terminating Monad Transformers (2005) [pdf] | Hacker News Reader

Backtracking, Interleaving, and Terminating Monad Transformers (2005) [pdf]

okmij.org

71 pointssetra15 comments

These notes explain the logic monad by solving solve n-queens with it: https://github.com/sshastry/queenslogic Despite its name, it's more of a search monad, it doesn't perform unification or anything like that.

Another interesting paper is "Monad transformers for backtracking search" https://arxiv.org/abs/1406.2058

The Select monad described in the later paper can be found in the "transformers" library http://hackage.haskell.org/package/transformers-0.5.4.0/docs...

Oh neat, I didn't know Ross had actually released a version of transformers with Select. Now I've got to go learn it.

I like FP and Haskell, but when I read a paper like this and realize the amount of effort it takes to implement a basic backtracking algorithm, then I wonder if Haskell can ever become mainstream in production environments.

It is the future except that production code will not be written by Humans.

It doesn't take very much effort to implement a back-tracking algorithm, it's exposing it as a monad that takes the time. If you don't need the benefits that gets you, you don't have to do the work either.

And, of course, it's wrapped up in a library anyway, so a lot of the time you won't care.

Do you know of an example of another general backtracking DSL implemented in another language that is significantly easier or more concise?

This is not what my comment is about. You wouldn't normally write a general backtracking DSL in an imperative language because a backtracking algorithm is trivial to write.

Only when you are using a pure functional language it becomes non trivial to combine the results of the individual sub branches.

Perhaps you misunderstand what this is doing? Or perhaps I misunderstand what you mean.

If all you want is to take some kind of search function or backtracking system that generates a stream of results then combining the sub branches is trivial. If you represent a stream as a list and use something like Haskell that is lazy, then all you have to do is literally combine the streams.

myStreamGenerator1 p1 ++ myStreamGenerator2 p2

if you want a different search strategy you can intersperse.

concat . intersperse (mySG1 p1) (mySG2 p2)

the cases being DFS and BFS

With backtracking you typically have some kind of pruning stragegy. That means keeping track of your best result so far and dont go into branches where it is clear that they can never beat your current winner anymore.

So you cannot simply concatenate the results of the subbranches, each new branch needs to be aware of what has been found so far. That can quickly become ugly in pure FP, that's why people have been looking for solutions that do that in an elegant way, e.g. using Monads.

Pruning can be implemented by just not computing a part of a stream based on some predicate.

If you want some kind of global state of the current results then you just pass around the current calculated states. Pure FP has many simple solutions for passing around state.

Would you care to show such a trivial example, and maybe we can see if it can be translated into Haskell?

Your comment is about something that is not this article. This article is about a generic backtracking DSL. Not about writing a recursive function that fails some of the time.

Prolog?

Prolog uses backtracking as the principal control flow paradigm and allows user-defined languages/DSLs by defining tokens, their associativity and precedence in operator-precedence parsing, where tokens are character sequences that are either all graphic characters or all letters/digits.

Example from the book Adventures in Prolog as returned by a cursory Google search:

    ? op(35, xfx, is_in)
    
    banana is_in room(kitchen).

There's always the classic from 1988, which completely blew my mind when I came across it a couple of years later:

"Building a backtracking facility in smalltalk without kernel support"[1]

Languages like Snobol, Prolog, and Icon were designed with backtracking facilities from the outset and these facilities are deeply intertwined with the implementation. Retrofitting a backtracking facility in a language that wasn't designed for it has never been achieved. We report on an experiment to retrofit Smalltalk with a backtracking facility. The facility is provided through a small number of primitives written in the language (no modifications to the kernel were made). The ability to do this is a direct result of the power provided by the objectification of contexts.

I'll leave the qualitative analysis of which is easier or more concise to others.

[1] http://dl.acm.org/citation.cfm?doid=62084.62094&CFID=7393283...

You wouldn't implement this in production, you would use a library - just like 90% of everything else you do in production. This paper is packaged up here https://hackage.haskell.org/package/logict

Reply on news.ycombinator.com