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)로 줄어듦
• 안정 정렬까지 같은 아이디어로 확장됨

그래프 탐색, 정렬, 효과 순서 제어 등 순서 기반 알고리즘 전반에 유용한 패턴임.