-- 깊이 우선: 한 갈래를 끝까지 내려간 뒤 돌아온다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]
-- 겹치는 이벤트를 나란히 놓는다: 시작 순으로, 비어 있는 가장 낮은 레인에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
-- 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 Fibernext f = child f <|> up f -- 내려간다 (beginWork)up :: Fiber -> Maybe Fiberup 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"