Haskell (FP101.x) – Chapter 4

edx 의 FP101.x (Introduction to Functional Programming) 수업 중 4 번째 챕터입니다.

 
이번시간엔 모나드를 배웁니다. 네. 올것이 왔습니다. 간단한 파서를 구현하는 것 부터 시작해 보겠습니다.

What is a Parser

Parser (파서) 란 텍스트 조각을 분석하여 syntaxtic structure 를 만들어 내는 프로그램(코드)를 말합니다.

많은 프로그램들이 자신만의 파서를 가지고 있습니다. GHChaskell , UNIXshell script, explorerHTML 분석합니다.

The Parser Type

type Parser = String -> Tree

하스켈 같은 함수형 언어에서 파서는 함수라 볼 수 있습니다. 문자열을 받아서 Tree (트리) 를 만들어 주는 함수처럼요.

때때로 입력된 문자열이 이상하다면 파서가 제대로 동작하지 않을수도 있습니다. 그럴때 분석되지 않은 문자열을 돌려주려면 이런 형태여야 합니다.

type Parser = String -> (Tree, String)

어떤 문자열들은 여러가지로 해석될 수도 있겠지요. 그럼 리스트를 돌려줘야겠네요.

type Parser = String -> [(Tree, String)]

꼭 파서가 트리를 만들 필요는 없지 않을까요? 문자열이 1 + 2 라면 이 값을 더한 3 을 돌려줄 수도 있을겁니다.

type Parser a = String -> [(a, String)]

이번 강의에서는 복잡한 파서를 구현하기 보다 파서가 무슨일을 하는지에 집중할 것이므로 파서의 타입을 심플하게 가져가겠습니다. 파서가 문자열을 분석하는데 실패하면 [] 성공하면 singleton list 를 돌려주겠습니다.

Basic Parsers

먼저 문자열에서 첫 번째 원소를 소비하고, 나머지를 돌려주는 간단한 item 파서를 만들어 봅시다. 이 파서는 빈 문자열에 대해서는 [] 를 돌려줍니다.

module Lecture7 where

type Parser a = String -> [(a, String)]

item :: Parser Char
item = \xs -> case xs of
               [] -> []
               (x:xs) -> [(x, xs)]

실행하면 이런 결과를 얻습니다.

> item "hello world"
-- [('h',"ello world")]

> item ""
-- []

항상 [] 만 돌려주는 failure 파서와 a -> Parser a 타입의 return 도 만들어 봅시다. 하나는 항상 실패하고, 다른 하나는 항상 성공하는 파서입니다.

failure :: Parser a
failure = \xs -> []

return :: a -> Parser a
return v = \xs -> [(v, xs)]

> failure "hello world!"
-- []

> (return "hello") " world"
-- [("hello"," world")]

> (return "hello") ""
-- [("hello","")]

이제 두 개의 파서를 붙이는 함수 (+++) 를 만들어 봅시다. p +++ q 에 대해 파서 p 가 성공하면 p 의 리턴값을, p 가 실패하면 q 가 처리하게 합시다. 위에서 항상 성공하는 파서 return v 와 항상 실패하는 파서 failure 를 여기다 붙이며 어떻게 될지도 한번 생각해 보는것도 좋습니다.

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = \xs -> case p xs of
                  [] -> parse q xs
                  [(y, ys)] -> [(y, ys)]
                  
parse :: Parser a -> String -> [(a, String)]
parse p xs = p xs  

여기서 parse 는 그냥 readable 한 코드를 만들기 위해 사용했다고 보면 됩니다. 파서와 텍스트를 받아서 그 적용한 결과를 돌려줍니다.

> parse (return '1') "234"
-- [('1',"234")]

> parse failure "abcd"
-- []

> parse (failure +++ (return '1')) "abcd"
-- [('1',"abcd")]

> parse (item +++ return 'd') "abc"
-- [('a', "bc")]

Monad

여기서 잠깐 생각해 볼 거리가 있습니다. “parser 가 대체 무슨일을 하고 있는가?”

파서의 타입을 잘 보면 원본 타입 String 을 받아, 여기서 부가적인 작업을 해서 a 타입을 만들고, 다시 본래 타입인 String 더해 튜플로 만들어 돌려줍니다. 다시 말해 파서는 한 타입을 받아 부가적인 정보를 만들어 본래 타입에 붙여주는 함수 라 볼 수 있습니다.

파서의 연결을 도와주는 함수는 (+++) 무엇일까요? 부가적인 정보를 붙여주는 파서 를 합성 해 주는 역할을 합니다.

지금 (+++) 의 규칙은 p 가 실패하면 q 를 적용하지만, 파서 t, u, v 를 받아 모두 적용한 뒤 결과를 돌려주는 연산자도 만들 수 있습니다.

(+++) 자체는 하나의 규칙을 의미하지만 자세히 보면 이외에도 다양한 규칙을 가진 합성 함수를 만들 수 있다는 것을 알 수 있습니다.

부가적인 정보를 만들어 내는 함수와(파서), 이 파서간의 합성이 아주 중요한 키 포인트입니다. 그리고 이 파서가 바로 monad 입니다. 두둥

The parser type is a monad, a mathematical structure that has proved useful for modeling many different kinds of computations

Sequencing

위에서는 두개의 파서를 엮어 하나로 만들긴 했지만 둘 중에 하나만 사용했죠. 둘 다 사용하진 않았습니다. 그럼 둘 이상의 파서를 엮어 하나의 파서를 만들려면 어떻게 해야할까요? 일단 생각해 볼 수 있는건 타입이 좀 다릅니다.

서로 다른 두개의 파서 Parser aParser b 를 고려해 봅시다.

type Parser a = String -> [(a, String)]

Parser a
-- String -> [(a, String)]

Parser b
-- String -> [(b, String)]

Parser a 의 출력은 [(a, String)], 이기 때문에 다른 파서 Parser b 의 입력 String 이 될 수 없습니다.

그리고 여기서 한 가지 더 중요한 사실은, Parser aString 을 이용해 만든 타입 a 의 부가정보를 Parser b 에 손실 없이 넘겨줘야 한다는 사실입니다. 그래야만 파서를 조합한 의미가 있지요.

정리하자면 Parser a 를 받아 Parser b 를 돌려주는 파서 조합함수 를 만들 것인데, 부가정보 a 의 보존을 위해 이 함수 내부에서 a -> Parser b 타입의 중간 함수가 필요합니다. 이 중간 함수가 어디에서 어떤 일을 할지가 구현해야 할 부분이자, 가장 중요한 부분입니다. 파서 종류에 따라 원본 데이터 (여기서는 String) 을 조작하는 방법이 다르기 때문입니다. 거꾸로 말하면 다양한 종류의 파서가 있다는 말 입니다.

함수의 이름은 >>= 라 짓겠습니다. bind 라 읽습니다. 타입은

type Parser a = String -> [(a, String)]

parse :: Parser a -> String -> [(a, String)]
parse p xs = p xs

(>>=) :: Parser a -> (a -> Parser b) -> Parser b

구현은

p >>= q = \xs -> case p xs of
                  [] -> []
                  (y, ys) -> parse (q y) ys

>>=Parser a 의 처리 결과가 [] 이면 [] 을 돌려줍니다. 올바르게 처리되었을 경우에는 Parser a 의 결과로 얻어진 부가정보 a 타입에 대해 a -> Parser b 타입의 함수인 y 에게 넘겨 Parser b 를 받고 결과적으로는 \xs -> parse k ys 를 돌려줍니다. (k :: parser b) 그런데, 여기서 parse k ys 의 결과가 [(b, String)] 이기 때문에 \xs -> parse k ysParser b 라 볼 수 있습니다.

최종적으로는 Parser a 를 이용해 Parser b 를 만들어 냈습니다.

예제를 한번 보시죠. Parser Char 을 이용해 Parser (Char, Char) 을 만들어 볼 수 있습니다.

return :: a -> Parser a
return v = \xs -> [(v, xs)]

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= q = \xs -> case p xs of
                   [] -> []
                   (y, ys) -> parse (q, y) ys
      
-- consume only one Char
parseTwice :: Parser (Char, Char)
parseTwice = item >>= \x -> return (x, x)
parseTwice "5BEAF"
-- [((5, 5), "BEAF")] 

itemreturn (x, x) 두개의 파서를 조합해서 parseTwice 라는 새로운 파서를 만들었습니다. 조금 더 붙여볼까요?

ignore2 :: Parser (Char, Char)
ignore2 = item >>= \x -> item >>= \y -> item >>= \z -> return (x, z)

> ignore2 "2A371"
-- [(('2','3'),"71")]

Do

위에서 보았듯이 같은 원본 타입 String 을 가지는 같은 종류의 파서(모나드)는 계속 연결할 수 있습니다. p1, ..., pn 을 파서라 하고 v1, ..., vn 을 파서가 만드는 부가정보라 할 때 다음과 같이 일반화 할 수 있습니다.

p1 >>= \v1 ->
p2 >>= \v2 ->
p3 >>= \v3 ->
...
pn >>= \vn ->
return (f v1 v2 ... vn)

하스켈에선 조금 더 편한 문법을 지원하는데요 바로 do 구문입니다.

do v1 <- p1
   v2 <- p2
   ...
   vn <- pn
   return (f v1 v2 ... vn)

Monadic Axioms

이 때 do 구문을 활용하는 파서(모나드) pn 에 대해서는 미리 >>=return 이 구현되어 있어야 합니다. 우리도 위에서 두 가지 함수를 사용했습니다.

하스켈에서는 모나드 클래스가 따로 있습니다. 그리고 모든 모나드 클래스의 인스턴스는 최소한 >>=return 을 구현해야 합니다. 우리가 위에서 구현했던 파서를 잠깐 보면

type Parser a = String -> [(a, String)]

return :: a -> Parser a
return v = \xs -> [(v, xs)]

(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= q = \xs -> case parse p xs of
                  [] -> []
                  [(y, ys)] -> parse (q y) ys

returna 를 받아 파서를 돌려줍니다. >>= 는 파서(모나드)를 결합하지요.

아까 다양한 파서(모나드)가 있을 수 있다고 말했던 것 기억 나시죠? 많은 종류의 모나드에 대해 최소한 return>>= 를 구현해야 하는데, 이때 지켜져야 할 axioms (공리) 가 있습니다.

(1) m >>= return == m (right unit)
(2) return x >>= f == f x (left unit)
(3) (m >>= f) >>= g == m >>= (\x -> f x >>= g) (associativity)

So, Why Monad?

근데, 이런 복잡한 모나드가 왜 중요한걸까요? 바로 부가정보 를 만들면서 본래의 타입을 유지하기 때문입니다.

본래 순수 함수형 프로그래밍에선 콘솔 출력 같은 side-effect 를 만들 수 없습니다. 그러나 모나드를 이용하면 부가정보 (= side-effect)연산 부분 (purely functional) 를 분리할 수 있습니다.

실제 하스켈에서도 IO Monad 를 통해 입출력을 할 수 있죠.

Monad, Again

그러면 실제로 하스켈에서 제공하는 모나드를 클래스를 사용해 봅시다. 코드를 조금 변경해야합니다.

module Lecture7 where

import Control.Monad

-- ref: http://www.cs.nott.ac.uk/~gmh/Parsing.lhs
newtype Parser a = P (String -> [(a, String)])

instance Monad Parser where
  return v = P $ \inp -> [(v, inp)]
  p >>= f = P $ \inp -> case parse p inp of
                         [] -> []
                         [(v, out)] -> parse (f v) out

item :: Parser Char
item = P $ \inp -> case inp of
                    [] -> []
                    (x:xs) -> [(x, xs)]

parse                         :: Parser a -> String -> [(a,String)]
parse (P p) inp               =  p inp

ignore2 :: Parser (Char, Char)
ignore2 = do x <- item
             item
             z <- item
             return (x, z)

실제 돌려보면,

> parse ignore2 "7A3BCEF"
-- [(('7','3'),"BCEF")]

MonadPlus

아까 작성했었던 파서 failure, (+++) 기억 나시나요? failure 는 항상 실패하는 파서를, (+++) 는 첫번째 파서와 두번째 파서를 붙여 둘 중 성공하는 하나의 파서만 선택하는 합성 파서입니다.

하스켈에선 이런 두 가지 특징을 구현한 모나드를 MonadPlus 라 부릅니다. 다시 말해 MonadPlus 에는 기본적인 return 이나 >>= 이외에도 위 두 가지가 더 구현되어 있다는 말이죠.

MonadPlus 에서는 failure 대신 mzero(+++) 대신 mplus 란 이름을 사용합니다.

instance MonadPlus Parser where
  mzero = P $ \_ -> []
  p `mplus` q = P $ \inp -> case parse p inp of
                             [] -> parse q inp
                             [(v, out)] -> [(v, out)]

failure :: Parser Char 
failure = mzero

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = p `mplus` q
> parse (item +++ return 'd') "abc"
-- [('a',"bc")]

> parse (item +++ return 'd') ""
-- [('d',"")]

Derived Primitives

이제 파서를 엮어서 다양한 파서를 만들어 봅시다.

import Data.Char

sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then return x else failure

digit :: Parser Char
digit = sat isDigit

lower :: Parser Char
lower = sat isLower

upper :: Parser Char
upper = sat isUpper 

letter :: Parser Char
letter = sat isAlpha

alphanum :: Parser Char
alphanum = sat isAlphaNum

char :: Char -> Parser Char
char x = sat (== x)

여기서 char 을 이용하면 지정된 문자열이 있는지 검사하는 파서 string 을 만들 수 있습니다.

string :: String -> Parser String
string [] = return []
string (x:xs) = do char x
                   string xs
                   return (x:xs)

string 은 재귀를 이용해 작성했는데, 입력된 문자열이 모두 존재할 경우에만 return 하고 아니면 [] 를 돌려줍니다. (do 매크로는 중간에 [] 가 나오면 [] 를 바로 리턴합니다.)

> parse (string "google") "naver google yahoo"
-- []

> parse (string "google") "google yahoo"
-- [("google"," yahoo")]

> parse (string "google") "goo yahoo"
-- []

그러면, digitletter 같은 파서에 대해 동일한 파서를 여러번 사용하려면 어떻게 해야 할까요? string 처럼 재귀를 이용해 매번 파서를 만들어야 할까요?

그렇지 않습니다. mutual recursion 을 이용해서 파서를 받아 여러번 적용해 주는 many 란 파서를 만들어 봅시다.

many :: Parser a -> Parser [a]
many p = many1 +++ return []

many1 :: parser a -> Parser [a]
many1 p = do x <- p
             xs <- many p
             return (x:xs)

manyp 을 0번 이상, many1 은 적어도 1번 이상 p 를 적용합니다.

many 를 활용하면 변수의 이름도 파싱할 수 있습니다. 변수의 이름은 첫 글자가 소문자로, 나머지는 알파벳 혹은 숫자로 구성되어 있다고 하면 이를 위한 파서 ident

ident :: Parser String
ident = do x <- lower
           xs <- many alphanum
           return (x:xs)

> parse ident "left = 3"
-- [("left"," = 3")]

이제 뭔가 파서가 좀 쓸만해 보이죠? 자연수를 파싱하는 nat 와 스페이스를 파싱하는 space 를 만들어 보겠습니다.

nat :: Parser Int
nat = do xs <- many1 digit
         return (read xs)
      
space :: Parser ()
space = do many (sat isSpace)
           return ()
        
> parse nat "123 abc"
-- [(123," abc")]

> parse space "   abc"
-- [((),"abc")]        

코드를 분석하는 파서를 만들때 스페이스를 주의해야 합니다. 예를 들어 1+21 + 2 는 같은 코드입니다.

파서를 받아 앞 뒤로 붙은 스페이스를 제거하는 기능을 덧붙인 파서를 돌려주는 token 이란 함수를 만들어 봅시다. 그리고 나면 token 을 활용해 identifier, natural, symbol 을 만들겁니다.

token :: Parser a -> Parser a
token p = do space
             v <- p
             space
             return v
             
identifier :: Parser String
identifier = token ident

natural :: Parser Int
natural = token nat

symbol :: String -> Parser String
symbol xs = token (string xs)

이제 이걸 엮어서 숫자 리스트를 분석하는 파서를 만들어 봅시다.

nlist :: Parser [Int]
nlist = do symbol "["
           n <- natural
           ns <- many (do symbol ","
                          natural)
           symbol "]"
           return (n:ns)


> parse nlist "[1, 2, 3]"
-- [([1,2,3],"")]

> parse nlist "[1, 2]"
-- [([1,2],"")]

> parse nlist "[1, 2"
-- []

> parse nlist "[1 2"
-- []

> parse nlist "[1,"
-- []

모나드의 세계란 참으로 놀랍죠?

Arithmetic Expressions

이제 단순한 텍스트가 아니라, 코드를 분석해 보죠. 우선 작은 수식을 분석하는 파서를 작성해 봅시다. 우리가 작성할 파서는 정수에 대한 *+ 만 처리할 수 있습니다. 간단히 문법을 만들어 보면

expr   ::= expr + expr | term
term   ::= term * term | factor
factor ::= (expr) | nat
nat    ::= 0 | 1 | 2 | ...

처음보면 난해할 수 있습니다. 이 그림과 비교해가며 보세요. 완벽히 일치하진 않지만 대략적인 설명을 해줍니다.

(http://www.csee.umbc.edu)

그런데, 실제로 2 + 3 + 4 에 적용해보면, (2 + 3) + 42 + (3 + 4) 두 가지 방법으로 해석될 수 있습니다. 따라서 모호함을 제거하기 위해

expr   ::= term + expr | term
term   ::= factor * term | factor
factor ::= (expr) | nat
nat    ::= 0 | 1 | 2 | ...

이제 2 + 3 + 4 는 확실히 2 + (3 + 4) 입니다. 괴상한 문법을 하스켈로 옮기기 위해 조금 더 다듬어 보도록 하지요.

term + expr | term 은 사실 term + (expr | e) 과 동일합니다. (e비었음 을 의미) factor * term | factorfactor + (term | e) 구요. 따라서

expr   ::= term + (expr | e)
term   ::= factor + (term | e)
factor ::= (expr) | nat
nat    ::= 0 | 1 | 2 | ...

이제 하스켈 코드로 옮길겁니다. 우리는 트리를 만드는 대신 바로바로 계산할 겁니다.

expr :: Parser Int
expr = do t <- term
          do symbol "+"
             e <- expr
             return (t + e)
           +++ return t

term :: Parser Int
term = do f <- factor
          do symbol "*"
             t <- term
             return (t * f)
           +++ return f

factor :: Parser Int
factor = do symbol "("
            e <- expr
            symbol ")"
            return e
          +++ natural          

return t 도 하나의 파서고, +++ 로 둘 중 올바르게 작동하는 파서만 택함으로써 문법에서의 | 를 구현했습니다.

이제 파싱된 결과를 해석하는 eval 함수를 만들어 봅시다.

eval :: String -> Int
eval xs = case parse expr xs of
           [(n, [])] -> n
           [(_, out)] -> error ("ununsed input: " ++ out)
           [] -> error ("invalid input: " ++ xs)


> eval "2 * 3 + 4"
-- 10

> eval "2 * (3 + 4)"
-- 14

> eval "2 * 3 +"
-- *** Exception: ununsed input: +

> eval "2 * 3 - 4"
-- *** Exception: ununsed input: - 4

> eval "-4"
-- *** Exception: invalid input: -4

Programming With Effects

Programming With EffectsProgramming in Haskell 의 저자인 Graham Hutton 이 작성한 글입니다. 모나드에 대해 이보다 쉽고, 간결하게 설명한 글은 찾기 힘들죠.

Programming with Effects 를 참고하여 몇 가지 예제를 더 작성해 보면서 모나드에 더 익숙해져 봅시다.

data Expr = Val Int | Div Expr Expr

위와 같은 Expr 이 있다고 합시다. 평가하기 위해서 eval 함수를 만들고 실행해 봅시다.

eval :: Expr -> Int
eval (Val n) = n
eval (Div x y) = eval x `div` eval y

> eval (Val 3)
-- 3

> eval (Div (Val 3) (Val 4))
-- 0

> eval (Div (Val 8) (Val 4))
-- 2

> eval (Div (Val 8) (Val 0))
-- *** Exception: divide by zero

0 으로 나누니 에러가 발생합니다. exprVal 0 인지 아닌지를 판별할 필요가 있습니다.

조금 더 고쳐보면

import Prelude hiding (Maybe, Just, Nothing)

data Expr = Val Int | Div Expr Expr
data Maybe a = Nothing | Just a

safediv :: Int -> Int -> Maybe Int
safediv n m = if m == 0 then Nothing else Just (n `div` m)

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = case eval x of
                  Nothing -> Nothing
                  Just n -> case eval y of
                             Nothing -> Nothing
                             Just m -> safediv n m

너무 복잡합니다. eval 에서 safediv 에 인자를 넘기는 부분을 추상화하면

seqn :: Maybe a -> Maybe b -> Maybe (a, b)
seqn _ Nothing = Nothing
seqn Nothing _ = Nothing
seqn (Just x) (Just y) = Just (x, y)

apply :: (a -> Maybe b) -> Maybe a -> Maybe b
apply f Nothing = Nothing
apply f (Just x) = f x

eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (Div x y) = apply f (eval x `seqn` eval y)
                 where f (n, m) = safediv n m

조금 더 간편해졌습니다. 그런데 만약 인자가 3개인 연산자에 대해 평가 방법을 정의한다면

eval (Op x y z) = 
  apply f (eval x `seqn` (eval y `seqn` eval z))
  where f (a, (b, c)) =                 

괄호가 점점 중첩됩니다. 모든 것을 나중에 seqn 로 모든 결과를 모아 f 에서 처리하기 보다는 Maybe a 를 받아 a -> Maybe b 를 바로 적용해 Maybe b 를 돌려주고, 이런식으로 순차적으로 처리하는 방식으로 바꿔봅시다.

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
m >>= f = case m of
           Nothing -> Nothing
           Just x -> f x

eval :: Expr -> Maybe Int
eval (Val x) = Just x
eval (Div x y) = eval x >>= \n -> 
                 eval y >>= \m -> 
                 safediv n m 

어디서 많이 보다싶은 식이죠? 바로 하스켈의 do 와 비슷합니다.

하스켈에서 Eq 의 클래스의 정의는 이렇게 되어있습니다.

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool
  
  x /= y = not (x == y)

이 말은 Eq 클래스의 인스턴스가 되는 a 타입은 무조건 == 를 구현해야 한다는 뜻입니다. (/= 는 이미 구현되어 있는거 보이시죠?)

마찬가지로 타입 m 으로 parameterizedMonad 클래스의 인스턴스 또한 다음의 두 함수를 구현해야 합니다.

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

예를 들어 Maybe 같은 경우

instance Monad Maybe where
  return x = Just x
  
  Nothing >>= _ = Nothing
  (Just x) >>= f = f x

List Monad

Maybe 모나드를 잘 보면 Nothing 은 실패를, Just x 는 성공을 나타내는 연산으로 볼 수 있습니다.

리스트 모나드는 이런 개념을 좀 더 일반화한 것입니다. 복수번의 성공이 있을 수 있죠.

instance Monad [] where
  return x = [x]
  xs >>= f = concat (map f xs)

이를 이용하면 pairs 와 같은 함수를 만들수 있습니다.

pairs :: [a] -> [b] -> [(a, b])
pairs xs ys = do x <- xs
                 y <- ys
                 return (x, y)
                 
> pairs [1, 2, 3] [4, 5, 6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]                 

list comprehension 구문과 비슷합니다. 실제로 dolist comprehension 모두 리스트의 >>= 를 이용합니다.

State Monad

한 상태(State) 에서 다른 상태로 변환시켜주는 state transformer 의 타입은 이렇게 정의할 수 있을 겁니다.

type ST = State -> State

그리고 상태가 변하면서 어떤 정보를 남겼을때의 타입을 이렇게 만들어 볼 수 있겠죠.

type ST a = State -> (a, State)

어디서 많이 본것 같죠? 맞습니다. 위에서 본 Parser 입니다. String -> (a, String) 이였으니까, StateString 이었던 거죠.

instance Monad ST where
  return x = \s -> (x, s)
  
  st >>= f = \s -> let (x, s') = st s
                   in f x s'

누차 언급했듯이 >>= 는 모나드(연산)간 연결입니다. sts 를 넣은 결과를 (x, s') 라 하면 다시 f xs 를 넣어 연결할 수 있다는 뜻이지요.

위에서는 type 을 사용했지만 실제로 이 키워드를 사용하면 클래스의 인스턴스가 될 수 없습니다. STmonadic type 클래스의 인스턴스로 만들려면 datanewtype 을 이용할 수 있습니다. data 의 경우엔 dummy constructor 가 필요합니다. 여기선 S 가 되겠습니다. dummy constructor 의 런타임 오버헤드를 피하려면 newtype 을 이용하면 됩니다.

그리고 이 예제에서는 dummy constructor 를 제거하기 위해 apply 함수를 만들어서 이용하겠습니다.

State 는 정수로 표시할겁니다.

type State = Int
data ST a = S (State -> (a, State))

apply :: ST a -> State -> (a, State)
apply (S f) x = f x

instance Monad ST where
  return x = S (\s -> (x, s))
  st >>= f = S (\s -> let (x, s') = apply st s in apply (f x) s')

이제 예제에서 활용할 간단한 이진트리를 정의해 봅시다. 이진트리의 leafa 타입의 값을 가지고 있습니다.

data Tree = Leaf a | Node (Tree a) (Tree b)

-- example
tree :: Tree Char
tree = Node (Node (Leaf 'a') (Leaf 'b')) (Leaf 'c')

이제 State 를 받아 +1 을 더한 다음 State 를 돌려주는 fresh 를 만들어 봅시다.

-- data ST a = S (State -> (a, State))

fresh :: ST Int
fresh = S (\n -> (n, n + 1))

freshState1 만큼 증가시키고 부가정보로 current state n 을 남깁니다. fresh 를 이용하면 위에서 만든 이진트리를 순회하면서 번호를 붙일 수 있습니다. 부가정보로 남는 nLeaf 에다가 붙이는 것이죠.

다음 fresh 의 입력은 이전 fresh 의 아웃풋인 n + 1 이기 때문에 서로 다른 두 노드가 같은 숫자를 가질 일은 없습니다.

mlabel :: Tree a -> ST (Tree (a, Int))
mlabel (Leaf x) = do n <- fresh
                     return (Leaf (x, n))
mlabel (Node l r) = do l' <- mlabel l
                       r' <- mlabel r
                       return (Node l' r')
                       
label  :: Tree a -> Tree (a,Int)
label t = fst (apply (mlabel t) 0)

> label tree
-- Node (Node (Leaf ('a',0)) (Leaf ('b',1))) (Leaf ('c',2))

IO Monad

하스켈에서 입출력은 IO 모나드를 이용합니다. 무슨말인고 하니, 다음과 같은 axioms 를 구현한 IO 모나드 에 대해

return  :: a -> IO a
(>>=)   :: IO a -> (a -> IO b) -> IO b
getChar :: IO Char
putChar :: Char -> IO ()

다음처럼 do 구문을 이용해서 프로그램을 작성할 수 있다는 뜻입니다.

getLine :: IO String
getLine = do x <- getChar
             if x == '\n' then
               return []
             else
               do xs <- getLine
                  return (x:xs)

IO 모나드는 State 모나드 라 볼 수 있습니다. IO a 는 타입 a 의 부가정보를 만들면서 State 를 변화시키는 것으로요

type World = ...
type IO a = World -> (a, World)

여기서 입/출력이 수행되는 것은 action 에 의해 World 가 변경되는 것이라 볼 수 있습니다.

Derived Primitives

다양한 종류의 모나드에 대해 적용할 수 있는 함수를 만들 수 있습니다.

liftM 는 모나드에 대한 mapjoinconcat 을, >> 는 첫 번째 결과값을 다 버리고 두번째만 취하는 함수입니다. 마지막으로 sequence 는 모나드 익스프레션 리스트를 하나의 모나드 익스프레션으로 바꾸고, 그 결과를 리스트로 돌려줍니다. 타입을 보시면 이해가 빠를겁니다.

liftM :: Monad m => (a -> b) -> m a -> m b
liftM f mx = do x <- mx
             return (f x)
             
join :: Monad m => m (m a) -> m a
join mmx = do mx <- mmx
              x <- mx
              return x
           
(>>) :: Monad m => m a -> m b -> m b
mx >> my = do _ <- mx
              y <- my
              return y
              
sequence :: Monad m => [m a] -> m [a]
sequence (mx:mxs) = do x <- mx
                       xs <- sequence mxs
                       return (x:xs)

References

(1) DelftX FP 101x
(2) error in sat function in “Programming in Haskell”
(3) http://wiki.reeseo.net/Haskell
(4) Understanding Monads
(5) http://www.csee.umbc.edu
(6) Programming With Effects by Graham Hutton

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.