2023-02-20-TIL
2023-02-20-TIL
Today I Learned
Category Theory
범주론(category theory)은 대상(object)과 그 사이의 화살표(arrow, 사상 morphism)로 구조를 다루는 수학 분야다. Bartosz Milewski의 『Category Theory for Programmers』는 범주의 본질을 합성(composition)이라고 설명한다. A에서 B로 가는 화살표와 B에서 C로 가는 화살표가 있으면 A에서 C로 가는 합성 화살표가 반드시 있어야 하고, 합성은 두 가지 성질을 만족해야 한다.
- 결합법칙:
h∘(g∘f) = (h∘g)∘f - 항등원: 모든 대상 A에는 자기 자신으로 가는 항등 화살표
id_A가 있고,f∘id_A = f,id_B∘f = f다.
프로그래밍에서는 타입을 대상, 함수를 화살표로 보면 그대로 들어맞는다. 함수 합성은 결합법칙을 만족하고, 항등 함수는 인자를 그대로 돌려주는 함수다. 함수형 프로그래밍이 작은 함수를 합성해 큰 프로그램을 만드는 방식이라는 점에서 범주론은 그 설계 원리를 설명하는 언어가 된다. 첫 번째 링크는 이 책의 비공식 PDF와 LaTeX 소스 저장소다.
- https://github.com/hmemcpy/milewski-ctfp-pdf
- https://namu.wiki/w/%EB%B2%94%EC%A3%BC%EB%A1%A0
- https://github.com/pilgwon/CategoryTheory
Functional Programming from Math
순수 함수는 보통 “같은 입력에 같은 출력”, “외부 상태를 바꾸거나 외부 상태에 영향받지 않음”이라는 두 특징으로 외운다. Evan Moon의 글은 순수 함수가 특별한 개념이 아니라 수학의 함수를 그대로 프로그래밍으로 옮긴 것일 뿐이라고 설명한다. 수학에서 함수는 정의역의 각 원소를 공역의 원소 하나에 대응시키는 관계이므로, 입력 말고 다른 것에 의존하거나 대응 외의 일을 할 여지가 없다. 위의 두 특징은 이 정의에서 자연스럽게 따라 나온다.
- https://evan-moon.github.io/2019/12/29/about-pure-functions/
- https://peter-cho.gitbook.io/book/2022/7/7_2
Monoid
모노이드는 집합 하나와 그 위의 이항 연산이 다음 두 법칙을 만족하는 구조다.
- 결합법칙:
(a op b) op c == a op (b op c) - 항등원: 모든
a에 대해a op e == e op a == a인 원소e가 있다.
정수와 덧셈(항등원 0), 정수와 곱셈(항등원 1), 문자열과 이어 붙이기(항등원 빈 문자열)가 모두 모노이드다. 『Functional Programming in Scala』 10장이 이 개념을 다룬다. 결합법칙이 성립하면 리스트를 어떻게 나눠서 접어도(fold) 결과가 같으므로 병렬로 계산한 뒤 합칠 수 있고, 항등원이 있으면 빈 리스트의 결과도 정의된다. 모노이드는 대상이 하나뿐인 범주로 볼 수도 있다.
1
2
3
4
5
6
7
8
9
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}
val intAddition = new Monoid[Int] {
def op(a1: Int, a2: Int) = a1 + a2
def zero = 0
}
- https://storyzero.gitbooks.io/functional-programming-in-scala/content/chapter10.html
- https://itchallenger.tistory.com/513
Monad
모나드는 값을 감싼 문맥(옵셔널, 리스트, 비동기 결과 등)에서 계산을 이어 붙이는 방법을 일반화한 구조다. 값을 문맥에 넣는 return(unit, pure)과, 감싼 값을 꺼내 다음 계산에 넘기는 >>=(bind, flatMap)으로 정의된다. HaskellWiki에 따르면 모든 모나드는 세 법칙을 만족해야 한다.
- 왼쪽 항등원:
return a >>= h는h a와 같다. - 오른쪽 항등원:
m >>= return은m과 같다. - 결합법칙:
(m >>= g) >>= h는m >>= (\x -> g x >>= h)와 같다.
자바의 Optional.flatMap, Stream.flatMap, CompletableFuture.thenCompose가 같은 모양이다. 법칙의 형태가 모노이드와 닮았는데, 범주론에서는 모나드를 자기 함자(endofunctor) 범주의 모노이드로 설명하기도 한다. 참고한 글이 이 연결을 범주론으로 풀어 간다.
- https://itchallenger.tistory.com/entry/%ED%95%A8%EC%88%98%ED%98%95-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EB%AA%A8%EB%82%98%EB%93%9C%EC%9D%98-%EB%AA%A8%EB%93%A0-%EA%B2%83-%EC%B9%B4%ED%85%8C%EA%B3%A0%EB%A6%AC-%EC%9D%B4%EB%A1%A0
SICP
『Structure and Interpretation of Computer Programs』는 MIT의 Harold Abelson과 Gerald Jay Sussman이 쓴 프로그래밍 교재로, Scheme으로 추상화, 고차 함수, 상태, 인터프리터 구현까지 다룬다. 흔히 “마법사 책”으로 불린다. 인사이트 출판사 블로그의 글은 한국어판 출간을 앞두고, 이 책에 대한 평가가 생각할 거리가 많은 명저라는 쪽과 배울 것 없이 시간만 쓰는 괴상한 책이라는 쪽으로 반반 갈린다고 소개한다.
- https://blog.insightbook.co.kr/2007/10/16/%EB%84%88%EB%AC%B4%EB%82%98-%EC%9D%B4%EC%83%81%ED%95%9C-%EC%B1%85-%EB%B3%B4%EB%8B%A4%EA%B0%80-%EB%91%90-%EB%B2%88%EC%9D%B4%EB%82%98-%EC%A7%91%EC%96%B4-%EB%8D%98%EC%A7%84-%EC%B1%85-sicp/
댓글
아직 댓글이 없습니다