Вот шаблон, который я использовал бесчисленное количество раз на разных языках программирования:
- Встречайте проблему, которая легко сводится к некоторому алгоритму графа.
- Определить функцию смежности:
outEdges :: MyNode -> [MyNode]. - Кодирует некоторый общий вид упомянутого алгоритма графа, который принимает эту функцию в качестве своего первого аргумента.
В качестве примера рассмотрим этот (целенаправленный неэффективный) метод вычисления расстояния редактирования между двумя словами. Мы посчитаем наименьшее количество вставок и исключений, необходимых для преобразования одного слова в другое с помощью первого поиска по ширине.
import Data.List
import Data.Maybe
alphabet :: String
alphabet = ['a'..'z']
wordNeighbors :: String -> [String]
wordNeighbors word = deletions ++ insertions where
insertions = [pre++[c]++suf | (pre,suf) <- splits, c <- alphabet]
deletions = [pre++suf | (pre,_:suf) <- take (length word) splits]
splits = zip (inits word) (tails word)
shortestDistance :: (Eq a,Hashable a)=> (a -> [a]) -> a -> a -> Maybe Int
shortestDistance edgeFunc source target =
-- 8 lines of code where I do a breadth-first traversal,
-- using a HashSet to track previously visited nodes;
-- yawn...
editDistance :: String -> String -> Int
editDistance a b = fromJust $ shortestDistance wordNeighbors a b
main = print $ editDistance "cat" "can" -- prints 2
Проблема в том, что Мне ужасно надоедает шаг 3. (см. shortestDistance выше...)
Мне кажется, что я написал эти же алгоритмы сотни раз. Мне бы это понравилось, если бы я мог вместо этого как-то использовать FGL или Data.Graph и покончить с этим, но, насколько я могу судить, в конечном итоге требуется построение какой-то структуры данных Graph, строгой по отношению к набор всех узлов. Это проблема, потому что во многих проблемах график бесконечен (например, в примере выше).
Я специально спрашиваю о Haskell, потому что у Haskell такой сильный фокус на комбинаторах, что я как-то ожидал, что многие из этих алгоритмов уже существуют где-то.
Добавление: Вот другие примеры функций, которые я часто пишу, помимо кратчайшего пути:
-- Useful for organizing the computation of a recursively-defined
-- property of the nodes in an acyclic graph, such as nimbers.
dfsPostOrder :: (v -> [v]) -> v -> [v]
dfsPostOrder adjFunc root = ...
-- Find all nodes connected in some manner to the root node.
-- In case I know the components are finite size, but am not sure
-- of a nice way to express their contents.
-- (Note: The API below is only good for undirected graphs)
getComponent :: (v -> [v]) -> v -> Set v
getComponent adjFunc root = ...
-- Lazily organize the graph into groups by their minimum distance
-- to any of the nodes in @[email protected]
-- One could use this to help incrementalize parts of e.g. a Game
-- of Life or Kinetic Monte Carlo simulation by locating regions
-- invalidated by changes in the state.
groupsByProximity :: (v -> [v]) -> Set v -> [Set v]
groupsByProximity adjFunc roots = ...
TL; DR: Есть ли какой-либо общий способ написания алгоритмов, которые работают с потенциально бесконечными, потенциально циклическими, ориентированными графами, такими как функция, определенная функцией смежности (Node -> [Node] или Node -> [(Node, Weight)])?
