How to functionally generate a tree breadth-first. (With Haskell)
- by Dennetik
Say I have the following Haskell tree type, where "State" is a simple wrapper:
data Tree a = Branch (State a) [Tree a]
| Leaf (State a)
deriving (Eq, Show)
I also have a function "expand :: Tree a - Tree a" which takes a leaf node,
and expands it into a branch, or takes a branch and returns it unaltered. This tree type represents an N-ary search-tree.
Searching depth-first is a waste, as the search-space is obviously infinite, as I can easily keep on expanding the search-space with the use of expand on all the tree's leaf nodes, and the chances of accidentally missing the goal-state is huge... thus the only solution is a breadth-first search, implemented pretty decent over here, which will find the solution if it's there.
What I want to generate, though, is the tree traversed up to finding the solution.
This is a problem because I only know how to do this depth-first, which could be done by simply called the "expand" function again and again upon the first child node... until a goal-state is found. (This would really not generate anything other then a really uncomfortable list.)
Could anyone give me any hints on how to do this (or an entire algorithm), or a verdict on whether or not it's possible with a decent complexity? (Or any sources on this, because I found rather few.)
