Flux와 List의 Algebra 구조는 같다

저는 NgRx를 쓰면서 처음 플럭스(Flux)구조를 접했어요. 플럭스의 첫인상은 상당히 복잡해보였죠. 하지만 가만보니 대수구조(algebraic structure)가 리스트(list) 자료구조와 같다는걸 알아챘어요. 그로써 복잡해보이는 구조를 더 간단한 구조로 투영해서 볼 수 있었고 결과적으로 더 쉽고 빠르게 적응할 수 있었어요. 저는 이번 글에서 바로 이 경험을 공유해볼거에요.

글을 읽기 위한 배경 지식

약간의 수학: Group 정도만 아셔도 돼요.
Flux(선택): 마지막에 Flux를 예로 들거라서 아시면 좋아요.

프로그래머에게 Algebra는 무엇인가?

Algebra A 를 만족하는 타입 T의 정의는 "T를 Algebraic하게 생성하는 방법" 을 물어보고, 답을 eval이라는 함수로 옮겨 적는것과 같아요. Group 을 예로 하나 들어볼게요. 그룹의 수학적 정의는 다음과 같아요.

$$\begin{aligned} &\text{Group } T \\ &\bullet : T \times T \rightarrow T \\ &T^{-1} : T \rightarrow T \\ &id : () \rightarrow T \\ &t_1 \bullet (t_2 \bullet t_3) = (t_1 \bullet t_2) \bullet t_3 \\ &T^{-1} \bullet T = T \bullet T^{-1} \\ &t \bullet id() = id() \bullet t = t \end{aligned}$$

이제 위에서 말한 질문을 스스로에게 던져보세요. T 를 algebraic하게 생성하는 방법은 뭐가있을까요? 그룹의 정의에 따르면 다음과같은 세가지 방법밖에 없어요.

• binary 연산자 $\bullet : T^2 \rightarrow T$
• unary 연산자 $inverse: T \rightarrow T$
• nullary 연산자 $id: 1 \rightarrow T$

identty 오브젝트를 nullary 함수로 표현한 부분을 주의해주세요. id 의 도메인을 1로 표현한 이유는 타입은 집합이고, 집합의 유일한 identification 은 cardinality(element 의 갯수)이기 때문에 단순히 숫자로 표현하는것에 전혀 문제가 없기 때문이에요.

셋을 piecewise 함수로 합친 $eval: T^2 + T + 1$ 함수가 바로 Algebra의 정의에요.

예로 그룹 Mod 5와 $\mathbb{Z}$ (Integers) 를 각각 eval로 정의해볼게요.

Mod N의 eval 과 $\mathbb{Z}$ 의 eval의 signature 는 둘다 $T^2 + T + 1 \rightarrow T$ 로 그룹이기 때문에 같아요. 하지만 구현은 다른 Algebra이기 때문에 다르죠.

Mod N의 eval 은 $x \bullet y$ 을 $x + y$ 의 결과값으로(여기서 + 는 Mod N의 덧셈), $x^{-1}$ 는 $-x$ 의 결과값으로, $\mathbb{1}$ 는 $\overline{0}$ 으로 맵핑하고 $\mathbb{Z}$ 의 eval은 $x \bullet y$ 을 $x + y$ 의 결과값으로, $x^{-1}$ 을 $-x$ 의 결과값으로, $\mathbb{1}$ 를 $0$ 로 맵핑해요.

리스트 Algebra

이제 Algeba에 대해서 조금 알았으니 좀더 실용적으로 접근해봅시다. 프로그래머들이 의식하진 않지만 매일매일 쓰는 Algebra가 하나 있어요. 바로 List E 에요. 어떤 타입 E의 List 도 그룹과 같은 Algebraic 구조에요. List E를 Algebra로 정의하기위해 그룹에서 했던것처럼 다음과같은 질문으로 시작해 볼게요. List E를 어떻게 algebraic 하게 생성할 수 있을까요? 프로그래머들은 List를 정의할때 필수로 다음 두 생성자를 먼저 만들어요.

1. 비어있는 리스트
2. 기존 리스트 에 새로운 e 가 추가된 리스트

이 두 생성자를 operator로 사용해서 위 Group처럼 정의해볼게요.

$$\begin{aligned} & \text{List E } T \\ & id : \textbf{1} \rightarrow T \\ & \bullet : e \times T \rightarrow T \end{aligned}$$

여기서 $e$ 는 타입 E의 cardinality 를 뜻하는 상수에요.

첫번째 생성자는 $id$ 에 해당하고 두번째 생성자는 $\bullet$ 에 해당해요. List E에 conform 할 algebra의 eval함수의 signature 는 $eT + 1 \rightarrow T$ 가 되겠죠.

우리는 List E에 conform 하는 두개의 algebra를 만드거에요. 하나는 $id$ 가 0으로 evaluate되고 $e \bullet t$ 는 $1 + t$ 로 evaluate 되게끔 구현하고 Len 이라고 부를거에요. 여기서 E는 어떠한 타입이든 될 수 있고 T는 이미 $id$ 가 0으로 evaluate 한다는 점에서 Int로 결정된거에요(type inference). 다른 하나는 $id$ 가 $0_E$ 으로 evaluate되고 $e \bullet t$ 는 $e + t$ 로 evaluate 되게끔 구현하고 Sum이라고 부를거에요. 여기서 $0_E$ 의 의미는 타입 E의 0에 해당하는 element를 뜻하고요 마찬가지로 $id$ 의 결과 타입이 E라는 점에서 이미 T도 E라는 점이 결정이 된거에요.

신기하게도 Sum Algebra의 evaluation은 리스트에 있는 모든 E의 합이되고, Len Algebra의 evaluation은 리스트가 포함하는 element의 갯수 (리스트의 길이)가 돼요. 둘의 eval함수의 구현을 들여다 보고 어떻게 이럴 수 있는지 알아볼게요.

Len의 eval은 다음과 같아요.

$$eval_{\text{len}}(x) = \begin{cases} 1 + t & \text{if $x = (e, t)$} \\ 0 & \text{else} \end{cases}$$

Sum의 eval은 다음과 같아요.

$$eval_{\text{sum}}(x) = \begin{cases} e + t & \text{if $x = (e, t)$} \\ 0 & \text{else} \end{cases}$$

두 Algebra 모두 두가지 정보를 이용해서 스스로를 정의해요. 하나는 초기값이고, 다른 하나는 리스트 element의 타입 E와 결과 타입 T를 받는 evaluation 함수 $E \times T \rightarrow T$ 죠. 뭔가 익숙하지 않나요?

class Foldable t where
    foldr :: (a -> b -> b) -> b -> t a -> b

프로그래머들이 매일매일 쓰는 fold (aka reduce) 함수가 바로 두가지 정보를 받아서 List E Algebra를 구현해주는 함수였습니다! (정확히 말하면 오른쪽부터 접는 foldr/reduceR) fold 를 쓸때마다 프로그래머는 항상 새로운 Algebra를 정의하고 있었던거죠.

Flux

Redux나 NgRx를 써보신 분들중 아마 List와 비슷하다는 점을 눈치채신 분들도 계실거에요. 특히나 초기 App State를 설정해주는 부분과 새로운 App State를 계산하는 부분을 reducer라고 불리는 부분이 리스트가 reduce를 사용하는것과 많이 일치하죠. 각각 다른 파라메터를 받는 세개의 dispatcher를 가진 Flux를 정의해볼게요:

$$\begin{gathered} \begin{aligned} & \text{Flux } AppState \\ & initialState : \textbf{1} \rightarrow AppState \\ & dispatch1 : \textbf{1} \times T \rightarrow T \\ & dispatch2 : A \times T \rightarrow T \\ & dispatch3 : B \times C \times T \rightarrow T \\ \end{aligned} \\ \cdot \cdot \cdot \end{gathered}$$

이 Algebra의 eval 함수는 다음과 같겠죠:

$$eval:1 + T + aT + bcT \rightarrow T$$

타입은 집합이잖아요? distributive 성질을 이용해서 하나로 합치면:

$$eval:1 + (1 + a + bc)T \rightarrow T$$

List E Algebra 로 바꿀 수 있어요. Flux도 결국 List Algebra 였던거죠.

위 내용은 F-Algebra라는 수학적 이론을 바탕으로 쓰여졌어요. F-Algebra에 대해 공부해보고싶다면 여길 추천:

Category Theory for Programmers: F-Algebra

전반적인 카테고리 이론을 공부하고 싶다면 여길 추천:

Category Theory for Programmers

Math3ma: Category Theory