如何将Haskell中的深度优先搜索（DFS）函数改为惰性求值？

我参考了一个迭代DFS算法，将其转换为Haskell代码，该代码返回前序访问的节点顺序，等价于常规访问函数。但存在性能问题：必须等待生成完整的访问顺序才能实际进行节点访问。我希望通过惰性化操作解决该问题，但不知如何实现。

请告诉我如何将以下Haskell函数dfs_prae改造为惰性求值，使我仅需计算标记列表中节点对应的搜索部分即可获取访问列表：

dfs_prae :: Eq e => Graph e -> e -> [e]
dfs_prae graph jetzige = innerDfs jetzige []
    where
        innerDfs :: e -> [e] -> [e]
        innerDfs jetzige jetzigeGemarkte = schleife [jetzige] jetzigeGemarkte []
        
        schleife :: [e] -> [e] -> [e] -> [e]
        schleife []                  _       visited = visited
        schleife xs gemarkt visited = schleife jetzigStack jetzigGemarkt jetzigVisited
            where
                jetzigVisited = if not (jetzige `elem` visited) then visited ++ [jetzige] else visited
                jetzigStack = if not (jetzige `elem` gemarkt) then foldr (:) stackTail wandernbarNachbaren else stackTail
                jetzigGemarkt = jetzige:gemarkt
                wandernbarNachbaren =  nachbarschaftBekommen jetzige jetzigGemarkt
                jetzige = head xs
                stackTail = tail xs

        nachbarschaftBekommen :: e -> [e] -> [e]
        nachbarschaftBekommen jetzige marked = filter (not . (\x -> elem x marked)) (nachbaren graph jetzige)

当前实现的性能瓶颈在于两点：一是visited ++ [jetzige]的列表拼接操作是O(n)复杂度，且会强制生成完整列表后才能返回结果；二是尾递归的schleife函数结构天然难以惰性生成结果，必须遍历到终点才会构建完整列表。

要实现惰性的前序DFS，我们可以直接利用Haskell列表的惰性特性，将访问节点的操作作为列表头部立即返回，递归处理剩余节点作为列表尾部，同时用高效的集合替代列表存储已标记节点，避免重复访问。

改造后的代码 #

import Data.Set (Set)
import qualified Data.Set as Set

-- 假设Graph类型定义为节点到邻居的映射，若你的Graph结构不同，只需调整邻居获取逻辑即可
type Graph e = e -> [e]

dfs_prae_lazy :: Ord e => Graph e -> e -> [e]
dfs_prae_lazy graph start = dfsHelper (Set.singleton start) [start]
    where
        dfsHelper :: Set e -> [e] -> [e]
        dfsHelper _ [] = []
        dfsHelper marked (node:rest) = 
            node : dfsHelper newMarked (unvisitedNeighbors ++ rest)
            where
                -- 获取当前节点的所有未访问邻居
                neighbors = graph node
                unvisitedNeighbors = filter (`Set.notMember` marked) neighbors
                -- 更新已标记节点集合
                newMarked = Set.union marked (Set.fromList unvisitedNeighbors)

关键改进点 #

• 用Set替代列表存储已标记节点：Set.notMember是O(log n)复杂度，远优于原代码中elem的O(n)，同时避免重复访问节点。
• 惰性列表构建：直接将当前访问的node作为列表头部返回，递归处理邻居和栈剩余元素作为尾部——Haskell会在需要时才计算后续元素，无需等待整个遍历完成。
• 去掉尾递归结构：改用“头部+递归尾部”的方式，天然适配惰性求值，每访问一个节点就立即输出，无需积累完整结果。
• 保持DFS顺序：将未访问邻居追加到栈的头部，若需要和原迭代版完全一致的顺序，可将unvisitedNeighbors反转后再拼接，即reverse unvisitedNeighbors ++ rest，具体取决于原邻居的返回顺序。

惰性效果验证 #

你可以通过取列表前缀验证惰性特性，比如构造一个无限链式图：

-- 链式图：1 -> 2 -> 3 -> 4 -> ...
chainGraph :: Int -> [Int]
chainGraph n = [n+1]

-- 仅获取前3个访问节点，无需遍历整个无限链
take 3 (dfs_prae_lazy chainGraph 1)  -- 输出 [1,2,3]

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