방문자 패턴, 불변 값 객체, 교회/스콧 인코딩, 코요네다, 런타임 등가 증명, 고차 소거자 등 기법을 이용해 ADT와 GADT의 핵심 개념을 C/C++/Java/JavaScript/PureScript/Dhall 같은 언어에서 구현·모방하는 방법을 사례와 함께 정리한다.
Haskell is the world’s best programming language1, but let’s face the harsh reality that a lot of times in life you’ll have to write in other programming languages. But alas you have been fully Haskell-brained and lost all ability to program unless it is type-directed, you don’t even know how to start writing a program without imagining its shape as a type first.
자, 걱정 마시라. Algebraic Data Types와 Generalized Algebraic Data Types(ADTs와 GADTs)의 바탕 이론은 너무나 기초적이라, 여러분이 어떤 언어로 작성하더라도(어느 정도는) 매끈하게 들어맞는다. 결국 마이크로소프트의 자바 코드에 프로펑터 광학을 욱여넣을 수 있었다면 못 할 게 뭐 있겠는가!
이 글은 이전 만우절 글의 전통을 잇는다. 다른 언어들을 이렇게 비틀어 쓰는 방식이 다소 비정상적이거나 권장되지 않을 수도 있다… 그런데 사실 제목은 거짓말이기도 하다. 이런 언어들에도 이런 기능은 분명히 있어야 한다! :D
상기 차원에서, Algebraic Data Types(ADTs)는 곱(product)과 합(sum)이다. 그래서 대수적(algebraic)이라고 부르는 것!
Product는 변경 불가능한 struct일 뿐이고, 이는 사실상 대부분의 언어가 지원한다 — 단, 절대 변경되지 않도록 보장만 할 수 있다면.
예를 들어 c에서 struct는 다음과 같다:
#include <stdint.h>
typedef struct {
uint32_t timestamp;
double amount;
} Transaction;
하지만 적절한 불변 API가 필요하다:
Transaction createTransaction(uint32_t timestamp, double amount) {
return (Transaction){ timestamp, amount};
}
uint32_t getTimestamp(const Transaction* t) {
return t->timestamp;
}
double getAmount(const Transaction* t) {
return t->amount;
}
Transaction setTimestamp(const Transaction* t, uint32_t timestamp) {
return (Transaction){timestamp, t->amount};
}
Transaction setAmount(const Transaction* t, double amount) {
return (Transaction){t->timestamp, amount};
}
데이터와 함수 결합(예: OOP의 클래스)이 되는 언어라면 훨씬 간단하다. 예컨대 자바에서 흔한 "값 객체(value object)" 패턴(대략 자바 빈과 관련2)은 다음과 같다:
public class Transaction {
private final long timestamp;
private final double amount;
public Transaction(long timestamp, double amount) {
this.timestamp = timestamp;
this.amount = amount;
}
public long getTimestamp() { return timestamp; }
public double getAmount() { return amount; }
public Transaction setTimestamp(long newTimestamp) {
return new Transaction(newTimestamp, this.amount);
}
public Transaction setAmount(double newAmount) {
return new Transaction(this.timestamp, newAmount);
}
}
좋다. 특별히 놀랄 건 없다!
이 경우, 이는 ADT(대수적 자료형)일 뿐 아니라 ADT(추상 자료형, abstract data types)이기도 하다. 내부 표현 대신, 타입 대수를 바탕으로 미리 정의된 추상 인터페이스에 따라 다루도록 되어 있기 때문이다.
언어가 합 타입을 지원하지 않는다면 보통은 방문자 패턴(visitor pattern)으로 간다: 내부 구현을 숨기고, 합 타입 값을 처리하는 유일한 방법은 모든 분기를 위한 핸들러를 제공하는 것이다 — 본질적으로 함수로서의 패턴 매치다. 합 타입의 값은 어떤 핸들러가 호출될지 결정한다.
예를 들어, IPv4 또는 IPv6일 수 있는 네트워크 주소 타입을 구현해 보자. 여기서는 제네릭과 클로저 있는 람다를 쓰기 위해 C++을 사용할 것이다. 단지 단순화를 위해서이고, 나중에 C에서는 어떻게 보일지도 논의하겠다.
#include <iostream>
#include <format>
#include <cstdint>
struct IPAddress {
bool isIPv4;
union {
uint32_t ipv4;
uint8_t ipv6[16];
};
};
template <typename R>
struct IPAddressVisitor {
R (*visitIPv4)(uint32_t);
R (*visitIPv6)(const uint8_t (&)[16]);
};
template <typename R>
R acceptIPAddress(const IPAddress& ip, IPAddressVisitor<R> visitor) {
return ip.isIPv4 ? visitor.visitIPv4(ip.ipv4)
: visitor.visitIPv6(ip.ipv6);
}
값 생성은 다음과 같이 한다:
IPAddress mkIPv4(uint32_t value) {
return { true, { value } };
}
IPAddress mkIPv6(const uint8_t (&value)[16]) {
IPAddress out = { false };
std::copy(std::begin(value), std::end(value), out.ipv6);
return out;
}
그리고 주소를 출력해 보자:
std::string showIPAddress(const IPAddress& ip) {
IPAddressVisitor<std::string> visitor = {
[](uint32_t v) {
return std::format("{}.{}.{}.{}",
(v >> 24) & 0xFF, (v >> 16) & 0xFF,
(v >> 8) & 0xFF, v & 0xFF);
},
[](const uint8_t (&v)[16]) {
return std::format("{:02X}{:02X}:{:02X}{:02X}:{:02X}{:02X}:{:02X}{:02X}:"
"{:02X}{:02X}:{:02X}{:02X}:{:02X}{:02X}:{:02X}{:02X}",
v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7],
v[8], v[9], v[10], v[11], v[12], v[13], v[14], v[15]);
}
};
return acceptIPAddress(ip, visitor);
}
이 방식에서는 모든 분기를 처리하도록 컴파일러가 강제한다는 점에 주목하라. 그리고 만약 새 분기를 추가하면, IPAddress를 IPAddressVisitor로 소비하는 모든 곳이 새 핸들러를 추가해야 한다.
제네릭이나 충분한 다형성이 없는 언어에서는, 모든 분기가 같은 타입을 반환한다는 것을 보장할 수 없어서 "순수한" 방문자 패턴을 강제하기 어렵다.
흔한 해법은 "효과가 있는" 방문자 패턴이다. 요지는 무언가를 반환하는 게 아니라, 현재 분기의 페이로드에 대해 어떤 동작을 실행하는 것이다. 타입이 엄격하지 않은 C, 자바스크립트, 파이썬 등의 언어에서 꽤 효과적이다.
예컨대 "암묵적 nullable"을 이렇게 다룰 수 있다:
export const visitMaybe = (visitNothing, visitJust, val) =>
(val == null) ? visitNothing() : visitJust(val);
이는 사실 Haskell의 for_와 비슷하다: 값이 있으면 어떤 액션을 조건부로 실행할 수 있다.
visitMaybe(
() => console.log("Nothing to request"),
(reqPayload) => makeRequest("google.com", reqPayload),
maybeRequest
);
더 간단하게, 언어에 서브타이핑(예: 클래스/서브클래스)이나 다른 형태의 동적 디스패치가 있다면 그걸로 구현할 수 있다. 파이썬, 자바, C++ 등에서 편리하다.
interface ExprVisitor<R> {
R visitLit(int value);
R visitNegate(Expr unary);
R visitAdd(Expr left, Expr right);
R visitMul(Expr left, Expr right);
}
abstract class Expr {
public abstract <R> R accept(ExprVisitor<R> visitor);
}
또는, 람다가 쉬운 언어라면 방문자를 튜플링하지 않고 accept 자체가 각 생성자에 대응하는 여러 인수를 받도록 할 수 있다:
// 명시적 Visitor 클래스를 두지 않는 대안 정의
abstract class Expr {
public abstract <R> R accept(
Function<int,R> visitLit,
Function<Expr,R> visitNegate,
BiFunction<Expr,Expr,R> visitAdd,
BiFunction<Expr,Expr,R> visitMul
);
}
(참고로 C++은 템플릿 가상 메서드를 허용하지 않는다 — 언어 의미론/문법상 불가능해서가 아니라, 메인테이너들이 추가하기 귀찮아서 — 그래서 이를 충실히 하려면 약간의 창의력이 필요하다)
이제, 동적 디스패치 또는 서브클래스 다형성이 있다면, 태그드 유니온 대신 다른 인코딩을 쓸 수 있다. 순수 유니온 타입을 완전하게 지원하지 않는 언어에서도 작동한다. 이 방식에서는 각 생성자가 하나의 클래스로 되고, 합 타입 패턴을 제대로 강제하려면 accept를 통해서만 접근하도록 하는 것이 중요하다.
class Lit extends Expr {
private final int value;
public Lit(int value) {
this.value = value;
}
@Override
public <R> R accept(ExprVisitor<R> visitor) {
return visitor.visitLit(value);
}
}
class Negate extends Expr {
private final Expr unary;
public Negate(Expr unary) { this.unary = unary; }
@Override
public <R> R accept(ExprVisitor<R> visitor) {
return visitor.visitNegate(unary);
}
}
class Add extends Expr {
private final Expr left;
private final Expr right;
public Add(Expr left, Expr right) {
this.left = left;
this.right = right;
}
@Override
public <R> R accept(ExprVisitor<R> visitor) {
return visitor.visitAdd(left, right);
}
}
class Mul extends Expr {
private final Expr left;
private final Expr right;
public Mul(Expr left, Expr right) {
this.left = left;
this.right = right;
}
@Override
public <R> R accept(ExprVisitor<R> visitor) {
return visitor.visitMul(left, right);
}
}
(하지만, 실제로 자바를 쓰고 있다면 sealed class로 네이티브 switch/case의 포괄성 검사까지 활용할 수 있다는 점을 덧붙인다.)
언어가 허용한다면 모든 서브클래스를 익명 클래스로 만들고 팩토리 메서드로 내보내는 방식도 가능하다:
abstract class Expr {
public abstract <R> R accept(ExprVisitor<R> visitor);
public static Expr lit(int value) {
return new Expr() {
@Override
public <R> R accept(ExprVisitor<R> visitor) {
return visitor.visitLit(value);
}
};
}
public static Expr negate(Expr unary) {
return new Expr() {
@Override
public <R> R accept(ExprVisitor<R> visitor) {
return visitor.visitNegate(unary);
}
};
}
public static Expr add(Expr left, Expr right) {
return new Expr() {
@Override
public <R> R accept(ExprVisitor<R> visitor) {
return visitor.visitAdd(left, right);
}
};
}
// ... 등등
}
사용은 다음과 같다:
public class Main {
public static void main(String[] args) {
Expr expr = new Mul(new Negate(new Add(new Lit(4), new Lit(5))), new Lit(8));
// 또는
// Expr expr = Eval.mul(Eval.negate(Eval.add(Eval.lit(4), Eval.lit(5))), Eval.lit(8));
ExprVisitor<Integer> eval = new ExprVisitor<>() {
@Override public Integer visitLit(int value) {
return value;
}
@Override public Integer visitNegate(Expr unary) {
return -unary.accept(this);
}
@Override public Integer visitAdd(Expr left, Expr right) {
return left.accept(this) + right.accept(this);
}
@Override public Integer visitMul(Expr left, Expr right) {
return left.accept(this) * right.accept(this);
}
};
System.out.println("Result: " + expr.accept(eval));
}
}
이렇게 함수 참조를 전달하는 방식은 데이터 타입의 스콧 인코딩과 상당히 가깝다 — 비재귀 타입에는 사실상 처치 인코딩과 동일하다.
재귀 타입 얘기가 나왔으니… 언어가 재귀 데이터 타입을 지원하지 않으면 어떡하지? 아예 재귀를 허용하지 않거나, 재귀적으로 생성한 값을 다루기가 귀찮다면? 예컨대 명시적 메모리 관리 언어에서 Expr 타입을 작성한다고 상상해 보라. 또는 더 우아하고 실행 시 안전한 방식으로 재귀 타입을 표현하고 싶다면?
대신 방문자를 "카타모르피즘(catomorphism)" 또는 처치 인코딩 형태로 만들 수 있다. 재귀 하위 값을 방문자에게 건네는 대신, 방문자가 자기 자신을 재귀적으로 적용한 결과를 반환하도록 하는 것이다.
가장 유명한 비재귀 언어 중 하나인 dhall로 해 보자. Dhall은 네이티브 합 타입이 있으므로 방문자 패턴을 수동으로 쓰는 건 걱정하지 말자. 그러나 재귀 데이터 타입은 없다.
다음과 같은 타입을 정의한다고 하자:
data Expr = Lit Natural
| Add Expr Expr
| Mul Expr Expr
그러나 dhall에서는 자기 자신을 참조하는 데이터 타입을 정의할 수 없다. 대신 "처치 인코딩"으로 정의할 수 있다: Expr를 소비할 때 무엇을 할지 주는데, 그 소비 함수는 자신에게 재귀적으로 적용된 것처럼 주어진다.
let ExprF : Type -> Type
= \(r : Type) ->
{ lit : Natural -> r
, add : r -> r -> r
, mul : r -> r -> r
}
let Expr : Type
= forall (r : Type) -> ExprF r -> r
여기서 ExprF r은 사실상 ExprVisitor<R>과 동일하지만, add가 Expr -> Expr -> r 대신 r -> r -> r라는 점이 다르다: 입력 값은 식 자체가 아니라, 그 식에 재귀적으로 fold를 적용한 결과이다. 원래의 비재귀 ExprVisitor<R>(정확히는 R accept(ExprVisitor<R>))는 흔히 재귀적인 "처치 인코딩" fold에 대응되는 "스콧 인코딩"이라고 부른다.
값 생성에서는 방문자를 받아 재귀적으로 적용한다:
let lit : Natural -> Expr
= \(x : Natural) ->
\(r : Type) ->
\(handlers : ExprF r) ->
handlers.lit x
let add : Expr -> Expr -> Expr
= \(left : Expr) ->
\(right : Expr) ->
\(r : Type) ->
\(handlers : ExprF r) ->
handlers.add (left r handlers) (right r handlers)
let mul : Expr -> Expr -> Expr
= \(left : Expr) ->
\(right : Expr) ->
\(r : Type) ->
\(handlers : ExprF r) ->
handlers.mul (left r handlers) (right r handlers)
마지막으로, 이 데이터 타입을 사용하는 것은 handler를 제공해 아래에서 위로 fold하도록 하는 것이다. add : \(left : Natural) -> \(right : Natural) -> left + right는 이미 하위 식에 handler가 적용되었다고 가정하므로, 양쪽 모두 Expr가 아니라 Natural을 받는다.
let eval : Expr -> Natural
= \(e : Expr) ->
e Natural
{ lit = \(x : Natural) -> x
, add = \(left : Natural) -> \(right : Natural) -> left + right
, mul = \(left : Natural) -> \(right : Natural) -> left * right
}
let testVal : Expr
= mul (add (lit 4) (lit 5)) (lit 8)
in assert : eval testVal === 72
이 패턴은 Haskell처럼 데이터타입 재귀가 좋은 언어에서도 유용하다 — 실제로 recursion-schemes로 재귀 데이터 타입을 리팩터링한 형태이며, 일반 재귀 타입과 나란히 존재하게 해도 유용하다. 이에 대해 이전 블로그 글에서 자세히 다뤘다.
이 패턴은 다른 언어에도 꽤 이식 가능하다. 랭크-N 타입 같은 것을 흉내 낼 수만 있다면:
interface ExprFold<R> {
R foldLit(int value);
R foldNegate(R unary);
R foldAdd(R left, R right);
R foldMul(R left, R right);
}
interface Expr {
public abstract <R> R accept(ExprFold<R> fold);
public static Expr lit(int value) {
return new Expr() {
@Override
public <R> R accept(ExprFold<R> fold) {
return fold.foldLit(value);
}
};
}
public static Expr negate(Expr unary) {
return new Expr() {
@Override
public <R> R accept(ExprFold<R> fold) {
return fold.foldNegate(unary.accept(fold));
}
};
}
// 등등
}
여기서 "랭크-N 타입"이란, 객체가 다형적인 함수를 생성할 수 있다는 뜻이다: 어떤 Expr가 주어지면, 표현의 선택과 무관하게 임의의 R에 대해 <R> R accept(ExprFold <R> fold)를 생성할 수 있어야 한다.
당신의 언어에서 ADT를 구현했거나, 네이티브 ADT가 있는 언어에 있다. 인생이 좋아 보인다. 그러다 귓가에 속삭이는 목소리: "더 많은 타입 안정성이 필요해." 이를 뿌리치고, 심지어는 그 없이도 많은 걸 해 보려 하지만, 결국 궁극의 타입 안정성이라는 따뜻하지만 냉혹한 포옹을 받아들이게 된다. 이제 어쩌지?
Haskell에서 싱글톤은 리어파이(reify) 가능한 타입과 값을 연결하기 위해 쓰는 열거형에 가깝다. 여기서 "리어파이 가능"이란, 싱글톤의 런타임 값을 가져와 타입 레벨로 증거를 끌어올릴 수 있음을 뜻한다. 나는 purescript로 작성한 https://coronavirus.jle.im/ — COVID-19 데이터의 웹 기반 시각화 도구(소스) — 를 만들면서 이를 실제로 겪었다. 산점도용 스케일을 나타내는 싱글톤이 필요했고, 플로팅 가능한 데이터와 연결해야 했다. 그리고 이는 ADT는 있지만 GADT는 없는 purescript에서 타입 안전해야 했고, 자바스크립트 FFI에서도 타입 안전해야 했다.
Haskell에서는 대략 다음과 같이 생겼다:
-- | Numeric types
data NType :: Type -> Type where
NInt :: NType Int
NDouble :: NType Double
NPercent :: NType Percent
-- | Define a scale
data Scale :: Type -> Type where
ScaleDate :: Scale Date
ScaleLinear :: Bool -> NType a -> Scale a -- ^ whether to include zero in the axis or not
ScaleLog :: NType a -> Scale a
사용은 다음과 같다:
plot :: Scale a -> Scale b -> [(a, b)] -> Canvas
즉, plot에 전달하는 값이 입력 튜플의 타입을 결정한다:
ghci> :t plot ScaleDate (ScaleLinear True (LNumeric NInt))
[(Date, Int)] -> Canvas
하지만 ADT만 있다고 하자. 그리고 이를 구조체와 함수만 있는 자바스크립트 FFI로 내려보낸다. 타입 안전성을 버리고 런타임 에러로 때울 수 있지만… 안 된다. 타입 불안전성은 받아들일 수 없다.
우리가 얻고 싶은 핵심 능력은 이것이다: ScaleDate에 대해 패턴 매칭하면 a가 Date라는 걸 안다. NInt에 매칭하면 a는 반드시 Int라는 걸 안다.
이 예제에서는, purescript와 자바스크립트에서 조금 더 단순한 함수를 구현해 보겠다: 스케일 타입과 점들의 리스트를 받아 경계를 출력하는 함수다. Haskell에서는 다음과 같다:
data AxisBounds a = AB
{ minValue :: a
, minLabel :: String
, maxValue :: a
, maxLabel :: String
}
displayAxis :: Scale a -> [a] -> AxisBounds a
displayAxis = \case
ScaleDate -> \xs ->
let xMin = minimum xs
xMax = maximum xs
in AB xMin (showDate xMin) xMax (showDate xMax)
ScaleLinear hasZero nt -> \xs ->
displayNumericAxis (if hasZero then 0:xs else xs)
ScaleLog nt ->
displayNumericAxis nt xs
displayNumericAxis :: NType a -> [a] -> AxisBounds a
displayNumericAxis = \case
NInt -> \xs ->
let xMin = minimum xs
xMax = maximum xs
in AB xMin (printf "%d" xMin) xMax (printf "%d" xMax)
NDouble -> \xs ->
let xMin = minimum xs
xMax = maximum xs
in AB xMin (printf "%.4f" xMin) xMax (printf "%.4f" xMax)
NPercent -> \xs ->
let xMin = minimum xs
xMax = maximum xs
in AB xMin (printf "%.1f%%" (xMin*100)) xMax (printf "%.1f%%" (xMax*100))
(Percent 타입은 그냥 Float을 새타입으로 감싼 것이라고 생각하자)
이걸 하는 방법은 최소 두 가지가 있다. 여기서는 런타임 동등성 증거와 고차(kind) 소거자(higher-kinded eliminators)를 다룬다.
요네다 보조정리는 범주론이 낳은 가장 강력한 도구 중 하나이고, 그 형제인 coyoneda는 Haskell에서 가장 유용한 추상화 중 하나다.
이것은 GADT를 직접 주지는 않지만, GADT를 일반 ADT로 "다운그레이드"하는 아주 가벼운 방법을 준다. 전력이 필요치 않다면 적절하다.
핵심 요령은 이렇다: MyGADT a가 있고 이것을 써서 a를 생산할 것임을 안다면, 공변(covariant) 코요네다 변환을 할 수 있다.
예를 들어 잠재적인 데이터 소스를 나타내는 타입이 있다면:
data Source :: Type -> Type where
ByteSource :: Handle -> Source Word
StringSource :: FilePath -> Source String
readByte :: Handle -> IO Word
readString :: FilePath -> IO String
readSource :: Source a -> IO a
readSource = \case
ByteSource h -> readByte h
StringSource fp -> readString fp
Source를 일반 매개변수화된 ADT로 바꾸고 X -> a 필드를 추가해, 일종의 CPS 변환을 할 수 있다:
data Source a =
ByteSource Handle (Word -> a)
| StringSource FilePath (String -> a)
byteSource :: Handle -> Source Word
byteSource h = ByteSource h id
stringSource :: FilePath -> Source String
stringSource fp = StringSource fp id
readSource :: Source a -> IO a
readSource = \case
ByteSource h out -> out <$> readByte h
StringSource fp out -> out <$> readString fp
이 방식의 장점은, 원래의 GADT는 가질 수 없던 Functor 인스턴스를 Source가 가질 수 있다는 것이다.
그리고 MyGADT a가 a를 소비할 것이라면, contravariant coyoneda 변환을 할 수 있다:
data Sink a =
ByteSink Handle (a -> Word)
| StringSink FilePath (a -> String)
이렇게 하면 Contravariant 인스턴스도 공짜로 생긴다!
그리고 a를 소비도 하고 생산도 한다면, invariant coyoneda 변환을 할 수 있다
data Interface a =
ByteInterface Handle (Word -> a) (a -> Word)
| StringInterface FilePath (String -> a) (Word -> a)
하지만 실제로는, _진정한 동등성_이란 단사적 타입 생성자 아래로도 들어올릴 수 있어야 하고, 모든 continuation을 다 들고 다니는 건 부담스럽다. 이를 **런타임 등가 증거(runtime equality witness)**로 묶어 담을 수 있다.
이는 NInt "안에" 넣어둘 수 있는 어떤 것이고, NType a에 대해 패턴 매칭할 때 a가 Int임을 타입 시스템이 확신할 수 있게 해 준다.
IsEq a b 같은 타입의 데이터를 만들어 아래 함수를 제공해야 한다:
refl :: IsEq a ato :: IsEq a b -> a -> bsym :: IsEq a b -> IsEq b atrans :: IsEq a b -> IsEq b c -> IsEq a cinj :: IsEq (f a) (f b) -> IsEq a bto와 sym이 있으면 from :: IsEq a b -> b -> a도 얻는다.
이 모든 것으로, 원래의 IsEq a Word -> Word -> a와 IsEq a Word -> a -> Word 함수를 다시 얻을 수 있어, 두 개의 함수를 넣는 수고를 던져 준다.
여러분의 언어에는 이미 이런 IsEq이 있을 수도 있다. 하지만 내가 흥미롭게 보는 방법 중 하나는 라이프니츠(Leibniz) 등가다(Ryan Scott의 글에서 자세히). 이는 하이어-카인드 다형성이 있는 언어에서 동작한다. 그런 언어에서의 라이프니츠 동등성은 forall p. p a -> p b이면 a와 b가 같다: a의 임의 속성은 b에도 참이다.
Haskell에서는 다음과 같이 쓴다:
newtype Leibniz a b = Leibniz (forall p. p a -> p b)
refl :: Leibniz a a
refl = Leibniz id
Leibniz를 구성하는 유일한 방법은 두 타입 매개변수가 같은 경우뿐이다: Leibniz a a 형태의 값만 만들 수 있고, b가 a가 아닌 Leibniz a b는 만들 수 없다.
Leibniz a b -> Leibniz b a와 Leibniz a b -> Leibniz b c -> Leibniz a c 같은 함수를 작성해 이것이 실제로 동등성임을 증명할 수 있다(위 Ryan Scott의 글 참고). 하지만 실무에서는 a와 b를 안전하게 왕복 강제(coerce)하는 방식으로 이를 실현한다:
newtype Identity a = Identity { runIdentity :: a }
to :: Leibniz a b -> a -> b
to (Leibniz f) = runIdentity . f . Identity
newtype Op a b = Op { getOp :: b -> a }
from :: Leibniz a b -> b -> a
from (Leibniz f) = getOp (f (Op id))
따라서, 언어가 하이어-카인드 랭크-2 타입을 지원한다면 해결책이 있다!
다른 언어에선 다른 해법이 있지만, 대개는 언어 의존적이다.
이제 purescript로 모든 걸 써 보자. 핵심 차이는, map (to isNumber) :: Array a -> Array Number 같은 식으로, 우리가 그 Array의 타입을 알고 있는 것으로 바꾸는 것이다.
import Text.Printf
newtype Leibniz a b = Leibniz (forall p. p a -> p b)
to :: Leibniz a b -> a -> b
from :: Leibniz a b -> b -> a
data NType a =
NInt (Leibniz a Int)
| NNumber (Leibniz a Number)
| NPercent (Leibniz a Percent)
type AxisBounds a =
{ minValue :: a
, minLabel :: String
, maxValue :: a
, maxLabel :: String
}
displayNumericAxis :: NType a -> Array a -> AxisBounds a
displayNumericAxis = \case
NInt isInt -> \xs ->
let xMin = minimum $ map (to isInt) xs
xMax = maximum $ map (to isInt) xs
showInt = show
in { minValue: xMin
, minLabel: showInt xMin
, maxValue: xMax
, maxLabel: showInt xMax
}
NNumber isNumber -> \xs ->
let xMin = minimum $ map (to isNumber) xs
xMax = maximum $ map (to isNumber) xs
showFloat = printf (Proxy :: Proxy "%.4f") -- 작동 방식이 약간 다르다
in { minValue: xMin
, minLabel: showFloat xMin
, maxValue: xMax
, maxLabel: showFloat xMax
}
NPercent isPercent -> \xs ->
let xMin = minimum $ map (to isPercent) xs
xMax = maximum $ map (to isPercent) xs
showPercent = printf (Proxy :: Proxy "%.1f%%") <<< (_ * 100.0)
in { minValue: xMin
, minLabel: showPercent xMin
, maxValue: xMax
, maxLabel: showPercent xMax
}
[a]를 [Int]인 것처럼 다루려면, Leibniz a Int가 준 사상 함수를 그 위에 map해야 한다. 솔직히 이 순진한 방법은 배열 복사를 야기하므로 런타임 비용이 든다. 하지만 조금 더 창의적으로 하면 상수 공간과 추가 할당 없이 최솟값/최댓값을 구할 수 있다.
그리고 자바스크립트 FFI에 넘기고 싶다면, 자바스크립트에는 합 타입이 없으니 간단한 방문자를 만들어 쓸 수 있다:
type NVisitor a r =
{ nvInt :: Leibniz a Int -> r
, nvNumber :: Leibniz a Number -> r
, nvPercent :: Leibniz a Percent -> r
}
type NAccept a = forall r. NVisitor a r -> r
toAccept :: NType a -> NAccept a
toAccept = case _ of
NInt isInt -> \nv -> nv.nvInt isInt
NNumber isNumber -> \nv -> nv.nvNumber isNumber
NPercent isPercent -> \nv -> nv.nvPercent isPercent
foreign import _formatNumeric :: forall a. Fn2 (NAccept a) a String
formatNumeric :: NType a -> a -> String
formatNumeric nt = runFn2 _formatNumeric (toAccept nt)
FFI 바인딩은 다음과 같다(내 실제 소스에서 가져옴):
import * as d3 from "d3-format";
export const _formatNumeric = (naccept, xs) =>
naccept(
{ nvInt: (isInt) => d3.format("~s")
, nvNumber: (isNumber) => d3.format(".3~s")
, nvPercent: (isPercent) => d3.format("+.3~p")
}
);
인정하건대, 자바스크립트에서는 등가를 버려서 "GADT 타입 안전성"을 잃는다. 하지만 가능한 선에서 취하자 — 적어도 합 타입의 타입 안전성과 포괄성 검사를 위한 방문자 패턴은 유지한다. 타입스크립트에서는 아직 해 보지 않았지만, 아마 라이프니츠 등가를 형식화해 타입스크립트에서도 전체 체인을 타입 안전하게 유지할 방법이 있을 것이다.
이것은 방문자 패턴의 하이어-카인드 버전이다. 종속 타입 이론에서는 이런 방문자를 흔히 "소거자(eliminator)" 혹은 분해자(destructor)라고 부르는데, 더 멋진 이름이다.
일반 방문자에서는 다음처럼 한다:
data User = TheAdmin | Member Int
data UserHandler r = UH
{ uhTheAdmin :: r
, uhMember :: Int -> r
}
그런데 적절한 continuation 집합이 있다면, User 없이도 사실상 User와 동일한 무언가를 가진다:
type User' = forall r. UserHandler r -> r
fromUser :: User -> User'
fromUser = \case
TheAdmin -> \UH{..} -> uhTheAdmin
Member userId -> \UH{..} -> uhMember userId
toUser :: User' -> Foo
toUser f = f $ UH { fhTheAdmin = TheAdmin, fhMember = Member }
이는 User가 실제로 forall r. UserHandler r -> r와 동등함을 의미한다: 언어에 합 타입이 없더라도 forall r. UserHandler r -> r로 인코딩할 수 있다. 방문자 만세.
그런데 여기서 r 타입 변수는 의미론적으로 무엇을 나타내는가? UserHandler r에서 r은 해석의 "대상"이다. 하지만 r과 User 사이에는 더 깊은 관계가 있다: UserHandler r은 User를 r로 "임베딩"한다. 그리고 UserHandler r -> r은 그 임베딩을 실제 User에 적용한 것이다.
r ~ ()로 잡으면 UserHandler ()는 User를 ()로 임베딩한다. r ~ String이면 String으로(이를테면 "표시"하기). r ~ User면 UserHandler User는 User를… 자기 자신으로 임베딩한다?
즉, 여기서 r은 사용자를 바라보는 투영(projection)이다. 그리고 모든r에 대해 forall r. UserHandler r -> r이 되게 하면, 어떤 정보도 잃지 않음을 보장한다: 임베딩은 완전히 1:1이다. 이는 실제 User 타입이 없어도 "다형적"으로 User를 충실히 "만들" 수 있게 해 준다.
이를 더 강조하기 위해, 어떤 사람들은 타입 변수 이름을 타입 이름과 똑같이 짓기도 한다: UserHandler user:
-- | 같은 내용이지만 이름만 바꿔 요점을 강조
data MakeUser user = MakeUser
{ uhTheAdmin :: user
, uhMember :: Int -> user
}
type User' = forall user. MakeUser user -> user
forall user.는 실제 User 데이터 타입이 없어도 시스템 안에서 User를 충실히 "만들" 수 있게 한다. forall r의 r이 User를 대리한다고 상상할 수 있다.
이제 돌파구: forall (r :: Type)로 User :: Type을 대체할 수 있다면, Scale :: Type -> Type을 대신해 forall (p :: Type -> Type)을 쓰면 어떤가?
data Scale :: Type -> Type where
ScaleDate :: Scale Date
ScaleLinear :: Bool -> LType a -> Scale a
ScaleLog :: NType a -> Scale a
data ScaleHandler p a = SH
{ shDate :: p Date
, shLinear :: Bool -> NType a -> p a
, shLog :: NType a -> p a
}
type Scale' a = forall p. ScaleHandler p a -> p a
fromScale :: Scale a -> Scale' a
fromScale = \case
ScaleDate -> \SH{..} -> shDate
ScaleLinear hasZero lt -> \SH{..} -> shLinear hasZero lt
ScaleLog nt -> \SH{..} -> shLog nt
toScale :: Scale' a -> Scale a
toScale f = f $ SH { shDate = ScaleDate, shLinear = ScaleLinear, shLog = ScaleLog }
새 시스템에서 forall p. ScaleHandler p a -> p a는 Scale과 동일하다: 언어가 GADT를 지원하지 않더라도 p a를 사용해 Scale을 대체할 수 있다.
이제 purescript로 formatNType을 써 보자. 더 이상 실제 Scale 합 타입은 없고, 그 하이어-카인드 처치 인코딩만 있다:
type NType a = forall p.
{ int :: p Int
, number :: p Number
, percent :: p Percent
} -> p a
type Scale a = forall p.
{ date :: p Date
, linear :: Bool -> NType a -> p a
, log :: NType a -> p a
} -> p a
ntInt :: NType Int
ntInt nth = nth.int
ntNumber :: NType Number
ntNumber nth = nth.number
ntPercent :: NType Percent
ntPercent nth = nth.percent
formatNType :: NType a -> a -> String
formatNType nt = f
where
Op f = nt
{ int: Op show
, number: Op $ printf (Proxy "%.4f")
, percent: Op $ printf (Proxy "%.1f%%") <<< (_ * 100.0)
}
여기서 우리는
newtype Op b a = Op (a -> b)
를 "대상"으로 사용한다: NType a를 Op String a로 바꾼다. 그리고 Op String a는 a -> String이며, 우리가 원하던 것이다! int 필드는 Op String Int, number 필드는 Op String Number 등등이다.
많은 언어에서 이 기법을 효과적으로 쓰려면 newtype 래퍼가 필요해, 비자명한 상황에서는 다소 불편할 수 있다. 예를 들어 이전의 축 함수처럼 NType a -> [a] -> String을 쓰고 싶다면, 인자로 a를 갖는 [a] -> String을 위한 newtype 래퍼가 있어야 한다:
newtype OpList b a = Op ([a] -> b)
아니면 Compose를 재사용할 수도 있다:
newtype Compose f g a = Compose (f (g a))
이 경우 p 투영 타입은 Compose Op []가 된다. 즉, 매번 bespoke 래퍼를 쓸 필요는 없지만, 약간의 두뇌 회전은 필요하다(또는 나중에 보겠지만, 이런 래퍼가 필요 없는 언어에 있다면 이야기가 달라진다).
덧붙여, 이 방법은 다인자에도 잘 일반화된다: MyGADT a b c 같은 타입이 있다면 forall (p :: k1 -> k2 -> k3 -> Type)로 투영하면 된다.
여기서 다룬 두 방법(런타임 등가 증거 vs. 하이어-카인드 소거자)은 실제로 전력이 완전히 동일하진 않다고 들었다. 어떤 GADT에서는 하나는 되는데 다른 하나는 안 되는 경우가 있다고… 어디서 읽었는지 기억이 안 나고, 나도 그 상황을 스스로 찾아낼 만큼 거대한 뇌는 아니다. 하지만 독자 여러분이 아이디어가 있다면 꼭 알려 주시길!
잠시 GADT와 기술적으로 직접 관련은 없지만 흔히 함께 쓰이는 개념을 이야기하자.
값을 그 NType과 함께 저장하되 타입 변수를 숨기고 싶다면? Haskell에서는 이렇게 쓴다:
data NType :: Type -> Type where
NInt :: NType Int
NDouble :: NType Double
NPercent :: NType Percent
data SomeNType = forall a. SomeNType (NType a) a
formatNType :: NType a -> a -> String
formatNType nt x = ...
formatSomeNType :: SomeNType -> String
formatSomeNType (SomeNType nt x) = formatNType nt x
myFavoriteNumbers :: [SomeNType]
myFavoriteNumbers = [SomeNType NInt 3, SomeNType NDouble pi]
하지만 언어에 존재 타입이 없다면? 기본적으로 SomeNType은 제네릭이 아니라, 같은 타입 변수 a를 공유하는 NType a와 a를 _포함_하는 값이다.
전략 하나는 존재 타입을 CPS 형태(continuation-passing style)로 변환하는 것이다. 즉, 패턴 매치했다면 그 내용으로 무엇을 할지 정확히 적는다. 본질적으로 단일 생성자만 있는 랭크-N 방문자 패턴이다:
type SomeNType = forall r. (forall a. NType a -> a -> r) -> r
someNType :: NType a -> a -> SomeNType
someNType nt x = \f -> f nt x
formatSomeNumeric :: SomeNType -> String
formatSomeNumeric snt = snt
\nt x -> formatNumeric nt x
문법적으로, snt 자체가 "자기 자신의" 패턴 매치처럼 동작한다고 상상할 수 있다. SomeNType nt x -> ..로 매칭하는 대신 \nt x -> ..로 "매칭"한다.
이 일반 패턴은 자바 같은 전통적 제네릭 언어에서도 통한다:
interface SomeNTypeVisitor<R> {
<A> R visit(NType<A> nt, A val);
}
interface SomeNType {
public abstract <R> R accept(SomeNTypeVisitor<R> visitor);
// 옵션 1: 팩토리 메서드
public static <A> SomeNType someNType(NType<A> nt, A val) {
return new SomeNType() {
@Override
public <R> R accept(SomeNTypeVisitor<R> visitor) {
return visitor.visit(nt, val);
}
};
}
}
// 옵션 2: 타입 변수를 숨기는 하위 타입 — 생성 후 항상 SomeNType으로 업캐스트해야 함
class SomeNTypeImpl<A> extends SomeNType {
private NType<A> nt;
private A val;
public SomeNTypeImpl(NType<A> nt, A val) {
this.nt = nt;
this.val = val;
}
@Override
public <R> R accept(SomeNTypeVisitor<R> visitor) {
return visitor.visit(nt, val);
}
}
…이렇게 자바를 쓰는 사람이 있을까? 구글에 있을 때 한 번 커밋했다가 자동으로 PIP 후보로 지목당했다.
이 이야기의 클라이맥스: 언어가 GADT도, 재귀 데이터 타입도 지원하지 않는다면?
다시 _dhall_을 예시로 쓰겠다. 하지만 여기서의 교훈은 재귀 타입이 있어도 유용하다: 우리는 하이어-카인드 처치 인코딩을 이야기할 것이고, 이는 일반 재귀 타입과 나란히 존재시키면 유용한 형태다.
Expr a가 a로 평가되는 Expr를 나타내는 GADT라고 상상하자:
data Expr :: Type -> Type where
NatLit :: Natural -> Expr Natural
BoolLit :: Bool -> Expr Bool
Add :: Expr Natural -> Expr Natural -> Expr Natural
LTE :: Expr Natural -> Expr Natural -> Expr Bool
Ternary :: Expr Bool -> Expr a -> Expr a -> Expr a
eval :: Expr a -> a
eval = \case
NatLit n -> n
BoolLit b -> b
Add x y -> eval x + eval y
LTE a b -> eval a <= eval b
Ternary b x y -> if eval b then eval x else eval y
이 타입 변수를 두면 Expr는 타입 안전해진다: Expr Bool을 Add할 수 없고, Ternary의 두 분기는 같은 결과 타입을 가져야 한다. 그리고 eval :: Expr a -> a를 써도 반환 타입이 정확히 무엇인지 알 수 있다.
이제 두 개념을 결합하자: 첫째, 처치 인코딩 — 핸들러가 재귀 값 Expr 대신 fold의 최종 결과 r을 받는다. 둘째, 하이어-카인드 소거자 — Expr :: Type -> Type을 forall (p :: Type -> Type)에 임베딩한다.
그리고 마침내, 우리는 다음을 얻는다:3
let ExprF =
\(p : Type -> Type) ->
{ natLit : Natural -> p Natural
, boolLit : Bool -> p Bool
, add : p Natural -> p Natural -> p Natural
, ternary : forall (a : Type) -> p Bool -> p a -> p a -> p a
}
let Expr
: Type -> Type
= \(a : Type) -> forall (p : Type -> Type) -> ExprF p -> p a
let eval
: forall (a : Type) -> Expr a -> a
= \(a : Type) ->
\(e : Expr a) ->
e
(\(q : Type) -> q)
{ natLit = \(x : Natural) -> x
, boolLit = \(x : Bool) -> x
, add = \(x : Natural) -> \(y : Natural) -> x + y
, ternary =
\(a : Type) ->
\(b : Bool) ->
\(x : a) ->
\(y : a) ->
if b then x else y
}
다시 말해, 이제 add는 Expr를 받지 않고 p Natural을 받는다: "fold의 Natural 결과"다. p는 Expr을 어디에 임베딩하는지뿐 아니라, 재귀 fold의 결과도 대리한다. 그래서 eval에서 add의 첫 두 인수는 하위 평가의 Natural 결과다.
값 생성은 이전처럼 두 기법을 결합해, 핸들러를 아래로 흘려보내며 만든다:
let natLit
: Natural -> Expr Natural
= \(n : Natural) ->
\(p : Type -> Type) ->
\(handlers : ExprF p) ->
handlers.natLit n
let boolLit
: Bool -> Expr Bool
= \(n : Bool) ->
\(p : Type -> Type) ->
\(handlers : ExprF p) ->
handlers.boolLit n
let add
: Expr Natural -> Expr Natural -> Expr Natural
= \(x : Expr Natural) ->
\(y : Expr Natural) ->
\(p : Type -> Type) ->
\(handlers : ExprF p) ->
handlers.add (x p handlers) (y p handlers)
let ternary
: forall (a : Type) -> Expr Bool -> Expr a -> Expr a -> Expr a
= \(a : Type) ->
\(b : Expr Bool) ->
\(x : Expr a) ->
\(y : Expr a) ->
\(p : Type -> Type) ->
\(handlers : ExprF p) ->
handlers.ternary (b p handlers) (x p handlers) (y p handlers)
let testVal
: Expr Natural
= add (natLit 5) (add (natLit 6) (natLit 7))
in assert : eval testVal === 18
이해가 어렵다면, 재귀 ADT 섹션과 하이어-카인드 소거자 섹션을 각각 복습해 둘을 잘 이해한 뒤, 이를 결합한 위 내용을 다시 보라!
인정하건대 Haskell(과 purescript)에서는 타입 변수를 명시적으로 전달할 필요가 없어 훨씬 간단하다:
data ExprF p = ExprF
{ natLit :: Natural -> p Natural
, boolLit :: Bool -> p Bool
, add :: p Natural -> p Natural -> p Natural
, ternary :: forall a. p Bool -> p a -> p a -> p a
}
type Expr a = forall p. ExprF p a -> p a
eval :: Expr a -> a
eval e = runIdentity $
e
{ natLit = Identity
, boolLit = Identity
, add = \(Identity x) -> \(Identity y) -> Identity (x + y)
, ternary = \(Identity b) -> \(Identity x) -> \(Identity y) -> if b then x else y
}
ternary :: Expr Bool -> Expr a -> Expr a -> Expr a
ternary b x y handlers = handlers.ternary (b handlers) (x handlers) (y handlers)
하지만 dhall 버전의 우연한 장점 하나는, Haskell처럼 별도의 newtype 래퍼가 필요 없다는 점이다. 타입 추론이 이런 것에서 종종 막히는데, dhall은 사실상 타입 추론이 거의 없다: 모든 타입을 명시적으로 넘긴다. 이런 점이 dhall을 이런 용도에 적합하게 만든다.
여기까지 왔다면 축하한다! 이제 여러분은 ADT와 GADT의 달인이다. 물론 언어마다 다르고, 언어에 따라 위 해법들을 손봐야 할 때도 많다. 프로그램이 매우 복잡해지면, 인체공학적으로 견디기 힘들어질 가능성도 있다.
하지만 적어도, 여러분이 선택한(혹은 어쩔 수 없이 사용 중인) 언어에 여러분의 haskell 원칙, 기법, 기준, 실천, 그리고 브레인로트를 가져와 보도록 상상력을 자극했길 바란다.
그리고 여기서 다루지 않은 언어에 이런 것을 들여놓는 흥미로운 방법(혹은 새로운 기법/패턴)을 발견한다면, 꼭 알려 주시라! 정말 듣고 싶다.
다음에 또 만날 때까지, 즐거운 "Haskelling"!
이 글들을 연구하고 쓰는 데 시간을 쓸 수 있도록 응원해 주는 멋진 커뮤니티에 늘 감사한다. patreon의 “Amazing” 레벨 후원자인 Josh Vera님께 특별한 감사를 드린다! :)