Haskell中cons运算符':'及DFS递归map调用的类型错误问题

Hey Adam, let's dig into this DFS maze problem you're stuck on—it sounds like a classic type mismatch and logic mix-up with your recursive map call. Let's break it down step by step.

首先明确问题核心 #

From your error stack and code snippet, the key issue is two-fold:

1. Type mismatch: You're passing (curr : trail) where a single Pos is expected, or you've mixed up the structure of your Path type with a list of paths.
2. Misused map for DFS logic: map will apply your DFS function to all adjacent cells and return a list of results, but standard DFS needs to try cells one by one until it finds a valid path.

先理清类型定义（基于你的代码上下文） #

Let's assume these standard type definitions to align with your code:

• type Pos = (Int, Int) (your cell coordinates)
• type Path = [Pos] (a sequence of cells from start to current position)
• trail is your current Path, and curr is the current Pos you're exploring.

错误代码的问题拆解 #

Your line dfs maze (curr : trail) curr 'map' (adj c (fst curr) (snd curr) prev) has two critical issues:

• You're passing the original curr as the current position parameter for every recursive call, but you should be passing each adjacent cell from adj as the new current position.
• You're treating map like a control flow operator, but it's a list transformer. map expects a function (not a function call) as its first argument, followed by the list to apply it to.

修正后的DFS实现示例 #

Here's a corrected version that fixes both issues, using either a recursive list traversal (for finding a single path) or map (for collecting all possible paths):

1. 找单个有效路径（标准DFS） #

This version tries adjacent cells one by one until it finds a path to the target:

type Pos = (Int, Int)
type Path = [Pos]
type Maze = [[Bool]] -- 示例迷宫类型：True表示可通行，False表示墙

dfs :: Maze -> Pos -> Pos -> Path -> Maybe Path
dfs maze start target visited =
  if start == target
    then Just (reverse visited) -- 反转得到从起点到终点的正序路径
    else let
           -- 获取当前位置的所有相邻坐标
           (x, y) = start
           adjacent = [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]
           -- 过滤出迷宫范围内、可通行且未访问的单元格
           validAdjacent = filter (\(nx, ny) -> 
               nx >=0 && nx < length maze && ny >=0 && ny < length (head maze)
               && maze !! nx !! ny
               && (nx, ny) `notElem` visited) adjacent
         in
           case validAdjacent of
             [] -> Nothing -- 没有未访问的邻居，回溯
             (next:rest) ->
               -- 先尝试第一个邻居
               case dfs maze next target (start : visited) of
                 Just path -> Just path -- 找到路径，直接返回
                 Nothing -> dfs maze start target visited -- 第一个邻居没找到，尝试下一个

2. 收集所有可能路径（用map） #

If you want to collect all valid paths instead of just one, use concatMap to flatten the list of paths:

dfsAllPaths :: Maze -> Pos -> Pos -> Path -> [Path]
dfsAllPaths maze start target visited =
  if start == target
    then [reverse visited]
    else let
           (x, y) = start
           adjacent = [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]
           validAdjacent = filter (\(nx, ny) -> 
               nx >=0 && nx < length maze && ny >=0 && ny < length (head maze)
               && maze !! nx !! ny
               && (nx, ny) `notElem` visited) adjacent
         in
           concatMap (\next -> dfsAllPaths maze next target (start : visited)) validAdjacent

关键修正点 #

• Pass the right current position: For each recursive call, use the adjacent cell (next) as the new start position, not the original curr.
• Fix map usage: When collecting all paths, pass a lambda function to map that takes each adjacent cell and calls DFS with it.
• Track visited cells: Since your maze is acyclic and undirected, you still need to track visited cells to avoid backtracking immediately to the previous cell.

验证错误来源 #

The error you saw about (curr : trail) being [Path] instead of Path likely came from accidentally defining trail as a list of paths ([Path]) instead of a single path (Path). Double-check your type definitions to ensure trail is [Pos] (a single path).

内容的提问来源于stack exchange，提问作者Adam M.