5 ms·

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

71 points by setra 10y ago

danidiaz 10y ago
These notes explain the logic monad by solving solve n-queens with it: https://github.com/sshastry/queenslogic 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 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/Control-Monad-Trans-Select.html http://hackage.haskell.org/package/transformers-0.5.4.0/docs...
- ocharles 10y ago
  Oh neat, I didn't know Ross had actually released a version of transformers with Select. Now I've got to go learn it.
misja111 10y ago
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.
- deleted 10y ago
  [deleted]
- eternalban 10y ago
  It is the future except that production code will not be written by Humans.
  - deleted 10y ago
    [deleted]
- moomin 10y ago
  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.
- mbrock 10y ago
  Do you know of an example of another general backtracking DSL implemented in another language that is significantly easier or more concise?
  - misja111 10y ago
    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.
    - setra 10y ago
      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
      - misja111 10y ago
        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.
        setra 10y ago
        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.
- ocharles 10y ago
  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 https://hackage.haskell.org/package/logict

71 points by setra 10y ago

These notes explain the logic monad by solving solve n-queens with it: https://github.com/sshastry/queenslogic 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 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/Control-Monad-Trans-Select.html http://hackage.haskell.org/package/transformers-0.5.4.0/docs...

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

misja111 10y ago

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.

deleted 10y ago
[deleted]
eternalban 10y ago
It is the future except that production code will not be written by Humans.
- deleted 10y ago
  [deleted]
moomin 10y ago
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.
mbrock 10y ago
Do you know of an example of another general backtracking DSL implemented in another language that is significantly easier or more concise?
- misja111 10y ago
  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.
  - setra 10y ago
    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
    - misja111 10y ago
      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.
      - setra 10y ago
        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.
ocharles 10y ago
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 https://hackage.haskell.org/package/logict