Haskell实现广度优先遍历获取树结构所有路径的方法咨询

需要查找树状结构中的所有路径，对应结构如下：

现有深度优先遍历实现 #

已定义如下深度优先遍历（迭代）函数，运行效果正常：

dfIterate:: (a -> [a]) -> a -> [[a]]
dfIterate f a = map (a:) ([] : concatMap (dfIterate f) (f a))

该函数接收种子值a和函数a -> [a]（可从每个a得到多个关联子a），返回从种子节点出发的所有路径列表，测试示例如下：

ghci> let f a = if a == 1 then [2, 3] else if a == 2 then [4] else []
ghci> dfIterate f 1
[[1],[1,2],[1,2,4],[1,3]]

上述dfIterate可正确遍历输出所有路径，其中函数f用于模拟前述树结构。

广度优先遍历需求与尝试 #

现在需要实现对应广度优先遍历函数，要求上述测试用例输出结果为：[[1],[1,2],[1,3],[1,2,4]]。
初次尝试的实现如下，效果不符合预期：

bfIterate :: (a -> [a]) -> [a] -> [[a]]
bfIterate _ [] = [[]]
bfIterate f (a:as) = map (a:) (bfIterate f (as ++ (f a)))

该实现尝试将第二个参数作为队列使用，但逻辑存在问题，无法得到正确结果。

原有实现的问题在于队列仅存储单个节点，无法直接拼接出完整路径，调整为在队列中存储已遍历的完整路径，按层处理队列即可得到符合要求的广度优先全路径列表。

正确实现代码 #

bfIterate :: (a -> [a]) -> a -> [[a]]
bfIterate f root = bfs [[root]]
  where
    bfs [] = []
    bfs (path:paths) = path : bfs (paths ++ nextPaths)
      where
        currentNode = last path
        nextPaths = map (\child -> path ++ [child]) (f currentNode)

测试验证 #

使用你提供的测试用例运行：

ghci> let f a = if a == 1 then [2, 3] else if a == 2 then [4] else []
ghci> bfIterate f 1
[[1],[1,2],[1,3],[1,2,4]]

输出完全符合预期。

实现说明 #

• 队列中存储的是从根节点到对应节点的完整路径，而非单个节点
• 每次取出队列首的路径加入结果集，再生成该路径末端节点所有子节点对应的新路径，追加到队列尾部
• 利用队列先进先出的特性自然实现广度优先的层序遍历，最终得到的结果集就是按层排序的所有路径

内容的提问来源于stack exchange，提问作者cdupont