User Tools

Site Tools


study:algorithms:monad

(http://www.intensivesystems.net/tutorials/monads_101.html 요약) (클로저를 통해 모나드를 설명하고 있는 사이트입니다.)

첫인상

모나드는 함수들을 합치는 방법입니다.

; f1~3 함수들이 인자 하나를 받고 값 하나를 리턴하는 경우.

(comp f1 f2 f3)
(fn [x]
   (f1
     (f2
       (f3 x))))
     

그런데 f3 연산의 결과를 f2 함수의 인자로 사용할 수 없을때는? f1~3 함수들이 int 를 인자로 받아서 [int] 리스트를 리턴하는 경우에는? 배관작업을 해줍니다.

(fn [x]
   (mapcat f1
           (mapcat f2
                  (f3 x))))
                

mapcat 을 이용해서 plain list 를 유지합니다. 모나드 이면에 있는 아이디어는 이런 배관작업을 뽑아내서 복잡성을 숨기고, 함수들의 조합만을 보이도록 해주는 것입니다.

모나드 기저

하스켈은 타입언어이기 때문에 함수들은 표기법(signature)을 가지며 입력-출력 값의 타입을 명시합니다. 함수에서 이러한 표기는 일종의 함수를 분류하는 타입과 같습니다. 같은 표기법을 가진 함수들은 같은 타입이라고 볼 수 있습니다. 클로저는 동적 타입이여서 표기법이 없습니다. 그러나 같은 종류의 함수들(입력 인자종류와 리턴 값의 종류)을 분류할 수 있습니다. 위에서 int 를 입력받아 [int 리스트] 를 리턴하는 f1,f2,f3 을 같은 그룹이라고 할 수 있습니다. 그룹내 함수들은 모나드를 이용해 조합하려고 한다면 모든 함수들은 같은 표기형태, “monadic function”이라는 형태를 가져야만 합니다. 또한, 이 모나딕 함수들에서 반환되는 값을 “monadic values” 라고 하며 일종의 포장한 것과 유사합니다. 위 예제에서 int 값들을 [리스트]라는 포장지로 감싼 [int 리스트]가 모나딕값입니다. 하지만 입력값과 출력값의 형태가 같다면 단순히 'comp' 고차함수를 사용하면 될것입니다.

현재 우리가 그룹잡은 함수들은 모나딕값을 반환하기 때문에 모나딕함수입니다. 위 예제의 모나딕함수들은 int (basic value)를 인자로 얻는 함수들이기 때문에 다른 모나딕함수에서 반환된 [int 리스트] (monadic value)를 집어 넣을 수가 없습니다. 그래서 모나딕값과 모나딕함수를 받아서 “제대로 맞게 처리하는” 어떤 함수가 필요합니다. 위 예제에서는 mapcat 이었습니다.

다만, 읽기 편하게, 관례상 모나딕값, 모나딕함수 순서대로 적습니다.

(mapcat f2 [1 5 7])

을 모나드 표현 관례에 따라

(m-bind [1 5 7] f2)

라고 적습니다.

(defn m-bind [mv mf]
      (mapcat mf mv))
    

이제 bind 함수 덕분에 모나딕값을 모나딕함수에 적용할 수 있게 되었습니다. 흠. 그럼, 처음 넣어주는 값이 모나딕값이 아니라 일반값인 경우에는 어떻게 할까요? 그럴땐 result 함수를 통해서 일반값을 모나딕값으로 바꿔주면 됩니다.

(m-result 6)
(defn m-result [x]
      [x])
    
    

결론적으로 모나드에서 result 함수는 일반값(regulat value) 를 모나딕값(monadic value)로 바꿔주고, bind 함수는 모나딕값, 모나딕함수를 받아서 잘 적용시켜줍니다.

Composing

그럼 이제 bind 를 이용해서 f1, f2, f3 을 합쳐봅시다.

    
(defn m-comp [f1 f2 f3]
    (fn [x]
        (m-bind
            (m-bind
                (m-bind
                    (m-result x)
                    f3)
                 f2)
             f1)))

코드가 상당히 지저분하지만, 이 함수는 어떤 종류의 모나드가 사용되는지 상관없이 쓰일 수 있습니다. 값을 포장하고 (모나딕값으로 바꾸고) 포장지를 뜯어 모나딕함수에 적용하는 부분을 bind 와 result 에서 다 처리해주고 있기 때문입니다. (* 어떤 종류의 모나드인지에 따라서 사용되는 bind 와 result 함수가 다릅니다. 하스켈은 타입으로 알아서 유추해서 인자 타입에 맞는 bind, result 함수를 부르지만, 클로저는 이제 예에서 나오겠지만, 어떤 종류의 모나드인지 언급을 해줘야 맞는 bind, result 함수를 찾을 수 있습니다.)

(m-comp f1 f2 f3)

이제 bind 와 result 덕분에 겉으로 주고받는 타입이 [int리스트](monadic value)가 되었습니다. 이제 새로만든 m-comp 를 이용해서 모나딕함수들을 조합할 수 있습니다. 다만, 아직 뭔가 부족해보입니다.

Do Notation

모나딕 함수를 합치는 더 좋은 방법은 'do' 표기를 사용하는 것입니다.

앞의 예에서 [int리스트] 를 모나딕값으로 정의한 모나드는 clojure.contrib.monads 에서 'sequenc-m' 이라고 불리는 것과 같습니다. (단, 'sequenc-m' 은 int 뿐 아니라 다른 타입의 리스트도 포함됩니다)

m-comp 함수를 이제 do 표기법을 사용해서 다시 정의해봅시다.

(defn m-comp [f1 f2 f3]
    (fn [x]
        (domonad sequence-m
                 [a (f3 x)
                  b (f2 a)
                  c (f1 b)]
                 c)))
                 

전보다 좀 나아졌습니다. :) 'domonad' 는 3 부분으로 되어있습니다. 첫째, 모나드 이름이 적힙니다. 위 코드에서는 sequence-m 모나드가 적혀있습니다. 둘째, 벡터로 감싸져 있는 부분에 변수-표현식 쌍이 들어있습니다. 셋째, 리턴값을 정의하는 표현식(위 코드에서 마지막 c))) 부분)이 있습니다.

자, 교모한 기술이 드러나고 있습니다. 변수-표현식 쌍에서, 표현식은 평가되서 모나딕 값을 리턴하고 있습니다. (f3 x) 가 평가되서 x 에 관련된 모나딕값이 나올 것입니다. 그러나 모나딕값이 바로 a 변수에 할당되는 것이 아닙니다. 이제 a 변수에는, 이어서 나오는 표현식에서 (f3 x)에서 나온 모나딕값 안에 들어있는 원래값에 접근할 수 있는 변수가됩니다.

위 예제에서 '(f3 x)' 는 x 를 가지고 [ int 리스트 ] (모나딕값) 을 만듭니다. 이어서 나온 f2 함수는 리스트의 각 int 값에 적용되고 적용된 값들을 모아 새 리스트를 만듭니다. 이 새 리스트의 값은 b 변수로 접근하게 됩니다. 이런 과정이 f1 에도 반복되어 c 변수까지 이어집니다.

domonad 의 마지막 부분이 반환 표현식 입니다. 이 표현식은 이전에 정의된 어떠한 변수에도 접근할 수 있습니다.

여기서 중요한 포인트가 있습니다. domonad 구분의 결과물도 monadic value 라는 점입니다. 그래서 domonad 구분 전체가 하나의 모나딕함수처럼 또다시 다른 모나딕 함수들과 합쳐질 수 있습니다. 바로 이점이 모나드가 가진 능력 중 하나입니다.

Comprehension

앞에서 눈여겨 봐야할 중요한 점은 변수-표현식 쌍에서 표현식이 반환하는 것이 모나딕값이라는 점입니다.

 (domonad sequence-m
                 [a (f3 x) <- 이부분은 호출되고 나오는 값이 모나딕값이다. 
                  b (f2 a) <- 여기도!
                  c (f1 b)] <- 그리고 여기도!
                 c)))
                 

아래 표현식을 살펴봅시다.

(domonad sequence-m
       [letters ['a 'b 'c]
        numbers [1 2 3]]
       [letters numbers])
;=> ([a 1] [a 2] [a 3] [b 1] [b 2] [b 3] [c 1] [c 2] [c 3])

이 코드에서 letters 가 의미하는 것은 모나딕값 (['a 'b 'c])에 들어있는 원래값(목적했던 값. 여기서는 여러개로 a', b', c' 가 된다.)을 가리킵니다. 이 모나드는 for 구분과 같습니다.

(for
   [letters ['a 'b 'c]
    numbers [1 2 3]]
   [letters numbers])
   
 ;=> ([a 1] [a 2] [a 3] [b 1] [b 2] [b 3] [c 1] [c 2] [c 3])
 

이 코드들을 보면 list comprehension 이라는 것이 실제로 domonad 의 특수한 경우, sequence-m 모나드의 경우라는 것을 알 수 있습니다. 이처럼 domonad 는 list comprehension 을 더 일반화한 것. 따른 말로 monad comprehension 라고 볼 수 있습니다.

하지만 왜?

All of this might be fascinating, but why go to the trouble of using a monad to structure code? 컴퓨터 과학분야에서 큰 문제를 작은 문제로 쪼개서 푸는 방법이 있습니다. 모나드를 사용하면 문제를 더작은 조각들로 쪼갤 수 있습니다. 각 쪼개진 문제들은 하나의 모나딕 함수가 처리할 수 있게합니다. 그리고 그 결과들을 하나로 합쳐서 큰 문제를 풉니다. 그러나 이 경우 단순히 큰 문제를 푼것만이 아닙니다. 수많은 조각들 - 독립된 코드들을 만든 것이고 레코처럼 샇여서 더큰 문제들을 해결할 수 있습니다. 모나딕 함수 조합의 진정한 힘은 바로 새 함수가 추가되었을때 풀 수 있는(조합가능한) 문제풀이방법이 지수적으로 증가한다는 것입니다.

More Power

sequence-m 모나드는 모나드를 설명할 때 좋은 예제가 됩니다. 시퀀스가 값들을 어떻게 가지고 있는지를 잘 보여줍니다. 이제 좀 더 어려운 모나드로 가보겠습니다.

함수형 언어의 강력한 특징 중 하나는 함수를 데이터처럼 취급해서 인자와 리턴값으로 주고받을 수 있다는 점입니다. 따라서 함수를 monadic value 로 하는 모나드를 생각할 수 있습니다. 헷갈리기 쉬운데 모나딕값으로써 함수와 모나딕함수로써 함수 구별에 집중하셔야합니다.

state-m 모나드를 이용해서 자세한 예제를 살펴봅시다. state-m 모나드의 모나딕값은 함수입니다. 이 모나딕값-함수는 하나의 value와 하나의 state 를 받아서 [return value, new-state] 인 리스트를 반환합니다. state 에는 문자열이든 숫자든 어떤것이든 가능합니다.

state-m 모나드의 모나딕값은 다음처럼 생겼습니다.

(defn some-fn [state]
     ; do something
     ; and something else
     [return-value new-state])

다시 강조하지만, 위 함수 그 자체가 모나딕값입니다.

우리는 state 가 숫자인 경우를 살펴보겠습니다. 그리고 이 state 숫자를 단순히 1씩 증가시키는 함수들을 만들어 보겠습니다.

(defn g1 [state-int]
    [:g1 (inc state-int)])
(defn g2 [state-int]
    [:g2 (inc state-int)])
(defn g3 [state-int]
    [:g3 (inc state-int)])

이제 모나딕 함수는 사용하지 않고, 바로 모나딕값을 넣어보도록 하겠습니다. 다시 강조하지만, g1, g2, g3 는 모나딕값입니다. 따라서 따로 모나딕함수를 호출해서 모나딕값을 만들지 않고 그냥 자리에 넣어도 됩니다.

(def gs (domonad state-m
               [a g1
                b g2
                c g3]
               [a b c]))

그럼 gs 는 무엇일까요? 일단 domonad 의 결과는 (state-m 의) 모나딕값이고, 그럼 gs 도 모나드값일 것입니다. 그리고 그 모나딕값은 state 를 인자로 받는 함수로 정의되어있음으로 gs 도 마찬가지로 state 를 인자로 받는 함수일 것입니다.

그럼 gs 의 반환값은 무엇일까요? 모나딕값인 함수가 [return value, new state ] 을 리턴하고 있습니다. 바로 이값이 gs 가 리턴하는 값입니다. return value 는 위 표현식 '[a b c]' 에 의해 결정됩니다.

(gs 5)
;=> ([:g1 :g2 :g3] 8)

state-m 모나드의 bind, result 함수는 다음과 같습니다.

(defn m-result [v]
    (fn [s]
        (list v s)))
(defn m-bind [mv f]
    (fn [s]
        (let [[v ss] (mv s)]
             ((f v) ss))))
             

좀 복잡해 보입니다.




일단 이 부분은 원문 사이트에 없는 부분이지만, 설명이 필요할 거 같아서 추가설명하겠습니다. 설명을 위해, 잠깐 identity 모나드를 먼저 설명하겠습니다. (클로저의 let 과 같음)

(let [x 5
       y (inc x)
       z (inc y)]
     (inc z))
   

를 함수로만 표현하면 아래와 같습니다.

( (fn [x] ( (fn [y] ( (fn [z] (inc z)) (inc y)) (inc x)) 5)

이것을 bind 함수로 표현을 바꿔보겠습니다.

 (defn bind [v f] 
           (f v))
; identity 모나드는 값 그자체가 모나딕값임으로 별도의 작업을 안해도 됩니다. 
; 순서만 바꿔주면 끝입니다.

 (bind  5  (fn [x] (bind  (inc x) (fn [y]  (bind (inc y) [fn [z] (inc z)))))))

순서를 바꿔서 더 쉽게 오른쪽 방향으로 읽을 수 있게 바뀌었습니다. 천천히 해석해보면, 5 라는 값을 뒤 함수에 인자 x로 들어갑니다. (inc x) 를 해주고, 그 값을 또 뒤 함수의 인자 y 로 넣습니다. (inc y) 해준 값을 또 그 뒤에 함수 z 에 인자로 넣습니다. 마지막으로 (inc z) 를 출력합니다.

다시 원래 문제로 돌아와서,

 (def gs (domonad state-m
               [a g1
                b g2
                c g3]
               [a b c]))
               

에서 bind 함수가 하는 일을 살펴봅시다. bind 함수는 mv(모나딕값) 과 f(모나딕함수)를 인자로 받습니다. 위 코드에서 우선 g1 이라는 mv 값이 bind 에 들어갑니다. 그럼 bind 에 인자로 들어가야할 f(모나딕함수)는 무엇일까요? 바로 앞에서 설명했던 identity모나드에 해답이 숨어있습니다.

바로 그 뒤의 연산 전부가 f(모나딕함수)로 들어가있습니다. 문제 코드에서 g1에서 나온 return value 인 :g1 값이 a에 할당됩니다. 함수로 달리 표현하면,

(bind  g1  (fn [a] ...

또 g2 가 사용됩니다.

(bind  g1  (fn [a]  (bind  g2  (fn [b] ...

마지막으로 g3 가 사용됩니다.

(bind  g1  (fn [a]  (bind  g2  (fn [b]  (bind  g3  (fn [c]  [a b c]))))))

'[a g1' 이 적힌 부분에서 나온 값 a 는 그 바로 아랫줄인 ' b g2' 부분에서 g2 함수가 전혀 사용하지 않습니다. 그래도 상관없습니다. 단순히 g1 에서 원하는 값을 변수 a에 할당해 놓고, 이후 계산단계 어디에서건 이 값을 접근할 수 있게 할 뿐입니다. a 값은 closure 로써 그 안의 nested function 에서 접근 가능한 상태로 남아있는 것입니다. 위에서 처럼 nested function 구조로 되어있기 때문에 변수가 선언된 위치 아래라면, 어디서건 그 값에 접근할 수가 있습니다.

자. 그럼 다시 원래~ 문제인 state-m 의 bind 함수를 살펴봅시다.

(defn m-bind [mv f]
    (fn [s]
        (let [[v ss] (mv s)]
             ((f v) ss))))

우선, g1 이 mv 값으로 들어오고, 그 이후 모든 처리 부분이 f 함수입니다. [:g1 (inc state)] = (g1 state) 가 될 것이고, 아래줄에 있는 (f v) 의 의미는 일단 여기서 나온 :g1 값을 인자로 넘겨서 나머지 부분에서 접근 가능하게 한 것이고, 이 부분을 처리하면 또 모나딕값(state 를 인자로 받는 함수)가 나올 것입니다. 그 모나딕값에 여기서 처리된 new-state 인 ss 를 인자로 넣는 것입니다.




state-m 모나드에는 흥미로운 점이 있습니다. state 에 대한 fetch-state 와 set-state 함수가 그것입니다.

(defn fetch-state []
    (fn [state]
        [state state]))
        
(def gs1
   (domonad state-m
            [a g1
             x (fetch-state)
             b g2]
            [a x b]))

(gs1 3)
;=> ([:g1 4 :g2] 5)
(defn set-state [new-state]
    (fn [old-state]
        [old-state new-state]))

(def gs2
   (domonad state-m
            [a g1
             x (set-state 50)
             b g2]
            [a x b]))

(gs2 3)
;=> ([:g1 4 :g2] 51)
(defn m-result [v]
    (fn [s]
        (list v s)))
(defn m-bind [mv f]
    (fn [s]
        (let [[v ss] (mv s)]
             ((f v) ss))))
             

result 함수는 단순히 값을 저장하면서 state 를 받는 함수를 리턴합니다.

(다시 언급하지만, MV = (fn [state] (return-value, new-state)) 함수이다.)

bind 함수는 조금 복잡한데, 우선, mv(monadic value = 현재 함수) 와 f(monadic function) 를 인자로 받습니다. 여기가 복잡한데, f 에 바로 mv 를 적용하지 않고, (mv s) 를 통해서 basic value 를 꺼내서 f 에 적용합니다.

bind 를 통해 모나딕값인 함수 (fn [s] …) 가 반환됩니다. 모나딕함수 f 를 반환된 값 v 에 적용해서 새 모나딕값이 나옵니다.

Legalities 적합성?

모나드 첫번재 규칙

(bind (result x) f) == (f x)

모나드 두번째 규칙

(bind mv result) == mv

모나드 세번째 규칙

(bind (bind mv f) g) == (bind mv (fn [x] (bind (f x ) g)))

이 규칙을 따른다면, 흥미로운 점이 모든 모나드에 적용할 수 있는 bind 와 result 만으로 작성된 함수가 존재한다는 점입니다.

… 계속… (추후 계속 번역 요약해서 올리겠습니다)




아래는 하스켈 언어로 모나드를 설명한 사이트입니다. (http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html 요약)

“모나드를 이미 만들어 사용하고 있었을지 모릅니다!”

Side Effects: Debugging Pure Functions

우선 부수효과를 다룬 모나드부터 살펴보겠습니다.

절차형 언어에서 함수는 수학의 함수와 다르게 부수효과과 있습니다. 주어진 인자에만 의존해서 일을하는게 아니라 그 이상의 변화를 만듭니다. 전역변수를 읽고 쓰는것, 화면에 출력, 유저에 의한 데이터 입력… 모두 부수효과입니다. 그러나, 순수 함수형 언어에서는 함수의 역할은 오직 인자만을 통해서 결정됩니다.

그럼 다음 문제를 순수 함수형언어에서 생각해봅시다. : f, g 라는 두 함수가 있는데 float → float 의 형태로 입력-반환이 됩니다. 그런데 디버깅 목적으로 리턴값에 추가적인 문자열 정보를 얻고 싶습니다.

f,g :: Float -> Float

어떻게 하면 f, g 가 부수효과를 가질 수 있게 만들까요? 별다른 선택이 없습니다. 리턴값에 추가로 문자열을 내는 함수 f' g' 가 필요합니다.

f',g' :: Float -> (Float,String)
  x
  |
+---+
| f'|
+---+
 |  \ 
 |   |
f x  "f was called."

이제 이런 함수를 'debuggable' 함수라고 하겠습니다.

이제 이런 함수 두개를 조합해야 한다고 생각해봅시다. 원래 함수 f, g 는 간단하게 f . g 처럼 합칠 수 있지만 debuggable 함수는 그런식으로 다룰 수 없습니다. f' 와 g' 에서 나온 문자열들을 하나의 문자열로 합쳐줘야 할것입니다.

let (y,s) = g' x
     (z,t) = f' y in (z,s++t)
   
(let [[y s] (g' x)
       [z t] (f' y)]
     (z, (str s t))) 
  

이렇게 적을 수 있습니다.

   x
   |
 +---+
 | g'|
 +---+
  |   \   
+---+  | "g was called."
| f'|  |
+---+  |
 | \   |
 |  \  |
 |  +----+
 |  | ++ |
 |  +----+
 |     |
f (g x) "g was called.f was called."

매번 let 을 통해서 문자열을 합치는 작업을 매번해야하는 것은 고된 일입니다. 우리 대신에 이런 배관작업을 해줄 고차함수가 필요합니다. 문제는 g' 의 결과물을 f' 에 바로 입력할 수 없다는 것입니다. 좀 더 'upgrade' f' 가 필요합니다. bind 함수가 이런 일을 해줍니다.

bind f' :: (Float,String) -> (Float,String)

bind 는 f' 라는 함수를 받아서 입출력이 모두 (Float,String) 형태로 바뀌었습니다.

bind :: (Float -> (Float,String)) -> ((Float,String) -> (Float,String))

bind 함수의 type signature 는 위와같습니다. (Float → (Float,String)) 같은 함수를 받아서 ( (Float,String) → (Float,String) ) 형태의 함수를 리턴합니다.

위 bind 함수는 2가지 목적을 가집니다. 1) g'x 의 올바른 부분의 값을 f' 에 적용합니다. 2) g' 에 나온 문자열과 f' 에서 나온 문자열을 합쳐줍니다.

연습문제 1
Q . bind 함수를 작성해보세요.

A . bind f' (gx,gs) = let (fx,fs) = f' gx in (fx,gs++fs)

mv = (v, s)

(defn bind [f'  [v1 s1]]
    (let [[v2 s2] (f' v1)]
       (v2  (str s1 s2))))
     

이제 주어진 함수 f'와 g' 를 새로운 debuggable 함수인 bind f' . g' 를 만들면서 가능해졌습니다. 이제 bind f' . g' 이것을 f' * g' 로 적겠습니다.

bind f' . g' 
f' * g' 

이제 g' 의 결과물이 f' 입력으로 맞지 않지만 두 연산을 쉽게 합칠 수 있게 되었습니다. 여기서 생기는 질문 : 'identity' debuggable function 가 존재할까요? identity 란 보통 f . id = f 와 id . f = f 성질을 만족하는 성질입니다. 이제 이런일을 하는 함수를 unit 이라고 부르겠습니다.

f . id = f 
id . f = f
unit * f = f * unit = f

(여기서의 f 는 위 예제의 f 와 상관없고 어떤 debuggable 함수를 말한다.)
연습문제 2
Q. unit 함수를 정의하세요.

A. unit x = (x, "")

unit 함수는 어떤 함수를 'lift' 들어올려서 debuggable 한 리턴값을 가지는 함수로 바꿔줍니다.

lift f x = (f x,"")

lift f x = unit . f 
연습문제 3
Q. lift f * lift g = lift (f.g) 임을 증명하세요

A. 위 문제에서 f, g 는 :: Float -> Float 함수이다.
lift f * lift g                       lift (f.g) 
unit . f  *  unit . g              unit . (f . g)

unit  은 값에 영향을 주지 않고 새로운 타입으로 이동만시켜주는 함수이다.
양쪽의 차이는 새로운 타입으로 이동한 상태에서 연산했는지
아니면 원래 타입에서 연산하고 그 결과물을 새로운 타입으로 이동시켰는지이다. 

어떤 값이 들어갔다고 했을때,
unit . f  *  (g-float, "")        unit . (f g-float)
( f g-float, "")                     (f g-float, "")

요약 : bind, unit 으로 인해서 debuggable 함수들을 간단하게 합칠 수 있게 되었습니다. 또한 여러개의 debuggable 함수들도 자연스럽게 가능해집니다.

벌써 우리는 첫번째 모나드를 정의해보았습니다. 아직 모나드의 구조가 명확하게 파악하기 힘들 것입니다. 앞으로 몇가지 다른 모나드의 쉬운 예제를 통해서 공통 구조물을 찾도록 하겠습니다. 제 생각에는 이런 문제를 맞딱드린 많은 사람들이 모나드를 모르지만 위와 같은 방법을 이미 만들어 사용하고 있을 것입니다. 맞

A Container: Multivalued Functions

두번째 살펴볼 모나드는 리턴값이 여러개인 함수입니다. 복소수 인자에 대한 제곱값과 세제곱값을 찾는 함수인 sqrt, cbrt을 생각해보면 type signature 가 다음과 같습니다.

sqrt',cbrt' :: Complex Float -> [Complex Float]

이를 'multivalued' functions 라고 부르겠습니다.

(일종의 함수를 분류하는 것입니다. 모나드는 한 종류에 함수들에게 작용하는 bind 와 unit 함수를 따로 가집니다. 앞에서 'debuggable' 함수 예제에서 :: Float → (Float,String) 라는 함수들이 monadic function 으로 정의했고, monadic value 는 (Float,String) 였습니다. 그리고 그에맞는 bind와 unit 함수를 정의했었습니다. 이번에는 'multivalued' 형태의 함수들에게 적용가능한 모나드를 만들려고 합니다. 당연히 이 분류 함수들에게 맞는 bind와 unit 함수를 정의해야합니다)

64를 복소수 범위에서 가능한 모든 6제곱근을 구한다고 해봅시다.

수학적으로 표현하면 cbrt (sqrt 64) 가 될테지만, 프로그래밍에서는 입력-출력값이 다르게 때문에 다른 방식으로 조합해야합니다.

우선 sqrt 에서 64에 대한 가능한 제곱근 값들을 얻습니다. [+8, -8] 그리고 모든 값들에 대한 cbrt 값을 구합니다. [2 .. … -2 .. …]

      64
      |
     +------+
     + sqrt'+
     +------+
   +8 /    \ -8
 +------+  +------+
 | cbrt'|  | cbrt'|
 +------+  +------+
  | | |      | | |
  2 . .     -2 . .
연습문제4
Q. bind 함수를 구현해보세요

A. bind f x = concat (map f x)

(defn bind [f x]
    (mapcat f x))
   

그럼 여기에서의 identity 함수는 어떤 형태일까요? 하나의 값을 받아서 길이1개짜리 리스트가 나올 것입니다. 이 함수를 unit 함수라고 부르겠습니다.

연습문제5
Q. unit 함수를 정의해보세요

A. unit x = [x]

(defn unit [x] 
        [x])
        

이제 다시한번 다음을 정의해봅시다.

f * g = bind f . g 
lift f = unit . f

여기서 lift 는 함수 f 의 리턴값을 multivalued 타입으로 이동시키고 있습니다.

(정리하자면, * 는 bind 함수로써 모나딕함수를 합치는 데 사용하고, lift 는 리턴값이 다른 곳인 함수를 multivalued 타입으로 이동시켜 모나딕함수로 바꾸는데 사용합니다)

또다시, 결국 bind 함수쪽으로 도착하였습니다. 이제 우리는 두번째 다른 모나드 정의를 끝냈습니다. 흥미로운 점은 완전히 다른타입의 문제들(하나는 디버깅관련, 하나는 멀티값 관련)이었는데 유사한 구조를 보이고 있다는 것입니다.

A more complex side effect: Random Numbers

세번째 살펴볼 모나드는 랜덤 함수에 관한 모나드입니다.

하스켈에서 랜덤함수는 다음과 같습니다.

random :: StdGen → (a,StdGen)

StdGen 는 seed 입니다.

이 모나드에서 monadic value 가 됩니다. 

요지는 다음과 같습니다. 순수 함수형 언어에서는 씨드를 받아서 랜덤 숫자를 생성하고 새로운 씨드를 리턴해야합니다. (명시적으로 입-출력으로 처리해야합니다) 비-순수 언어에서는 함수 안에서 전역변수에 저장된 씨드를 가져다가 업뎃까지 해주지만, 부수효과를 지양하는 순수함수에서는 인자로 넣어줘야합니다. 여기까지 보면 앞에서 다뤘던 디버깅 케이스와 유사합니다. 부가적인 데이터가 출력된다는 것. 하지만 부가적인 데이터가 입력까지 된다는 것이 다릅니다.

그러면 우리가 분류할 randomised function 들은 다음과 같은 형태를 가질 것입니다.

randomised function :: a → b
랜덤함수 a -> 랜덤함수 b 
씨드를 명시적으로 표시를 해주면, 다음과 같다. 
randomised function :: a → StdGen -> (b,StdGen)

랜덤함수 a 와 씨드를 받아서 랜덤함수 b와 새-씨드를 생성하는 함수이다.

(많이 어지럽다 -_-; 하스켈에서는 씨드만 바뀌는 것이 아니라, 랜덤함수도 바뀔 수 있다는 것 같다.;;
 다른언어에서 함수는 똑같이 유지하고 씨드만 새로 바뀌는 랜덤함수만 생각하다보니 더 헷갈렸다;
 하스켈 랜덤부분을 좀더 공부해야할듯;;) 

이런 랜덤함수들을 합치려면,

bind :: (a → StdGen → (b,StdGen)) → (StdGen → (a,StdGen)) → (StdGen → (b,StdGen))
                           f                                          mv                                   mv'                             
            f 는 모나딕 함수. 
            모나딕값은  (StdGen → (b,StdGen)) 형태의 함수 
            그리고 a b 도 랜덤함수이며 모나딕값형태와 같다.
연습문제 7
Q. bind 함수를 구현해보세요

A. bind f x seed = let (x',seed') = x seed in f x' seed'


x 는 모나딕값으로써  :: StdGen → (a,StdGen) 형태의 함수이다.

(defn bind [ f x seed ]
     (let [[x'  seed']  (x seed)]
         (f x' seed')))
         
 하스켈은 커링이 되서 f x seed 인자들 중, 받지못한 부족한 인자만큼 대기하는 함수를 만들어주지만,
 클로저의 경우 정해진 인자가 들어오지 않으면 문제가 된다. 
 아래처럼 seed 를 나중에 받도록 뺀, 함수형태로 반환하는 것이 더 알맞다.
         
(defn bind [ f x ]
      (fn [seed]
         (let [[x'  seed']  (x seed)]
            ((f x') seed'))))
         
 

이제 'identity' randomised function 를 찾아봅시다. 타입 시그니처는 다음과 같을 것입니다.

unit :: a → (StdGen → (a,StdGen))
연습문제 8
Q. unit 함수를 구현해보세요

A. unit x g = (x,g)

    or 

    unit = (,)
연습문제 9
Q.  f * unit = unit * f = f 
      lift f * lift g = lift (f.g) 임을 보여라.
모나드

type Debuggable a = (a,String) type Multivalued a = [a] type Randomised a = StdGen → (a,StdGen)

Debuggable, Multivalued, Randomised 대신에 변수 m 을 사용해보자. 각 모나드에서 모나딕 함수들은 a → ma 이런 형태를 취하고 있습니다. 여기서 공통적으로 맞딱뜨린 문제가 앞선 연산의 결과물을 뒤이은 함수의 인자로 넣기 어렵다는 것이었습니다. 그래서 각각 bind 라는 함수를 정의했습니다.

bind 함수를 간략히 요약하자면, 
모나딕함수 f와 모나딕값 mv 를 받아서 새로운 모나딕값 mv 를 만들어내는 함수이다.
(a → m b) -> (m a → m b)
다른 식으로 표현하면, 
모나딕함수 f 를 받아서 (m a → m b) 로 연산하는 함수로 바꿔주는 고차함수이다.
(모나드는 설명하는 방법이 너무 다양해서 오히려 이해하기 힘드네요 -_-;)

더불어 일반값을 모나딕값으로 바꿔주는 unit 함수도 정의했습니다. 그리고, bind, unit 으로 정의된 모나드들이 f * unit = unit * f = f 와 lift f * lift g = lift (f.g) 을 만족함을 보았습니다.

이제 모나드가 무엇인지 말할 수 있습니다. m, unit, bind 3가지가 모나드를 구성합니다. 그리고 위에서 다들 증명했던 몇가지 모나드 규칙을 만족해야 합니다. 아마도 각각 문제의 경우 모나드가 뭔지 몰라도 유사한 방법을 사용하고 있었을지 모릅니다.




모나드 참고 자료 사이트
study/algorithms/monad.txt · Last modified: 2019/02/04 14:26 (external edit)