제 2부에서는 함수적 설계의 원리를 이용해서 몇 가지 라이브러리를 작성해 보았는데 제 3부에서는 좀 더 넓은 관점에서 함수적 프로그래밍에 등장하는 공통의 패턴을 살펴볼 것이다. 즉, 그런 라이브러리들의 공통 구조를 서술하는 추성적인 이론으로 통합해 볼 것이다. 이런 종류의 추상화는 중복 코드의 제거라는 실용적인 이득으로 직접 이어진다. 그런 추상화는 중복 코드의 제거라는 실용적인 이득으로 직접 이어진다. 실제 프로그램에서 사용할 수 있는 클래스나 인터페이스, 함수의 형태로 실체화할 수 있기 때문이다. 그러나 주된 이득은 개념적 통합(conceptual integration)이다. 서로 다른 문맥의 서로 다른 해법들 사이에서 공통의 구조를 인식한다면, 그런 구조의 인스턴스들을 모두 하나의 정의로 통합하고 그것에 이름을 부여 할 수 있다.
경험이 쌓여 문제의 일반적 형태만 봐도 이거"모나드(monad)처럼 보이는데!? 라고 말한다면 해법의 형태를 거의 찾아 낸 셈이다(^^;)
-
이번장에서 논의할 내용
-
순수 대수적(purely algebraic) 구조
-
이번 장에서 논의할 모노이드의 유용함 2가지
-
문제를 병렬로 계산할 수 있는 여러 조각으로 나눌 수 있어서 병렬 계산이 쉽다.
-
간단한 계산을 조립해서 더 복잡한 계산을 만드는 데 유용하다.
-
문자열 연결의 대수를 생각해 보자. 문자열 연결('덧셈') 연산 "foo" + "bar"의 결과는 "foobar"이고, 이러한 연산의 항등원(identiy element)은 빈 문자열이다. 즉, (s + "")나 ("" +s)의 결과는 항상 s이다.
더 나아가서 (r + s + t)로 문자열 세개로 연결하는 연산은 결합법칙(associative law)을 만족한다. 즉, (r + s) +t) = (r + (s +t )) 이다.
정수 덧셈에서 덧셈의 항등원은 0 , 결합법칙 성립
s가 0 이면 (1 + 2) + s) = 1 + ( 2 + s) = 3
정수 곱셈에서 곱셈의 항등원은 1 , 결합법칙 성립
s가 1 이면 ( 1 * 2) * s ) = 1 * ( 2 * s ) = 2
&&연산의 항등원은 true, 결합법칙 성립
s 가 true 이면 if ( 3>1 && s ) = if ( 3<1 && s ) = false
|| 연산의 항등원은 false를 갖는다. , 결합법칙 성립
s 가 false 이면 if ( 5< 1 s || ) = if ( 5 > 1 || s) = true
위와 같은 종류의 대수를 지칭하는 용어가 모노이드 이다. 결합법칙과 항등법칙을 합쳐서 모노이드 법칙이라고 부른다.
-
어떤 형식 A
-
A형식의 값 두 개를 받아서 하나의 값을 산출하는 결합적 이항 연산 op. 임의의 x: A, y: A, z: A에 대해 op(op(x,y), z) = op (x, op(y,z))가 성립한다.
-
그 연산의 항등원값 zero: A. 임의의 x: A에 대해 op(x, zero) == x이고 op(zero, x) == x이다.
trait Monoid[A] {
def op(a1: A, a2: A): A // op(op(x,y), z) == op(x, op(y,z))를 만족한다.
def zero: A // op(x, zero) == x 와 op(zero, x) == x를 만족한다.val stringMonoid = new Monoid[String] = {
def op(a1: String, a2: String) = a1 + a2
val zero = ""
}def listMonoid[A] = new Monoid[List[A]] {
def op(a1: List[A], a2: List[A]) = a1 ++ a2
val zero = Nil
}모노이드 법칙을 만족한다는 점 말고는 Monoid의 여러 인스턴스에 공통점이 별로 없음을 주목하자. 모노이드는 하나의 형식과 모노이드 연산들, 그리고 법칙들의 집합이다. 다른 말로 모노이드는 대수일 뿐이다. 물론 독자가 여러 구체적인 인스턴스들을 보면서 이와는 다른 어떤 직관을 얻을 수도 있지만, 그러한 직관은 부정확 할 가능성이 크다. 독자가 이후에 만날 모든 모노이드가 반드시 그 직관과 부합하리라는 보장은 없다.
모노이드 형식과 모노이드 인스턴스를 가진 형식의 구분과 관련하여 프로그래밍과 수학의 어법에 미묘한 차이가 있다. 프로그래머들은 Monoid[A]형식의 인스턴스가 곧 모노이드라고 생각하기 쉽다. 그러나 이는 정확한 어법이 아니다. 실제로는, 형식과 해당 법칙들을 만족하는 인스턴스가 모노이드다. 좀 더 엄밀한 표현은 "형식 A는 Monoid[A] 인스턴스에 정의된 연산들에 의해 하나의 모노이드를 형성한다(form)"이다. 덜 엄밀하게 말하면 "형식 A가 곧 모노이드이다"라고 말할 수 있으며, 또는 "형식 A는 모노이드적(monoidal)이다" 라고 말할 수도 있다. 어떤 경우든, Monoid[A] 인스턴스는 이러한 사실의 한 증거일 뿐이다.
모노이드는 형식 A와, 관련 법칙들을 만족하는 Monoid[A]의 구현이다. 좀 더 간결하게 말하면, 모노이드는 하나의 형식이되 그 형식에 대해 결합법칙을 만족하며 항등원(zero)을 가진 이항 연산(op)이 존재하는 형식이다.
모노이드는 목록과 밀접한 관계가 있다. List에 대한 foldLeft, foldRight를 통해 알아보자
def foldRight[B](z: B)(f: (A,B) => B): B
def foldLeft[B](z: B)(f: (B,A) => B): B
// 만약 A와 B 가 같은 형식이라면 ?
def foldRight[A](z: A)(f: (A,A) => A): A
def foldLeft[A](f: (A,A) => A): A모노이드의 구성요소들은 이 인수 형식과 딱 들어맞는다. 문자열들의 목록이 있을 떄, 그냥 stringMonoid의 op와 zero만 넘겨주면 모노이드로 그 목록을 축약해서(접어서) 문자열들을 모두 하나로 연결 할 수 있다.
val words = List("Hic", "Est", "Index")
words: List[String] = List(Hic, Est, Index)
val s = words.foldRight(stringMonoid.zero)(stringMonoid.op)
s: String = HicEstIndex
val t = words.foldLeft(stringMonoid.zero)(stringMonoid.op)
t: String = HicEstIndex모노이드를 이용한 접기에서 foldLeft를 사용하느냐, foldRight를 사용하느냐는 중요하지 않다. (물론 둘다 꼬리 재귀로 구현되어 있다고 가정 했을때이다.) 둘다 같은 결과를 내는데, 이는 다름 아닌 결합법칙과 항등법칙이 성립하기 때문이다. 왼쪽 접기는 연산들을 왼쪽에서 있는 항등원과 함께 왼쪽에서 결합하는 반면 오른쪽 접기는 오른쪽의 항등원과 함께 오른쪽으로 결합한다.
words.foldLeft("")(_ + _) == (("" + "Hic") + "Est") + "Index"
words.foldRight("")(_ + _) == "Hic" + (("Est") + ("Index" + ""))이를 일반화해서, 모노이드로 목록을 접는 일반적 함수 concatenate를 만들 수도 있다.
def concatenate[A](as: List[A], m: Monoid[A]): A =
as.foldLeft(m.zero)(m.op)그런데 목록의 원소 형식이 Monoid 인스턴스와는 부합하지 않을 수도 있다. 그럴 때에는 map을 이용해서 형식을 맞춰 주면 된다.
def foldMap[A,B](as: List[A], m: Monoid[B])(f: A => B): B접을 수 있는 자료구조
-
List
-
Tree
-
Stream
-
IndexedSeq
접을 수 있는 자료구조를 처리해야 하는 코드를 작성할 때
-
구체적인 형식(자료구조의 형태, 지연 여부, 효율적인 임의 접근 능력 등)을 신경 쓸 필요가 없다.
-
foldLeft, foldRight, foldMap을 사용한다.
trait Foldable[F[_]] {
def foldRight[A,B](as: F[A])(z: B)(f: (A,B) => B): B
def foldLeft[A,B](as: F[A])(z: B)(f: (B,A) => B): B
def foldMap[A,B](as: F[A])(f: A => B)(mb: Monoid[B]): B
def concatenate[A](as: F[A])(m: Monoid[A]): A =
foldLeft(as)(m.zero)(m.op)
}-
F[_]: 밑줄은 F가 형식이 아니라 하나의 형식 인수를 받는 형식 생성자(type constructor)임을 나타낸다.
-
Foldable: 다른 형식 생성자를 인수로 받는 형식 생성자 → 고차 형식 생성자(higher-order type constructor) or 상위 종류 형식(higher-kinded type)
모노이드의 진정한 위력은 그 합성 능력에서 비롯된다.
-
형식 A와 B가 모노이드이면 튜플 형식 (A, B)(이것을 두 모노이드의 곱(product)이라고 부른다.) 역시 모노이드임을 뜻한다.
-
자료구조에 담긴 요소들의 형식들이 모노이드를 형성한다면 그 자료구조 자체도 흥미로운 모노이드를 형성하기도 한다.
-
ex) 키-값 Map의 값 형식이 모노이드면 그런 Map들을 병합하기 위한 모노이드가 존재한다.
목록 10.1 키-값 Map들의 병합
def mapMergeMonoid[K,V](V: Monoid[V]): Monoid[Map[K, V]] =
new Monoid[Map[K, V]] {
def zero = Map[K,V]()
def op(a: Map[K, V], b: Map[K, V]) =
(a.keySet ++ b.keySet).foldLeft(zero) { (acc,k) =>
acc.updated(k, V.op(a.getOrElse(k, V.zero),
b.getOrElse(k, V.zero)))
}
}이 간단한 조합기를 이용하면 좀 더 복잡한 모노이드를 상당히 수월하게 조립할 수 있다.
scala> val M: Monoid[Map[String, Map[String, Int]]] =
| mapMergeMonoid(mapMergeMonoid(intAddition))
M: Monoid[Map[String, Map[String, Int]]] = $anon$1@21dfac82이에 의해, 추가적인 프로그래밍 없이도 모노이드를 이용해서 중첩된 표현식들을 조합할 수 있게 된다.
scala> val m1 = Map("o1" -> Map("i1" -> 1, "i2" -> 2))
m1: Map[String,Map[String,Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 2))
scala> val m2 = Map("o1" -> Map("i2" -> 3))
m2: Map[String,Map[String,Int]] = Map(o1 -> Map(i2 -> 3))
scala> val m3 = M.op(m1, m2)
m3: Map[String,Map[String,Int]] = Map(o1 -> Map(i1 -> 1, i2 -> 5))-
여러 모노이드를 하나로 합성할 수 있다는 사실은 자료구조를 접을 때 여러 계산을 동시에 수행할 수 있음을 뜻한다.
-
ex) 목록의 평균을 구할 때, 다음과 같이 목록의 길이와 합을 동시에 구할 수 있다.
scala> val m = productMonoid(intAddition, intAddition)
m: Monoid[(Int, Int)] = $anon$1@8ff557a
scala> val p = listFoldable.foldMap(List(1,2,3,4))(a => (1, a))(m)
p: (Int, Int) = (4, 10)
scala> val mean = p._1 / p._2.toDouble
mean: Double = 2.5-
모노이드를 productMonoid와 foldMap을 이용해서 일일이 조립하는 것이 좀 번거롭다.
-
그 이유는 foldMap의 매핑 함수로부터 Monoid를 구축할 때 형식을 일일이 맞추어 주어야 하기 때문이다.
-
합성된 모노이드들을 조립하는 작업과 병렬화해서 하나의 path로 실행할 수 있는 계산을 훨ㄹ씬 더 편하게 정의할 수 있는 조합기 라이브러리를 만들면 된다.
-
웹 부록의 이번 장 참고자료 보세요.