A* Monad

Hackage

Caveat Emptor; this hasn't been battle-tested yet; it should work, but make sure to test it out if you're doing anything serious.

Easily do A* searches with use of arbitrary monadic effects!

Basics

• Use <|> or asum (anything using Alternative) to branch into multiple possible choices.
• Use updateCost myCost to set the value of your 'heuristic' function whenever you've done enough work to change your estimate. Remember that A* heuristics should always be pessimistic (e.g. can over-estimate cost, but shouldn't UNDER estimate).
• Every call to updateCost creates a branch; Branches with LOWER costs will run before those with higher costs.
• Call done mySolution to short circuit ALL running branches and immediately return your result.
• AStarT has a built-in State monad which can store branch-local states for you. You can store your current branch's solution-space for instance, or the path you've followed to get to the current solution; or both!

Here's an example of using A* to find a path to a location in a 2 dimensional grid.

-- Track which moves we've made, up, down, left or right
data Move = U | D | L | R
    deriving (Show, Eq)

-- Track our current position, the goal we're moving towards, and the moves we've taken so far.
data Context =
    Context { _currentPos :: (Int, Int)
            , _goal    :: (Int, Int)
            , _moves   :: [Move]
            }
    deriving (Show, Eq)
makeLenses ''Context

-- The Manhattan distance between two points
-- This is our A* heuristic
distanceTo :: (Int, Int) -> (Int, Int) -> Int
distanceTo (x, y) (x', y') = abs (x - x') + abs (y - y')

-- Move around the space looking for the destination point.
findPoint :: AStar Context Int () ()
findPoint = do
    c <- use currentPos
    gl <- use goal
    -- I could return the moves we took, 
    -- but our State is automatically returned when we run AStar
    when (c == gl) $ done ()
    -- We have more work to do, we should update the cost estimate and continue
    updateCost $ distanceTo gl c
    if c == gl 
       then done ()
       else updateCost $ distanceTo gl c
    -- Non-deterministically choose a direction to move, 
    -- store that move in our state, and edit our current position.
    asum
        [ moves <>= [R] >> currentPos . _1 += 1 >> findPoint
        , moves <>= [L] >> currentPos . _1 -= 1 >> findPoint
        , moves <>= [D] >> currentPos . _2 += 1 >> findPoint
        , moves <>= [U] >> currentPos . _2 -= 1 >> findPoint
        ]

-- We only care about the ending state, so we use `execAStar`
-- `runAStarT` is the most powerful and runs a monad-transformer version
-- and returns both the state and result type.
run :: Maybe Context
run = execAStar findPoint
             Context { _current = (5, 5)
                     , _goal    = (7, 4)
                     , _moves   = []
                     }

-- run it to see if we found a solution; it returns the state of the the 'winning' branch.
>>> run 
Just (Context { _current = (7, 4)
              , _goal    = (7, 4)
              , _moves   = [U, R, R]
              })

Known Issues

Currently, computation will hang if the end of a branch "finishes" without calling done or failure; so don't do that.