search-algorithms
Common graph search algorithms
https://github.com/devonhollowood/search-algorithms#readme
LTS Haskell 22.37: | 0.3.2 |
Stackage Nightly 2024-10-07: | 0.3.2 |
Latest on Hackage: | 0.3.2 |
search-algorithms-0.3.2@sha256:9d224b9c6b5875598e6fc91497a178f3ca6e45768c637d07d4f874e6211a331b,2203
Module documentation for 0.3.2
- Algorithm
search-algorithms
Haskell library containing common graph search algorithms
Lots of problems can be modeled as graphs, but oftentimes one doesn’t want to use an explicit graph structure to represent the problem. Maybe the graph would be too big (or is infinite), maybe making an explicit graph is unwieldy for the problem at hand, or maybe one just wants to generalize over graph implementations. That’s where this library comes in: this is a collection of generalized search algorithms, so that one doesn’t have to make the graphs explicit. In general, this means that one provides each search function with a function to generate neighboring states, possibly some functions to generate additional information for the search, a predicate which tells when the search is complete, and an initial state to start from. The result is a path from the initial state to a “solved” state, or Nothing
if no such path is possible.
Documentation
Documentation is hosted on Hackage.
Acknowledgements
This library shares a similar functionality with the astar library (which I was unaware of when I released the first version of this library). astar
‘s interface has since influenced the development of this library’s interface, and this library owes a debt of gratitude to astar
for that reason.
Examples
Change-making problem
import Algorithm.Search (bfs)
countChange target = bfs (add_one_coin `pruning` (> target)) (== target) 0
where
add_one_coin amt = map (+ amt) coins
coins = [1, 5, 10, 25]
-- countChange gives the subtotals along the way to the end:
-- >>> countChange 67
-- Just [1, 2, 7, 17, 42, 67]
Simple directed acyclic graph:
import Algorithm.Search (dfs)
import qualified Data.Map as Map
graph = Map.fromList [
(1, [2, 3]),
(2, [4]),
(3, [4]),
(4, [])
]
-- Run dfs on the graph:
-- >>> dfs (graph Map.!) (== 4) 1
-- Just [3,4]
Using A* to find a path in an area with a wall:
import Algorithm.Search (aStar)
taxicabNeighbors :: (Int, Int) -> [(Int, Int)]
taxicabNeighbors (x, y) = [(x, y + 1), (x - 1, y), (x + 1, y), (x, y - 1)]
isWall :: (Int, Int) -> Bool
isWall (x, y) = x == 1 && (-2) <= y && y <= 1
taxicabDistance :: (Int, Int) -> (Int, Int) -> Int
taxicabDistance (x1, y1) (x2, y2) = abs (x2 - x1) + abs (y2 - y1)
findPath :: (Int, Int) -> (Int, Int) -> Maybe (Int, [(Int, (Int, Int))])
findPath start end =
let next = taxicabNeighbors
cost = taxicabDistance
remaining = (taxicabDistance end)
in aStar (next `pruning` isWall) cost remaining (== end) start
-- findPath p1 p2 finds a path between p1 and p2, avoiding the wall
-- >>> findPath (0, 0) (2, 0)
-- Just (6,[(0,1),(0,2),(1,2),(2,2),(2,1),(2,0)])
--
-- This correctly goes up and around the wall
Changes
Changelog
All notable changes to this project will be documented in this file.
The format is based on Keep a Changelog and this project adheres to Semantic Versioning.
0.3.2 - 2021-12-27
- Add two new functions,
dijkstraAssoc
andaStarAssoc
. These allow for the simultaneous computation of neighboring states and their costs. (Thank you to nagydani)
0.3.1 - 2010-08-19
- Dependencies version bump
0.3.0 - 2017-11-29
Added
- Monadic versions of search algorithms and helper functions
0.2.0 - 2017-05-13
Changed
- BREAKING CHANGE: Simplified return type of
dijkstra
andaStar
.- This should make these functions more ergonomic.
- Introduced new
incrementalCosts
function to compensate.
- BREAKING CHANGE: Replaced searches’
prunes
arguments withpruning
combinator. - BREAKING CHANGE: Split searches’
next
arguments into multiple arguments fordijkstra
andaStar
.- This should make these functions more ergonomic.
next
arguments now only require a way of generatingFoldable
s, instead of lists specifically.
0.1.0 - 2017-03-07
- Initial release