I’m probably reinventing the wheel here, but I haven’t come across this elsewhere.
I came across an idea whilst working on Traces, unbounded graphs (I could say infinite, but I am something of a constructionist).
An unbounded graph is a graph defined by a function
adjacentNodes :: a -> [a]
The function adjacentNodes could for example create every possible legal game move from the current position, run every possible lsystem rule on the string or find all legal one step permutations of Trace (some of these generate Trees but the method I am applying here is fairly universal). There is also scope for creating strings out of grammars in general.
So lets say you want to find out a property of your graph. Whether in a Trace a certain substring can occur, for example. Or whether there is a strategy to guarantee a win in a small game.
To generate every node in the unbounded graph you just generate a list of those nodes and append a list of those nodes with iterate applied recursively. Warning unbounded lists created! Also code not thoroughly tested.
> import Data.List as List > import Data.Set as Set > import Data.Monoid > gIterate :: (a -> [a]) -> a -> [a] > gIterate nextNodes start = nextList ++ (List.concat $ List.map (gIterate (nextNodes)) nextList) > where nextList = nextNodes start
You can get back to iterate simply by doing
take 10 (mIterate (\a -> [a]) '!')
iterate is just creating a unbounded graph where there is only one possible adjacent node! Now iterating through a graph with mulitple options is a bot more interesting then the flat graphs done by iterate. So you might choose to ignore some edges, for example those you have visited before.
> gIterateNoCycles :: (Ord a, Eq a) => (a -> [a]) -> Set a -> a -> [a] > gIterateNoCycles nextNodes visited start = nextList ++ (List.concat $ List.map (gIterateNoCycles (nextNodes) visited') nextList) > where nextList = List.filter (\a -> member a visited) $ nextNodes start > visited' = Set.insert start visited
Or those that fail some predicate, a heuristic or the end of the game.
> gFilteredIterate :: (Ord a, Eq a) => (a -> [a]) -> (a -> Bool) -> a -> [a] > gFilteredIterate nextNodes filt start = nextList ++ (List.concat $ List.map (gFilteredIterate (nextNodes) filt) nextList) > where nextList = List.filter (filt) $ nextNodes start >
However all this (++) is not always ideal, lets generalise it somewhat.
> gfoldMap :: Monoid b => (a -> [a]) -> (a -> b) -> a -> b
> gfoldMap nextNodes transform start = mconcat (List.map (transform) (nextList)) `mappend` (mconcat $ List.map (gfoldMap (nextNodes) (transform)) nextList)
> where nextList = nextNodes start
This allows you to use the Any monoid if you just want to find if one of the Nodes satisfies a predicate, or the First monoid to look for one value. However it does mean that you can no longer specify how far to search with the (take n) trick, unless you specify transform to be something that returns a list. So you would probably want to use one of the variants above, or specify a number to go with it.
