그래프 0–1, 0–2, 1–3, 1–4, 2–5 에서 0 부터 깊이 우선으로 돌면, 1 로 내려가 3, 4 를 끝까지 본 뒤 돌아와 2, 5 를 본다 — 0, 1, 3, 4, 2, 5. 재귀로 쓰면 콜 스택이 돌아올 자리를 기억하고, 명시적 스택으로 쓰면 이웃을 거꾸로 넣어 첫 이웃이 먼저 나오게 한다. 이미 방문한 노드는 건너뛴다.

-- 깊이 우선: 한 갈래를 끝까지 내려간 뒤 돌아온다
dfs :: Graph -> Node -> [Node]
dfs g start = go [start] []
  where
    go []       seen = reverse seen
    go (n : st) seen
      | n `elem` seen = go st seen
      | otherwise     = go (g ! n ++ st) (n : seen)   -- 이웃을 앞에: 첫 이웃이 먼저 (JS 스택은 reverse 후 push)
-- 재귀로 쓰면 돌아올 자리를 콜 스택이 기억한다

graph = fromList [(0, [1, 2]), (1, [0, 3, 4]), (2, [0, 5]), (3, [1]), (4, [1]), (5, [2])]
dfs graph 0 == [0, 1, 3, 4, 2, 5]
#344

노드마다 child(첫 자식), sibling(다음 형제), return(부모) 세 링크가 걸려 있다. App 의 child 는 Header, Header 의 sibling 은 Main, Main 의 child 는 List, 각자의 return 은 부모다. 규칙은 넷: child 가 있으면 내려가고, root 에 도달하면 끝내고, sibling 이 없으면 return 으로 올라가며 반복하고, sibling 이 있으면 옆으로 간다. 내려가는 길이 beginWork, 올라오는 길이 completeWork 라 한 노드를 두 번 지난다. 순서: begin App → begin Header → complete Header → begin Main → begin List → complete List → complete Main → complete App.

-- Fiber 가 렌더링을 쪼갤 수 있는 이유: 진행 상태가 콜 스택이 아니라 포인터 하나다
data Fiber = Fiber { child, sibling, return :: Maybe Fiber }

-- 재귀: 어디까지 했는지가 콜 스택 프레임(App → Main → List)에 있다
-- 양보하려고 빠져나오면 프레임이 풀려나가고, 스택 위 모두가 중단을 알아야 한다
-- 원문은 스택을 다시 쌓는 비용은 "not too bad" 라 하고, 진짜 문제를 이 중단 쪽으로 든다
walk f = beginWork f >> mapM_ walk (children f) >> completeWork f

-- 세 포인터: 한 걸음 = 다음 workInProgress. 멈추면 이 값 하나만 남고, 거기서 다시 시작한다
next :: Fiber -> Maybe Fiber
next f = child f <|> up f                                  -- 내려간다 (beginWork)

up :: Fiber -> Maybe Fiber
up f | isRoot f  = Nothing                                 -- 끝
     | otherwise = sibling f <|> (return f >>= up)         -- 옆으로, 없으면 올라간다 (completeWork)

-- App{Header, Main{List}}: 한 노드를 두 번 지난다
-- begin App → begin Header → complete Header → begin Main → begin List
--   → complete List → complete Main → complete App
-- 원문도 Fiber 사정이라 못박는다 — "apply to Fiber, but not necessarily anything else"
#560