[FP In Scala] 모나드

모노이드: 완전히 추상적이고 순수한 대수적인(결합법칙 + 항등법칙) 인터페이스 -> 다형적 함수 작성 가능 -> 문제를 여러 조각으로 나눠 병렬 계산 용이 -> 복잡한 계산 생성 가능

 

모노이드와 비슷한 사고방식을 이어나가며 중복된 코드를 추출하는 문제에 적용해 그 과정에서 새로운 추상 인터페이스 Functor와 Monad를 알아본다.

1. Functor: map 함수의 일반화

Gen 형식, Parser 형식, Option 형식에 대한 map 함수의 서명

def map[A,B](ga: Gen[A])(f: A => B): Gen[B]

def map[A,B](pa: Parser[A])(f: A => B): Parser[B]

def map[A,B](oa: Option[A])(f: A => B): Option[B]

 

이 형식 서명들의 차이는 구체적인 자료 형식(Gen, Parser, Option)뿐이다. 이 점을 "map을 구현하는 자료 형식"이라는 개념을 대표하는 스칼라 특질(trait)로 표현할 수 있다.

 

trait Functor[F[_]] {
	def map[A, B](fa: F[A])(f: A => B): F[B]
}

이 특질(trait)은 map을 형식 생성자(형식에 적용해서 형식을 생성하는 수단) F[_]로 매개변수화한다. 

 

특정 F[_]를 Gen이나 Parser 같은 특정한 형식으로 고정하는 대신, 이 Functor 특질은 F를 하나의 형식 매개변수로 두어서 프로그래머가 임의로 지정할 수 있게 한다. 

 

다음은 List를 위한 Functor 인스턴스.

val listFunctor = new Functor[List] {
	def map[A, B](as: List[A])(f: A => B): List[B] = as map f
}

List(또는 Option, F) 같은 형식 생성자를 가리켜 함수자(functor)라고 부른다. 

Functor[F] 인스턴스는 F가 실제로 하나의 functor임을 증명하는 증거가 된다.

 

이러한 추상으로 할 수 있는 것: 인터페이스의 연산들을 순수하게 대수적인 방식으로 다루는 것만으로도 유용한 함수를 발견할 수 있다.

예) F가 하나의 함수자이고 F[(A, B)]가 주어졌을 때, F를 그 쌍(pair)에 분배해서 (F[A], F[B])를 얻을 수 있다.

 

trait Functor[F[_]] {
	def distribute[A, B](fab: F[(A, B)]): (F[A], F[B]) =
    	(map(fab)(_._1), map(fab)(_._2))
}

 

List에 distribute를 적용하면 길이가 같은 목록 두 개가 산출된다. 하나는 A로만 이루어진 목록이고, 하나는 B로만 이루어진 목록이다.

이 연산을 unzip이라 부르기도 한다. 

 

핵심은 목록뿐만 아니라 모든 함수자에 대해 작동하는 unzip 함수를 작성한 것이다.

 

곱(product)에 대한 이러한 연산이 가능하다면, 합이나 쌍대곱(coproduct)에 대해 이와 반대되는 연산들 만들 수 있을 것이다.

def codistribute[A,B](e: Either[F[A], F[B]]): F[Either[A, B]] =
  e match {
    case Left(fa) => map(fa)(Left(_))
    case Right(fb) => map(fb)(Right(_))
  }

Gen에 대해 codistribute가 어떤 의미일까? 

A에 대한 생성기나 B에 대한 생성기가 있다면, 둘 중 어떤 것이 주어지느냐에 따라 A나 B 중 하나를 생성하는 생성기를 만들 수 있다.

 

Functor 추상 인터페이스에만 근거해서 아주 일반적이고 잠재적으로 유용한 조합기 두 개를 만들어 냈다.

이 조합기들을 map의 구현이 가능한 임의의 형식에 재사용할 수 있다.

 

1.1 Functor의 법칙들

Functor 같은 추상을 만들 때에는 어떤 추상 메서드들이 필요한지 고민할 뿐만 아니라 구현들이 지켜야 할 법칙(수학이 이미 명시한 법칙)들도 고민해야 한다. 그 이유는 

 

• 법칙은 인터페이스의 의미론을, 해당 대수를 인스턴스들과는 독립적으로 추론할 수 있을 정도의 새로운 수준으로 끌어올리는 데 도움이 된다. 예를 들어 Monoid[A]와 Monoid[B]의 곱으로 Monoid[(A, B)]를 만든다고 할 때, 모노이드 법칙 덕분에 이 융합된 모노이드 연산 역시 결합법칙을 만족한다는 결론을 내릴 수 있다. A와 B에 대해 알지 못해도 이러한 결론을 얻을 수 있다.
• Functor 같은 추상 인터페이스의 함수들로부터 조합기들을 파생할 때 법칙들에 의존하는 경우가 많다.

map(x)(a => a) == x

이는 자료구조 x에 항등 함수를 사상하는 것 자체가 하나의 항등 함수이어야 한다는 것을 의미한다. 

 

이 법칙은 map(x)가 x의 "구조를 보존해야 한다"는 요구사항을 반영한다.

구현이 이 법칙을 만족하려면, 이를테면 예외를 던지거나, List의 첫 요소를 제거하거나, Some을 None으로 바꾸는 등의 행동을 해서는 안 된다. map은 오직 자료구조의 요소들만 수정해야 하며, 구조 자체의 형태는 그대로 두어야 한다. 

 

이 법칙이 List와 Option, Par, Gen을 비롯한, map을 정의하는 형식들 대부분에 대해 성립한다.

 

이러한 구조의 보존의 구체적인 예로, 앞에서 정의한 distribute와 codistribute를 생각해 보자. 

 

def distribute[A,B](fab: F[(A, B)]): (F[A], F[B])

def codistribute[A,B](e: Either[F[A], F[B]]): F[Either[A, B]]

F가 functor라는 사실 외에는 F에 대해 아는 바가 없지만, 이 법칙은 반환된 값들이 그 인수들과 같은 형태임을 보장해 준다. 

 

distribute에 '쌍들의 목록'이 입력되었다면, distribute가 돌려주는 '목록들의 쌍'은 그 입력과 같은 길이일 것이며, 해당 요소들은 같은 순서로 나타날 것이다. 이런 종류의 대수적 추론은 프로그래머의 시간을 크게 절약해 줄 수 있다. 그런 속성마다 개별적인 검사를 작성할 필요가 없기 때문이다.

 

2. 모나드: flatMap 함수와 unit 함수의 일반화

Functor는 라이브러리들에서 추출할 수 있는 여러 추상 중 하나일 뿐이다. 

Functor가 그리 매력적이지 않을 수 있는데, map만으로 정의할 수 있는 유용한 연산이 별로 많지 않기 때문이다.

 

이번에는 Monad를 살펴보겠다.

이 인터페이스를 통해 한 번만 정의해 두면 코드의 중복을 크게 줄일 수 있는 유용한 연산들을 많이 만들어 낼 수 있다. 또한 이 인터페이스는 또한 라이브러리가 기대한 대로 작동하는지 추론하는데 사용할 수 있는 법칙들도 가지고 있다.

 

인수 두개를 받는 함수를 "승급시키는" map2 함수.

Gen, Parser, Option에 대해 map2 함수를 다음과 같이 구현할 수 있다.

 

// 무작위 생서이 fa와 fb를 실행하고 그 결과들을 함수 f로 조합하는 무작위 C 생성기를 만든다.
def map2[A,B,C](
      fa: Gen[A], fb: Gen[B])(f: (A,B) => C): Gen[C] =
  fa flatMap (a => fb map (b => f(a,b)))


// 파서 fa와 fb의 결과들을 함수 f로 조합해서 C를 산출하는 파서를 만든다. 
def map2[A,B,C](	
      fa: Parser[A], fb: Parser[B])(f: (A,B) => C): Parser[C] =
  fa flatMap (a => fb map (b => f(a,b)))


// 두 Option 모두 값이 잇으면 그것들을 f로 조합해서 돌려주고 그렇지 않으면 None을 돌려준다.
def map2[A,B,C](	
      fa: Option[A], fb: Option[B])(f: (A,B) => C): Option[C] =
  fa flatMap (a => fb map (b => f(a,b)))

이 함수들은 공통점이 없어 보이는 서로 다른 자료 형식에 작용하지만, 구현은 모두 동일하다. 다른 점은 함수가 적용되는 구체적인 자료 형식뿐이다.

이는 이들이 좀 더 일반적인 패턴의 특정 사례일 뿐이라는 점을 확인해 준다. 이러한 사실을 활용한다면 코드의 중복을 크게 줄일 수 있을 것이다. 

2.1 Monad 특질

Parser와 Gen, Par, Option 등 살펴본 여러 자료 형식들을 하나로 묶는 공통점은, 이들이 모나드라는 것이다.

 

Functor와 Foldable에 대해 했던 것처럼, map2와 기타 여러 함수를 구체적인 자료 형식마다 중복해서 정의하는 대신 모나드를 대표하는 스칼라 특질에서 한 번만 정의해 두고 재사용하는 것일 더 좋을 것이다.

 

추상 인터페이스를 최소한의 기본수단들의 집합으로 정련한다.

 

일단 임시로 Mon이라는 새 trait을 정의하고 map2를 정의한다.

trait Mon[F[_]] {
  def map2[A,B,C](fa: F[A], fb: F[B])(f: (A,B) => C): F[C] =
    fa flatMap (a => fb map (b => f(a,b)))	
}

이 구현은 기존의 map2 구현에서 Parser, Gen, Option을 서명에 있는 Mon[F] 인터페이스의 다형적 F(형식 생성자 인수의 이름을 F로 한 것음 임의다. Foo, blah2라고 해도 된다. 그러나 F, G, H와 같이 대문자 하나로 된 이름을 부여하는 것이 관례이다.)로 대체했다.

 

그런데 이 다형적 문맥에서 이 구현은 아직 컴파일되지 않는다. 이 문맥에서는 F에 대해 아무것도 알지 못하므로, F[A]에 대해 flatmap이나 map을 적용하는 방법도 모를 수밖에 없다.  

 

map과 flatmap을 Mon 인터페이스에 추가하고 추상적인 상태로 남겨두자. 

 

trait Mon[F[_]] {
  def map[A,B](fa: F[A])(f: A => B): F[B]
  def flatMap[A,B](fa: F[A])(f: A => F[B]): F[B]

  def map2[A,B,C](
      fa: F[A], fb: F[B])(f: (A,B) => C): F[C] =
    flatMap(fa)(a => map(fb)(b => f(a,b)))	
}

 

이제 이 trait을 컴파일할 수 있다. Mon[List], Mon[Parser], Mon[Option] 같은 인스턴스들의 정의로 넘어가지 전에, 먼저 기본수단들의 집합을 정련할 수 있는지 살펴본다. 

 

현재 정의된 기본수단은 map과 flatmap이고, 이 둘로부터 map2를 파생할 수 있다.

 

그런데 map과 flatmap이 최소한의 기본수단일까? map2를 구현하는 자료 형식에는 항상 unit 함수가 있다. 

map은 flatmap과 unit을 통해서 구현 가능

 

def map[A,B](f: A => B): Gen[B] =
  flatMap(a => unit(f(a)))

따라서 최소한의 기본수단 집합은 unit과 flatMap이어야 한다. 

 

이제부터 이 함수들이 정의되어 있는 모든 자료 형식을 하나의 개념으로 묶는다.

그러한 개념을 대표하는 trait의 이름을 Monad라고 한다.

 

Monad trait은 추상 함수 flatMap과 unit으로 구성, map과 map2의 기본 구현을 제공.

 

trait Monad[F[_]] extends Functor[F] {	
  def unit[A](a: => A): F[A]
  def flatMap[A,B](ma: F[A])(f: A => F[B]): F[B]

  def map[A,B](ma: F[A])(f: A => B): F[B] =
    flatMap(ma)(a => unit(f(a)))
  def map2[A,B,C](ma: F[A], mb: F[B])(f: (A, B) => C): F[C] =
    flatMap(ma)(a => map(mb)(b => f(a, b)))
}

 

* 모나드라는 용어: FlatMappable, Unicorn, Bicycle이라고 할 수도 있다. 그러나 모나드라고 불리는 이유는 범주론에서 비롯되었다. 모나드는 의도적으로 모노이드와 비슷하게 만들어진 용어이며 두 개념 사이에는 깊은 연관 관계가 존재한다. 

 

이를 다시 구체적인 자료 형식과 연관시키는 한 예로, Gen을 위한 Monad 인스턴스를 구현.

object Monad {
  val genMonad = new Monad[Gen] {
    def unit[A](a: => A): Gen[A] = Gen.unit(a)
    def flatMap[A,B](ma: Gen[A])(f: A => Gen[B]): Gen[B] =
      ma flatMap f
  }
}

unit과 flatMap만 구현하면 map은 저절로 생긴다. map과 map2는 Monad의 인스턴스를 제공할 수 있는 모든 자료 형식에 대해 한 번만 구현하면 된다. 

map과 map2 뿐만 아니라 이런 식으로 구현해 두면 되는 함수들이 많이 있다.

 

Par, Parser, Option, Stream, List에 대한 모나드 인스턴스 구현.

object Monad {
  val genMonad = new Monad[Gen] {
    def unit[A](a: => A): Gen[A] = Gen.unit(a)
    override def flatMap[A,B](ma: Gen[A])(f: A => Gen[B]): Gen[B] =
      ma flatMap f
  }

  val parMonad = new Monad[Par] {
    def unit[A](a: => A) = Par.unit(a)
    override def flatMap[A,B](ma: Par[A])(f: A => Par[B]) = Par.flatMap(ma)(f)
  }

  def parserMonad[P[+_]](p: Parsers[P]) = new Monad[P] {
    def unit[A](a: => A) = p.succeed(a)
    override def flatMap[A,B](ma: P[A])(f: A => P[B]) = p.flatMap(ma)(f)
  }

  val optionMonad = new Monad[Option] {
    def unit[A](a: => A) = Some(a)
    override def flatMap[A,B](ma: Option[A])(f: A => Option[B]) = ma flatMap f
  }

  val streamMonad = new Monad[Stream] {
    def unit[A](a: => A) = Stream(a)
    override def flatMap[A,B](ma: Stream[A])(f: A => Stream[B]) = ma flatMap f
  }

  val listMonad = new Monad[List] {
    def unit[A](a: => A) = List(a)
    override def flatMap[A,B](ma: List[A])(f: A => List[B]) = ma flatMap f
  }

3. 모나드적 조합기

sequence 조합기와 traverse 조합기

  def sequence[A](lma: List[F[A]]): F[List[A]] =
    lma.foldRight(unit(List[A]()))((ma, mla) => map2(ma, mla)(_ :: _))

  def traverse[A,B](la: List[A])(f: A => F[B]): F[List[B]] =
    la.foldRight(unit(List[B]()))((a, mlb) => map2(f(a), mlb)(_ :: _))

 

listOfN:

• Gen과 Parser에 대한 조합기.
• parser 또는 generator를 n번 되풀이해서 그 길이의 입력을 인식하는 파서 또는 그 개수만큼의 목록들을 생성하는 generator
• 이 조합기를 모나드 특질에 추가해서 모든 모나드 F에 대해 구현할 수 있다.
• listOfN 대신 replicateM과 같이 일반적인 이름으로 명명.

def replicateM[A](n: Int, ma: F[A]): F[List[A]] =
  sequence(List.fill(n)(ma))

val testReplicateMList = List(1, 2, 3)
println("replicateM of listMonad: ", listMonad.replicateM(2, testReplicateMList))

: (replicateM of listMonad: ,List(List(1, 1), List(1, 2), List(1, 3), List(2, 1), List(2, 2), List(2, 3), List(3, 1), List(3, 2), List(3, 3)))

product:

• 주어진 생성기 두 개로 쌍들을 생성하는 하나의 생성기를 돌려준다.
• 임의의 모나드 F에 대한 product

def product[A,B](ma: F[A], mb: F[B]): F[(A, B)] = map2(ma, mb)((_, _))

 

함수들을 가지고 놀면서 여러 가지로 실험하자.