# A* Monad

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 **automatically keeps state contiguous in spite of branching**. This means that your state monad will properly switch states when switching branches. Just use state normally, it should work as expected. 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]
})
```