Non-deterministic
함수형 프로그래밍 자료를 보다보면, 특히 모나드나 펑터 관련 자료를 보면 non-deterministic 알고리즘 얘기가 나온다. 처음에는 뭔가 대단한 것인가 싶었지만 결국 어떤 함수 f가 있을 때 a -> b 가 아니라 a -> [b] 처럼 여러 개의 결과를 내놓는 경우를 말한다. 사실 리스트 혹은 배열은 그 자체를 결과물로 볼 수 있는데, 이것을 특정 b가 아닌 여러 개의 b라는 식으로 관점을 바꾸어 비결정적 알고리즘이라고 하는 것이다.
비결정적 알고리즘은 대개 리스트 모나드로 처리된다. 여기서 간단하지만 적용 예를 하나 살펴보자.
LeetCode 문제 중에 Letter Combinations of a Phone Number라는 것이 있다. 전화 번호가 주어지면 다이얼패드의 숫자마다 매핑된 알파벳으로 표현 가능한 모든 문자열을 찾는 문제다. “2”번 키에 “abc”, “3”번 키에 “def”가 매핑되어 있으니 “23” 번호로 “ad”, “ae”, “af”, “bd”, “be”, .. 등의 영문자열이 표현 가능하다. 이 조합을 모두 찾는 문제다.
이 문제는 입력된 전호번호마다 매핑된 알파벳을 찾고, 가능한 조합으로 문자열을 붙여나가면 된다. 대략 다음과 같은 3중 루프로 풀 수 있다.
그냥 배열/문자열 이라는 관점으로는 위와 같은 imperative 스타일이 자연스럽다. 그런데 이 문제를 non-deterministic 알고리즘, 즉 리스트 모나드 문제로도 볼 수 있다.
“2” 는 “abc” 중 어느 하나, “3”은 “def” 중 어느 하나와 매핑되는데, “23”으로 나타나는 것은 그 모든 경우들이 모두 해당된다. 두 개의 알파벳을 연결하는 연산자 ⊕ 가 있다고 할 때(“a” ⊕ “b” = “ab”), 이 연산자 ⊕를 비결정적 알고리즘 문맥에서 적용하면 된다. 즉 {“a”, “b”, “c”} ⊕ {“d”, “e”, “f”} = {“ad”, “ae”, “af”, “bd”, …}와 같다.
이를 하스켈 코드로 옮겨보면 다음과 같다.
> "abc" ++ "def"
"abcdef"> liftM2 (++) ["a", "b", "c"] ["d", "e", "f"]
["ad","ae","af","bd","be","bf","cd","ce","cf"]
liftM2는 (++)라는 리스트 연결 함수를 모나드로 리프팅 시킨다는 의미다. 물론 여기서는 리스트 모나드, 즉 비결정적 알고리즘으로 변환시킨다. liftM2 (++)의 타입은 liftM2 (++) :: Monad m => m [a] -> m [a] -> m [a]
이렇게 비결정적 이어붙이기라는 관점으로 이 문제를 보면 문제를 다르게 해석할 수 있다. 이제 “23” 이라는 입력이 주어지면 각 숫자키에 대해 “abc”, “def” 처럼 가능한 글자들로 매핑한 다음, 후보들(“abc”)을 비결정적으로(즉 리스트 모나드로) 이어붙이면 된다.
그런데 이러한 연산(리스트 안에 담긴 모나드 효과를 리스트 바깥으로 꺼내오기)은 너무나 빈번해서 라이브러리에 이미 구현되어 있다. sequence라는 함수다.
> :t sequence
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)
> sequence ["abc", "def"]
["ad","ae","af","bd","be","bf","cd","ce","cf"]게다가, 이 문제가 요구하는 건 각 숫자키에 매핑되는 알파벳을 먼저 찾은 다음 그 후보들을 연결하는 것인데, 이 과정 역시 traverse 라는 함수로 제공된다. (혹은 mapM)
> :t traverse
traverse
:: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)이번에는 조금 복잡하니 하나씩 따져보자. 먼저 두 번째 인자인 t a는 매핑 연산이 적용될 대상, 우리 같으면[Char]라고 할 수 있다. 첫 인자인 매핑 함수의 결과 타입 f b 는 여기서 후보가 되는 선택지, 즉 알파벳의 목록이다. 문자열 [Char]라고 보면 된다. [Char] == String이므로 최종 결과는…
traverse :: (Char -> String) -> String -> [String]딱 이 문제에 맞는 함수가 이미 준비된 셈이다. 첫 인자인 Char -> String은 숫자키에 매핑된 알파벳을 찾는 함수, 두번째 인자인 String은 입력 전화번호, 그리고 결과 [String]은 우리가 원하는 답, 즉 조합 가능한 모든 문자열이 된다.
> letters c = fromJust $ lookup c [('2', "abc"), ('3', "def")]
> traverse letters "23"
["ad","ae","af","bd","be","bf","cd","ce","cf"]이상의 과정을 JavaScript로 옮겨보는 것도 흥미롭다. 이 경우는 배열에 대한 Traversable/Monad 구현만을 고려한다.
여기에 필요한 flatMap/map 구현이 모나드를 이룬다.
여기서 굳이 for-of를 쓴 이유는 JavaScript 문자열에 대해서도 flatMap/map을 사용할 수 있게 하기 위해서다.
마지막 코드는 다음과 같다.
만약, 필요한 Traverse/Monad 구현이 이미 준비되어 있다면 이 문제는 그야말로 할게 없는, 그냥 문제를 코드로 적으면 끝나는 문제다.
