--- title: "Monus와 힙 — 차이만 저장하면 됨이라는 대수적 통찰" published: 2026-03-18T23:55:42.000Z canonical: https://jeff.news/article/691 --- # Monus와 힙 — 차이만 저장하면 됨이라는 대수적 통찰 Monus(부분 뺄셈을 지원하는 모노이드)를 이용해 pairing heap을 구현하는 아이디어를 설명한 Haskell 포스트. 핵심 통찰은 '절댓값 대신 부모와의 차이를 저장하라'는 것으로, 이를 통해 힙 불변식을 타입 수준에서 강제하고 전체 가중치 수정을 O(1)로 만들 수 있음. 이 패턴을 Phases 어플리케이티브, 안정 정렬을 위한 Key monus, 모나딕 힙으로까지 확장함. ## Monus가 뭔지부터 Monus는 **부분 뺄셈을 지원하는 모노이드**임. 정확히는 순서가 붙은 모노이드(ordered monoid)인데, 그 순서가 모노이드 연산 자체로 정의됨: ``` x ≤ y ⟺ ∃z. y = x • z ``` "x가 y보다 작거나 같다"는 말은 "x와 y 사이의 간격 z가 존재한다"는 뜻임. 즉, 그 간격이 반드시 원소로서 실재해야 함. 왜 그룹(group)은 안 되냐면 — 정수 `(ℤ, +, 0)` 같은 그룹에서는 음수가 있어서 어떤 x, y에 대해서도 항상 z를 찾을 수 있음. 그러면 순서가 흐릿해짐. Monus는 자연수 `(ℕ, +, 0)` 같은 **양의 모노이드**에서 자연스럽게 나타남. 이진 뺄셈 연산 `∸`은 다음처럼 파생됨: ``` x ∸ y = z (y ≤ x이고 x = y • z인 경우) 0 (그 외) ``` ## 힙과의 연결 고리 힙 성질은 이것임: 모든 부모 노드의 가중치 ≤ 자식 노드의 가중치. 보통 구현은 각 노드에 **절댓값(absolute weight)** 을 저장함. 그런데 모노이드 구조가 있는 가중치를 쓸 때는 다른 관점이 가능함. 힙 성질 자체가 "자식 가중치 = 부모 가중치 + 어떤 차이" 를 보장하니까, 자식 노드엔 절댓값 대신 **부모와의 차이(difference)만 저장해도 됨**. 이 방식의 장점 두 가지: 1. **타입 수준에서 힙 성질 위반 불가** — 잘못된 트리를 아예 표현할 수 없음 2. **전체 가중치 일괄 변경이 O(1)** — 루트 노드 하나만 바꾸면 트리 전체에 반영됨 ## Haskell 구현 — Pairing Heap with Monus 저자는 `Monus` 타입클래스를 정의하고 pairing heap을 구현함. Pairing heap을 선택한 이유는 구현이 단순하면서도 성능이 좋기 때문임 (포인터 기반 힙 중 실험적으로 가장 빠른 편). 핵심은 두 힙을 합칠 때 키 비교 후 자식의 키를 `yk ∸ xk` 로 저장하는 것. 절댓값이 아닌 부모와의 차이를 저장함으로써 힙 성질이 구조적으로 강제됨. `popMin`에서도 이 구조가 빛남 — 루트를 꺼낼 때, 나머지 서브힙들 전체에 루트 가중치를 "더해줘야" 하는데, 차이만 저장하는 방식 덕분에 루트에만 더하면 됨 → O(1). ### Max와 Last Monus — 일반 Ord 힙 복원 Monus가 없는 일반 키로도 쓰고 싶을 때는 `Max`나 `Last` 세미그룹 래퍼로 해결함. 이 둘은 퇴화(degenerate)해 보이지만 Monus 법칙을 만족함. `Last`는 불필요한 비교를 줄여서 더 효율적임. ## Phases — 자유 대수적 페어링 힙 `Phases` 어플리케이티브(Easterly 2019)는 효과(effect)들을 키 기준으로 재정렬하는 어플리케이티브 트랜스포머임. 원래는 정수 단계(integer phases)만 지원했는데, 저자는 이를 **임의의 전순서 키**로 일반화함. 구조는 pairing heap을 그대로 응용하되, 각 노드에 순수 값 대신 **효과적 계산(effectful computation)** 을 담음. 실행하면 키 순서대로 효과가 발생하고, 순수 값의 원래 구조는 보존됨. ## 안정적 정렬을 위한 Key Monus 문제: pairing heap 기반 정렬은 **불안정(unstable)** 함. 같은 키를 가진 효과들의 순서가 보장되지 않음 → 어플리케이티브 법칙 위반. 해결책: `Key k` = `(k, Int)` 형태의 새 Monus. 키가 같을 경우 원래 위치의 오프셋으로 타이브레이킹함. 중요한 점은 이 오프셋이 **완전히 로컬** 하다는 것 — 전체 시퀀스를 한 번 훑어서 인덱스를 붙이는 게 아니라, 각 노드가 자신과 이웃 간의 상대적 차이만 알면 됨. 차이를 저장하는 패턴이 여기서도 그대로 적용됨. 힙 크기를 추적해서 오프셋을 부여하고, 차이 저장 덕분에 O(1)로 전체 오프셋 조정 가능. ## 모나딕 힙 — Free Monad Transformer 저자의 2021년 논문에서 나온 `Search` 타입은 free monad transformer 기반의 모나딕 힙임. list 모나드와 `(,) k` 펑터(writer 모나드)를 레이어로 쌓은 구조. 이 타입에서는 대수적으로 차이를 저장해야 의미론적으로 올바름 — 레이어들을 `join`으로 합칠 때 가중치가 제대로 누적되려면 각 레이어가 절댓값이 아닌 차이를 담고 있어야 함. ## 결론 — 핵심 원리 하나 > "절댓값을 저장하지 말고 차이를 저장하라." 이게 이 포스트 전체를 관통하는 주제임. Monus는 이 패턴을 대수적으로 형식화하는 도구. 가중치가 monus 구조를 가질 때 적용 가능하고, 적용하면: - 불변식(invariant)이 타입 수준에서 강제됨 - 전역 조작이 O(1)로 줄어듦 - 안정 정렬까지 같은 아이디어로 확장됨 그래프 탐색, 정렬, 효과 순서 제어 등 순서 기반 알고리즘 전반에 유용한 패턴임. ## 핵심 포인트 - Monus는 순서가 모노이드 연산으로 정의되는 대수 구조로, x ≤ y ⟺ ∃z. y = x • z - 힙에서 절댓값 대신 부모와의 차이를 저장하면 힙 성질이 타입 수준에서 강제되고 전체 가중치 수정이 O(1)이 됨 - Max/Last 세미그룹 래퍼로 일반 Ord 키를 monus 힙에서도 사용 가능 - Phases 어플리케이티브를 pairing heap으로 구현하면 임의의 전순서 키로 효과를 재정렬할 수 있음 - Key monus(키 + Int 오프셋)로 안정 정렬을 달성하며, 오프셋 정보가 완전히 로컬하게 유지됨 ## 인사이트 같은 '차이를 저장한다'는 패턴이 힙 구조, 안정 정렬, 모나딕 레이어 합성까지 일관되게 관통함. 대수 구조가 자료구조 설계 원칙과 이렇게 자연스럽게 맞물리는 예시가 드문데, monus가 그 접점을 깔끔하게 포착함.