그래프 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

이벤트를 시작 시각 순으로 보며, 이미 끝난 레인 중 가장 낮은 것에 넣고, 없으면 레인을 하나 늘린다. 이렇게 하면 레인 수가 동시에 겹치는 최대 개수와 같아진다(구간 그래프의 탐욕 색칠). 겹치는 것끼리 묶은 그룹마다 레인 수를 세어 너비를 100% ÷ 레인 수, 위치를 레인 ÷ 레인 수로 둔다. 예: A 9–11, B 10–12, C 11–13 이면 A·C 가 레인 0, B 가 레인 1 이고 레인은 둘이다. D 14–15 는 새 그룹이라 혼자 전체 폭이다.

-- 겹치는 이벤트를 나란히 놓는다: 시작 순으로, 비어 있는 가장 낮은 레인에
assign :: [Event] -> [(Event, Lane)]
assign = go [] . sortOn (\e -> (start e, end e))
  where
    go _     []       = []
    go lanes (e : es) = (e, l) : go (set l (end e) lanes) es
      where l = fromMaybe (length lanes) (findIndex (<= start e) lanes)   -- 끝난 레인 중 가장 낮은 것
-- 레인 수 = 동시에 겹치는 최대 개수 (구간 그래프의 탐욕 색칠) — 가능한 한 적은 레인으로 모두 덮는 최적해다

-- 겹치는 것끼리 그룹으로 묶어 그룹마다 total 을 센다
groups :: [Event] -> [[Event]]   -- 다음 시작 < 그룹의 최대 끝이면 같은 그룹
style (lane, total) = { left = lane / total * 100%, width = 100% / total }

assign [A 9 11, B 10 12, C 11 13] == [(A, 0), (B, 1), (C, 0)]   -- total 2
#510

노드마다 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