相关疑难解决方法(0)

Data.Tree包括unfoldTreeM_BF和unfoldForestM_BF使用monadic动作的结果构造树广度优先的功能.可以使用forest unfolder轻松编写树展开文件,因此我将重点关注后者:

unfoldForestM_BF :: Monad m =>
             (b -> m (a, [b])) -> [b] -> m [Tree a]

从种子列表开始,它为每个种子应用一个函数,生成将产生树根的动作和用于下一级展开的种子.所使用的算法是稍微严格,因此,使用unfoldForestM_BF与该Identity单子是不完全一样使用纯unfoldForest.我一直试图弄清楚是否有办法让它变得懒惰而不牺牲它的O(n)时间限制.如果(正如Edward Kmett向我建议的那样)这是不可能的,我想知道是否有可能采用更具约束力的类型,特别是需要MonadFix而不是Monad.这个概念将(以某种方式)设置指向未来计算结果的指针,同时将这些计算添加到待办事项列表中,因此如果它们在早期计算的效果中是惰性的,则它们将立即可用.

最近,我已经从Stackoverflow中的Graph中提出了构建DFS树的问题,并且已经了解到可以使用State Monad简单地实现它.

在haskell的DFS

虽然DFS要求仅跟踪被访问节点,因此我们可以使用"Set"或"List"或某种线性数据结构来跟踪被访问节点,BFS需要完成"被访问节点"和"队列"数据结构.

我的BFS伪代码是

Q = empty queue
T = empty Tree
mark all nodes except u as unvisited
while Q is nonempty do
u = deq(Q)
    for each vertex v ? Adj(u)
        if v is not visited 
        then add edge (u,v) to T
             Mark v as visited and enq(v)

从伪代码可以推断,我们每次迭代只需要做3个进程.

1. 从队列中出列点
2. 将点的所有未访问的邻居添加到当前树的子节点,队列和"已访问"列表
3. 在队列中重复此操作

由于我们没有使用递归遍历进行BFS搜索,我们需要一些其他的遍历方法,例如while循环.我在hackage中查找了loop-while包,但似乎有点弃用了.

我假设我需要这样的代码:

{-...-}
... =   evalState (bfs) ((Set.singleton start),[start])
where 
    neighbors x = Map.findWithDefault [] x adj 
    bfs =do (vis,x:queue)<-get
             map (\neighbor ->
                  if (Set.member …

data Tree a b = Leaf a | Branch b [Tree a b]

给定一对函数f :: a -> a'，g :: b -> b'我可以轻松地将 aTree a b转换为 a Tree a' b'。

type Transform a b = a -> b
treeTransform :: Transform leaf leaf' ->
                 Transform branch branch' ->
                 Tree leaf branch ->
                 Tree leaf' branch'
treeTransform f _ (Leaf a) = Leaf (f a)
treeTransform f g (Branch b ts) = Branch (g b) …