Real World Haskell 부록 B 번역: 문자, 문자열, 이스케이프 규칙Real World Haskell 부록 B 번역: 문자, 문자열, 이스케이프 규칙

Posted at 2015.02.01 23:45 | Posted in 지식저장소/읽은 책 요약
부록 B. 문자, 문자열, 이스케이프 규칙

부록 B. 문자, 문자열, 이스케이프 규칙

이 부록은 비 아스키 문자를 하스켈 문자와 문자열에 사용하는 이스케이프 규칙을 다룹니다. 하스켈의 이스케이프 규칙은 C언어에서 쓰는 방식을 따르지만, 거기에 대해 좀 부연하겠습니다.

문자와 문자열 나타내기

아스키 작은 따옴표 '로 감싼 문자 하나는 Char 타입을 가집니다.

ghci> 'c'
'c'
ghci> :type 'c'
'c' :: Char

문자열 상수는 큰 따옴표 "로 감싸고, [Char] 타입을 가집니다 (보통 String으로 씁니다).

ghci> "a string literal"
"a string literal"
ghci> :type "a string literal"
"a string literal" :: [Char]

큰따옴표 문자열은 단지 리스트 표기법의 설탕 구문입니다.

ghci> ['a', ' ', 's', 't', 'r', 'i', 'n', 'g'] == "a string"
True

다국어 지원

하스켈은 Char 데이터 타입을 위해 내부적으로 유니코드를 사용합니다. String[Char], 즉 Char 리스트이기에 문자열에도 또한 유니코드를 씁니다.

각각의 하스켈 구현은 소스 파일에서 쓸 수 있는 문자 집합에 제한을 둡니다. GHC는 UTF-8 소스파일을 허용하기에 문자나 문자열 상수로 UTF-8 상수를 쓸 수 있습니다. UTF-8을 소스파일에 쓰면 다른 하스켈 구현은 파싱할 수 없을 수도 있기에 유의해야 합니다.

ghci 인터프리터를 실행 중일 땐 키보드로 입력한 비아스키 문자나 문자열은 잘 다루지 못할 수도 있습니다.

유의

하스켈이 문자와 문자열을 유니코드로 다룬다지만, 유니코드 데이터를 담은 파일에 대한 입출력 방법은 표준화되지 않았습니다. 하스켈의 표준 입출력 함수는 텍스트를 8비트 문자의 나열로 간주하고, 그 어떤 문자 집합 변환도 수행하지 않습니다.

파일에 쓰는 다양한 인코딩과 하스켈의 내부 유니코드 간 변환을 해주는 서드 파티 라이브러리도 있습니다.

텍스트 이스케이핑

일부 문자는 문자나 문자열 상수로 표현할 때 반드시 이스케이프되어야 합니다. 예를 들어, 큰따옴표 문자는 문자열 안에서 이스케이프하지 않으면 문자열의 끝으로 간주되기 때문에 이스케이프가 필요합니다.

단일 문자 이스케이프 코드

하스켈은 기본적으로 C언어와 다른 유명한 언어의 단일 이스케이프 문자를 사용합니다.

표 B.1. 단일 문자 이스케이프 코드

이스케이프 유니코드 문자
\0 U+0000 널 문자
\a U+0007 비프음
\b U+0008 백스페이스
\f U+000C 폼 피드
\n U+000A 개행 (라인 피드)
\r U+000D 커리지 리턴
\t U+0009 수평 탭
\v U+000B 수직 탭
\" U+0022 큰따옴표
\& n/a 빈 문자열
\' U+0027 작은 따옴표
\\ U+005C 백슬래시

여러 줄 문자열 상수

여러 줄에 걸쳐 문자열을 쓰고 싶을 땐, 한 줄을 백슬래시로 끝내고, 다시 백슬래시로 문자열을 시작하면 됩니다. 아무 종류의 공백이든 두 백슬래시 사이에 넣어도 됩니다.

"this is a \
  \long string,\
    \ spanning multiple lines"

아스키 제어 문자

하스켈은 두 글자나 세 글자의 아스키 제어문자 약어를 인식합니다.

표 B.2. 아스키 제어 문자 약어

이스케이프 유니코드 의미
\NUL U+0000 널 문자
\SOH U+0001 start of heading
\STX U+0002 start of text
\ETX U+0003 end of text
\EOT U+0004 end of transmission
\ENQ U+0005 enquiry
\ACK U+0006 acknowledge
\BEL U+0007 bell
\BS U+0008 백스페이스
\HT U+0009 수평 탭
\LF U+000A 라인 피드 (개행)
\VT U+000B 수직 탭
\FF U+000C 폼 피드
\CR U+000D 커리지 리턴
\SO U+000E 시프트 아웃
\SI U+000F 시프트 인
\DLE U+0010 data link escape
\DC1 U+0011 device control 1
\DC2 U+0012 device control 2
\DC3 U+0013 device control 3
\DC4 U+0014 device control 4
\NAK U+0015 negative acknowledge
\SYN U+0016 synchronous idle
\ETB U+0017 end of transmission block
\CAN U+0018 cancel
\EM U+0019 end of medium
\SUB U+001A substitute
\ESC U+001B escape
\FS U+001C file separator
\GS U+001D group separator
\RS U+001E record separator
\US U+001F unit separator
\SP U+0020 스페이스
\DEL U+007F delete

컨트롤 첨부 문자 이스케이프

하스켈은 키보드의 컨트롤키를 다른 키와 같이 눌렀을 때 나오는 옛날 나오던 문자를 연상시키는, 제어 문자에 대한 다른 표기법을 인식합니다. 이 시퀀스는 \^ 뒤에 기호나 알파벳 대문자가 따라옵니다.

표 B.3. 컨트롤 문자 코드

이스케이프 유니코드 의미
\^@ U+0000 널 문자
\^A에서 \^Z까지 U+0001에서 U+001A까지 제어 코드
\^[ U+001B escape
\^\ U+001C file separator
\^] U+001D group separator
\^^ U+001E record separator
\^_ U+001F unit separator

숫자 이스케이프

하스켈에선 숫자 이스케이프로 유니코드 문자를 표현할 수 있습니다. 10진 문자는 숫자 문자로 시작하고(예: \1234), 16진 문자는 x로 시작하고(예: \xbeef), 8진 문자는 o로 시작합니다(예: \o1234).

숫자 이스케이프의 최대 값은 \1114111이고, \x10ffff\o4177777와 같습니다.

너비 없는 이스케이프 시퀀스

문자열 상수는 \&로 쓰는 폭이 없는 이스케이프 시퀀스를 포함할 수 있습니다. 이건 실제 문자가 아니고, 빈 문자열을 나타냅니다.

ghci> "\&"
""
ghci> "foo\&bar"
"foobar"

이 이스케이프 시퀀스는 숫자 이스케이프 다음에 곧바로 아스키 숫자를 쓰는 걸 가능하게 만들기 위해 있는 것입니다.

ghci> "\130\&11"
"\130\&11"

빈 이스케이프 시퀀스는 빈 문자열을 나타내기 때문에 적법한 문자 상수는 아닙니다.

저작자 표시 비영리 동일 조건 변경 허락
신고

Real World Haskell 15장 번역: 모나드로 프로그래밍하기Real World Haskell 15장 번역: 모나드로 프로그래밍하기

Posted at 2015.02.01 19:41 | Posted in 지식저장소/읽은 책 요약
15장. 모나드로 프로그래밍하기

15장. 모나드로 프로그래밍하기

골프 연습: 관계 리스트

웹 서버와 클라이언트는 텍스트로 자주 키-값 쌍을 표현해 서로 전달합니다.

name=Attila+%42The+Hun%42&occupation=Khan

이 인코딩은 application/x-www-form-urlencoded라고 부르고, 매우 이해하기 쉽습니다. 각각의 키-값 쌍은 “&” 문자로 구분합니다. 키-값 쌍 안에선 키 문자열이 나오고 “=”가 따라온 다음 값 문자열이 나옵니다.

키는 간단히 String으로 나타낼 수 있지만, HTTP 명세에선 값이 반드시 키 뒤에 나와야 하는지 알려주지 않습니다. 우린 이 애매함을 값 타입으로 Maybe String을 써 해결할 수 있습니다. 값으로 Nothing을 쓰면, 값이 따라오지 않은 것입니다. 문자열을 Just로 감싸면, 값이 있던 것입니다. Maybe를 써서 “값이 없는 것”과 “빈 값”을 구분할 수 있습니다.

하스켈 프로그래미들은 각각의 원소를 키와 값의 관계로 생각할 수 있는 [(a, b)]타입을 관계 리스트Association list라고 부릅니다. 이 이름은 리스프 커뮤니티에서 유래했고, 거기선 흔히 alist라고 줄여 부릅니다. 위 문자열을 다음 하스켈 값으로 나타낼 수 있습니다.

-- file: ch15/MovieReview.hs
    [("name",       Just "Attila \"The Hun\""),
     ("occupation", Just "Khan")]

“URL 인코딩한 질의 문자열” 절에서, application/x-www-form-urlencoded 문자열을 파싱하고 그 결과를 [(String, Maybe String)]로 나타낼 겁니다. 우리가 자료구조를 채우는 데 이 관계 리스트를 사용하고 싶다고 해 봅시다.

-- file: ch15/MovieReview.hs
data MovieReview = MovieReview {
      revTitle :: String
    , revUser :: String
    , revReview :: String
    }

명백한 것들을 생각 없이 길게 늘여써 시작하겠습니다.

-- file: ch15/MovieReview.hs
simpleReview :: [(String, Maybe String)] -> Maybe MovieReview
simpleReview alist =
  case lookup "title" alist of
    Just (Just title@(_:_)) ->
      case lookup "user" alist of
        Just (Just user@(_:_)) ->
          case lookup "review" alist of
            Just (Just review@(_:_)) ->
                Just (MovieReview title user review)
            _ -> Nothing -- no review
        _ -> Nothing -- no user
    _ -> Nothing -- no title

이 함수는 관계 리스트가 필요한 모든 값을 가지고 있고, 그 값들이 빈 문자열이 아니어야만 MovieReview를 반환합니다. 하지만, 입력 값을 검사한다는 사실만이 유일한 장점이고, 이 함수는 우리가 피해야 한다고 배운 “계단화”가 심각하고, 관계 리스트의 세부 구조까지 알고 있습니다.

우린 이제 Maybe 모나드에 익숙해졌으므로, 이 계단 코드를 가지런히 할 수 있습니다.

-- file: ch15/MovieReview.hs
maybeReview alist = do
    title <- lookup1 "title" alist
    user <- lookup1 "user" alist
    review <- lookup1 "review" alist
    return (MovieReview title user review)

lookup1 key alist = case lookup key alist of
                      Just (Just s@(_:_)) -> Just s
                      _ -> Nothing

더 깔끔해졌지만, 아직 반복 부분이 남아있습니다. 우린 MovieReview 생성자가 “순수 코드와 모나딕 코드 섞기” 절에서 봤듯이 모나드 안으로 일반 순수 함수를 리프팅하는 것과 마찬가지로 동작한다는 걸 이용할 수 있습니다.

-- file: ch15/MovieReview.hs
liftedReview alist =
    liftM3 MovieReview (lookup1 "title" alist)
                       (lookup1 "user" alist)
                       (lookup1 "review" alist)

여기서도 아직 반복이 약간 남아있지만, 상당히 적고, 또한 제거하기도 더 까다롭습니다.

일반화된 리프팅

liftM3가 우리 코드를 정리해주지만, 표준 라이브러리엔 liftM5까지밖에 없으므로 liftM 계열 함수로 이 종류의 문제를 해결할 순 없습니다. 우리가 필요한 숫자의 liftM 변종을 만들 수도 있지만, 노가다에 불과할 겁니다.

만약 우리가 표준 라이브러리를 고수한 상태에서 10개 정도의 인자를 받는 생성자나 순수 함수가 있다면 독자는 이제 끝났다고 생각할지도 모릅니다.

물론, 우리 도구상자는 아직 고갈나지 않았습니다. Control.Monadap라는 흥미로운 타입 시그니처를 가진 함수가 있습니다.

ghci> :m +Control.Monad
ghci> :type ap
ap :: (Monad m) => m (a -> b) -> m a -> m b

독자는 누가 왜 인자 하나를 받는 순수 함수를 모나드 안에 집어넣으려 할 지 의문일 수 있습니다. 하지만 모든 하스켈 함수는 실제론 인자 하나만을 받는다는 걸 떠올리시고, 이게 MovieReview 생성자와 어떤 관계가 있는지 봅시다.

ghci> :type MovieReview
MovieReview :: String -> String -> String -> MovieReview

우린 이 타입을 String -> (String -> (String -> MovieReview))라고 쉽게 쓸 수 있습니다. 만약 기존의 liftM으로 MovieReviewMaybe 모나드 안으로 리프팅하면, Maybe (String -> (String -> (String -> MovieReview))) 타입의 값을 얻을 겁니다. 이 값을 ap에 인자로 주면 Maybe (String -> (String -> MovieReview)) 타입이 결과로 나오는 걸 알 수 있습니다. 이 결과도 차례로 ap에 넘겨 이 정의가 끝날 때까지 연쇄할 수 있습니다.

-- file: ch15/MovieReview.hs
apReview alist =
    MovieReview `liftM` lookup1 "title" alist
                   `ap` lookup1 "user" alist
                   `ap` lookup1 "review" alist

이런 식으로 ap를 필요한 만큼 연쇄해 liftM 계열 함수를 피할 수 있습니다.

ap을 다르게 보면 ap($) 연산자의 모나딕 버전이라고 생각할 수 있습니다. ap의 발음을 어플라이apply라고 생각하세요. 두 함수의 타입 시그니처를 비교해 이 사실을 명확히 볼 수 있습니다.

ghci> :type ($)
($) :: (a -> b) -> a -> b
ghci> :type ap
ap :: (Monad m) => m (a -> b) -> m a -> m b

실제로, liftM2 idliftM2 ($)ap을 정의할 수 있습니다.

다른 방법 찾기

아래는 개인 전화번호의 간단한 표현입니다.

-- file: ch15/VCard.hs
data Context = Home | Mobile | Business
               deriving (Eq, Show)

type Phone = String

albulena = [(Home, "+355-652-55512")]

nils = [(Mobile, "+47-922-55-512"), (Business, "+47-922-12-121"),
        (Home, "+47-925-55-121"), (Business, "+47-922-25-551")]

twalumba = [(Business, "+260-02-55-5121")]

우리가 누군가와 사적인 통화를 하고 싶다고 생각해 봅시다. 회사 전화번호로 걸고 싶진 않을 것이고, 휴대폰보단 (집 전화가 있다면) 집 전화가 나을 것입니다.

-- file: ch15/VCard.hs
onePersonalPhone :: [(Context, Phone)] -> Maybe Phone
onePersonalPhone ps = case lookup Home ps of
                        Nothing -> lookup Mobile ps
                        Just n -> Just n

물론 Maybe를 결과 타입으로 쓰면, 누군가 이 기준을 만족하는 전화번호가 2개 이상 있을 때를 처리하지 못 합니다. 이 경우를 대비해, 리스트 타입으로 바꾸겠습니다.

-- file: ch15/VCard.hs
allBusinessPhones :: [(Context, Phone)] -> [Phone]
allBusinessPhones ps = map snd numbers
    where numbers = case filter (contextIs Business) ps of
                      [] -> filter (contextIs Mobile) ps
                      ns -> ns

contextIs a (b, _) = a == b

두 함수의 case 식이 비슷한 것에 주목하세요. 한 개 짜리 결과 함수는 룩업이 빈 결과를 반환했는지 아닌지에 따라 결과를 처리했습니다.

ghci> onePersonalPhone twalumba
Nothing
ghci> onePersonalPhone albulena
Just "+355-652-55512"
ghci> allBusinessPhones nils
["+47-922-12-121","+47-922-25-551"]

하스켈의 Control.Monad 모듈은 이런 case 식을 추상화 할 수 있는 MonadPlus 타입클래스를 정의해 뒀습니다.

-- file: ch15/VCard.hs
class Monad m => MonadPlus m where
   mzero :: m a 
   mplus :: m a -> m a -> m a

mzero 빈 값을 나타내는 반면, mplus는 결과를 하나로 합칩니다. 아래는 Maybe와 리스트의 mzeromplus 표준 정의입니다.

-- file: ch15/VCard.hs
instance MonadPlus [] where
   mzero = []
   mplus = (++)

instance MonadPlus Maybe where
   mzero = Nothing

   Nothing `mplus` ys  = ys
   xs      `mplus` _ = xs

이제 우린 mpluscase식 전체를 제거할 수 있습니다. 다양한 방법을 보는 셈 치고, 한 개 회사 전화번호와 모든 개인 전화번호를 가져와봅시다.

-- file: ch15/VCard.hs
oneBusinessPhone :: [(Context, Phone)] -> Maybe Phone
oneBusinessPhone ps = lookup Business ps `mplus` lookup Mobile ps

allPersonalPhones :: [(Context, Phone)] -> [Phone]
allPersonalPhones ps = map snd $ filter (contextIs Home) ps `mplus`
                                 filter (contextIs Mobile) ps

각각의 함수에서 lookupMaybe를 반환하고 filter가 리스트를 반환하는 걸 알기에, 각각 어떤 mplus 구현이 쓰일지 명백합니다.

더 재밌는 사실은 mzeromplus모든 MonadPlus 인스턴스에 유용한 함수를 짤 수 있다는 겁니다. 예를 들어, 아래는 Maybe 값을 반환하는 표준 lookup 함수입니다.

-- file: ch15/VCard.hs
lookup :: (Eq a) => a -> [(a, b)] -> Maybe b
lookup _ []                      = Nothing
lookup k ((x,y):xys) | x == k    = Just y
                     | otherwise = lookup k xys

임의의 MonadPlus 인스턴스의 결과 타입을 다음처럼 쉽게 일반화할 수 있습니다.

-- file: ch15/VCard.hs
lookupM :: (MonadPlus m, Eq a) => a -> [(a, b)] -> m b
lookupM _ []    = mzero
lookupM k ((x,y):xys)
    | x == k    = return y `mplus` lookupM k xys
    | otherwise = lookupM k xys

이걸로 결과 타입이 Maybe면 결과가 없거나 하나의 결과를 얻을 수 있고, 리스트면 모든 결과를 얻고, 다른 생소한 MonadPlus 인스턴스에 대해서도 적절히 결과를 얻을 겁니다.

위에서 본 것과 같은 작은 함수들의 경우엔, mplus를 사용해도 거의 효용이 없습니다. mplus의 장점은 더 복잡한 코드나 모나드 문맥에 독립적인 코드에서 드러납니다. 비록 MonadPlus를 독자의 코드에서 쓸 필요를 못 찾았더라도, 다른 사람의 프로젝트에서 맞닥뜨릴 수도 있습니다.

mplus란 이름은 덧셈을 뜻하지 않습니다

mplus 함수 이름에 “plus”란 단어가 있긴 하지만, 이것이 두 값을 더하는 걸 의미한다고 생각해선 안 됩니다.

우리가 작업하는 모나드에 따라, mplus는 덧셈처럼 보이는 작업을 구현할 수도 있습니다. 예를 들어, 리스트의 mplus(++) 연산자로 정의했습니다.

ghci> [1,2,3] `mplus` [4,5,6]
[1,2,3,4,5,6]

하지만 다른 모나드로 바꾼다면, 이 명백한 덧셈과의 유사성은 사라집니다.

ghci> Just 1 `mplus` Just 2
Just 1

MonadPlus를 다루는 규칙

MonadPlus 타입클래스의 인스턴스는 일반적인 모나드 규칙과 더불어 몇가지 규칙을 더 지켜야 합니다.

인스턴스는 mzero가 바인드 식 왼쪽에 오면 반드시 단축 평가를 해야 합니다. 즉, mzero >>= f 식은 mzero와 같은 결과를 반환해야 합니다.

-- file: ch15/MonadPlus.hs
    mzero >>= f == mzero

인스턴스는 mzero가 시퀀스 식 오른쪽에 오면 단축평가를 해야 합니다.

-- file: ch15/MonadPlus.hs
    v >> mzero == mzero

MonadPlus로 안전하게 실패하기

“모나드 타입클래스” 절에서 fail을 소개했을 때, 오남용하지 말라고 경고했습니다. 대부분의 모나드에서, fail은 불행한 결과를 가져올 error로 정의되어 있습니다.

MonadPlus 타입클래스는 재앙을 초래할 fail이나 error 없이도 계산을 실패할 더 신사적인 방법을 제공합니다. 우리가 위에서 소개한 규칙이 mzero를 코드 어느 지점에든 끼워넣어, 그 곳부터 단축 평가를 하도록 만들어줍니다.

Control.Monad 모듈에서, 표준 함수 guard는 이 아이디어를 편리한 형태로 싸맸습니다.

-- file: ch15/MonadPlus.hs
guard        :: (MonadPlus m) => Bool -> m ()
guard True   =  return ()
guard False  =  mzero

간단한 예로, 아래는 숫자 x를 받아 모듈로 n을 구하는 함수입니다. 결과가 0이면 x를 반환하고, 아니면 현재 모나드의 mzero를 반환합니다.

-- file: ch15/MonadPlus.hs
x `zeroMod` n = guard ((x `mod` n) == 0) >> return x

배관 숨기기의 장점

“상태 모나드 사용하기: 랜덤 값 생성” 절에서, State 모나드로 어떻게 쉽게 난수에 접근할 수 있는지 그 방법을 보았습니다.

우리가 개발한 코드의 단점은 그 코드가 새기 쉽다는 것입니다. 누군가 그 코드를 사용하는 사람이 그 코드가 State 모나드 안에서 돌아갈 걸 안다고 해 봅시다. 그건 사용자도 제작자 만큼이나 쉽게 난수 생성기의 상태를 조사하고 바꿀 수 있다는 걸 의미합니다.

우리가 내부 구현을 노출한 채 남겨두면, 누군간 당연히 인간의 본능에 따라 그 부분을 파고들어 원숭이같은 짓을 할 겁니다. 작은 프로그램엔 괜찮을 수 있지만, 더 큰 소프트웨어 프로젝트에선, 한 사용자가 다른 사용자가 준비하지 못한 상태에서 내부 구현을 수정해 놓으면, 발생하는 버그는 추적하기 매우 어려운 축에 들어갈 겁니다. 이런 버그는 우리가 다른 모든 가능성을 조사해보고 탈진한 다음 절대 깨질 것 같지 않은 라이브러리에 대한 기본 전제가 깨져야 해결할 수준입니다.

게다가 한번 우리 구현을 노출한 채로 두면, 누군가 바른 의도를 가진 사람이 불가피하게 API를 우회해 구현을 직접 사용한다면, 우리가 버그를 고치거나 개량을 할 때 옴싹달싹 못하게 됩니다. 내부 구현을 수정하고 거기에 의존하는 코드를 포기하거나, 내부 구현에 얽매이고 가능한 다른 우회책을 찾아야 합니다.

어떻게 State 모나드를 사용한다는 걸 숨기도록 난수 모나드를 개선할 수 있을까요? 우리 사용자가 get이나 put을 호출하는 걸 막을 방법을 찾아야 합니다. 이건 하기 어렵지 않고, 매일의 하스켈 프로그래밍에 재활용할 약간의 기교를 도입합니다.

범위를 넓혀, 난수를 넘어 임의 종류의 고유한 값을 제공하는 모나드를 구현하겠습니다. 이번에 만들 모나드 이름은 Supply입니다. 우린 실행 함수 runSupply과 값의 리스트를 제공할 겁니다. 각각의 원소가 고유할지는 우리에게 달렸습니다.

-- file: ch15/Supply.hs
runSupply :: Supply s a -> [s] -> (a, [s])

이 모나드는 값이 난수일지, 임시 파일 이름일지, HTTP 쿠키 ID일지 신경쓰지 않을 겁니다.

모나드 안에서 사용자가 값을 요구할 때마다 next 액션은 리스트에서 다음 하나를 가져와 사용자에게 전달할 겁니다. 각각의 값은 리스트가 부족할 경우를 대비해 Maybe 생성자로 감쌉니다.

-- file: ch15/Supply.hs
next :: Supply s (Maybe s)

우리 배관을 감추기 위해서, 모듈 헤더에 타입 생성자와 실행 함수, next 액션만 드러내도록 하겠습니다.

-- file: ch15/Supply.hs
module Supply
    (
      Supply
    , next
    , runSupply
    ) where

라이브러리를 불러오는 모듈이 모나드의 내부를 못 보기 때문에, 내부를 조작할 수 없습니다.

이 배관 공사는 극히 간단합니다. 우린 기존의 State 모나드를 감싸기 위해 newtype 선언을 썼습니다.

-- file: ch15/Supply.hs
import Control.Monad.State

newtype Supply s a = S (State [s] a)

s 인자는 우리가 제공할 고유한 값의 타입이고, a는 이 타입을 모나드로 만들기 위해 반드시 제공해야 하는 보통의 타입 인자입니다.

Supplynewtype으로 선언한 것과 모듈 헤더로 사용자가 State 모나드의 getset 액션을 쓰는 것을 막고 있습니다. 우리 모듈이 S 데이터 생성자를 드러내지 않았기 때문에, 사용자는 프로그래밍적 방법으로 우리가 State 모나드를 쓰고 있다는 걸 알거나, 접근할 수 없습니다.

이제 Monad 타입클래스의 인스턴스로 만들어야 하는 Supply 타입을 만들었습니다. 평범하게 (>>=)return을 정의할 수도 있지만, 그러면 순수한 보일러플레이트 코드가 될 겁니다. 우리가 해야할 건 State 모나드의 (>>=)returnS 값 생성자로 감싸거나 푸는 것입니다. 아래는 그런 코드의 예시입니다.

-- file: ch15/AltSupply.hs
unwrapS :: Supply s a -> State [s] a
unwrapS (S s) = s

instance Monad (Supply s) where
    s >>= m = S (unwrapS s >>= unwrapS . m)
    return = S . return

하스켈 프로그래머는 보일러플레이트를 별로 좋아하지 않고, GHC는 물론 이런 작업을 없애줄 달콤한 언어 확장을 가지고 있습니다. 이 언어 확장을 사용하기 위해 모듈 헤더 전 우리 소스 파일의 맨 위에 다음 지시자를 넣을 겁니다.

-- file: ch15/Supply.hs
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

대개 ShowEq같은 일부의 표준 타입클래스만 자동으로 인스턴스를 선언할 수 있습니다. 이름이 알려주듯이 GeneralizedNewtypeDeriving 확장은 타입클래스 인스턴스 자동 선언 범위를 넓혀주고, newtype에만 적용됩니다. 어떤 타입클래스의 인스턴스를 newtype으로 감싼다면, 새 타입도 자동으로 다음과 같이 그 타입클래스의 인스턴스가 될 겁니다.

-- file: ch15/Supply.hs
    deriving (Monad)

이건 밑바탕 타입의 (>>=)return의 구현을 사용하고, S 데이터 생성자로 필요한 감싸기와 풀기를 진행하는 함수를 만들어 Monad 인스턴스를 끌어내는 데 사용합니다.

우리가 여기서 얻은 이득은 이 예제 너머에 있습니다. 우리는 newtype을 밑바탕 타입을 감싸는 데 쓸 수 있고, 우리가 원하는 타입클래스만 노출할 수 있으며, 거의 노력을 들이지 않고도 더 특수화된 타입을 만들 수 있습니다.

이제 GeneralizedNewtypeDeriving 기법을 봤으니, 남은 것은 nextrunSupply를 정의하는 것 뿐입니다.

-- file: ch15/Supply.hs
next = S $ do st <- get
              case st of
                [] -> return Nothing
                (x:xs) -> do put xs
                             return (Just x)

runSupply (S m) xs = runState m xs

모듈을 ghci로 불러와, 몇가지 방법으로 시험해 볼 수 있습니다.

ghci> :load Supply
[1 of 1] Compiling Supply           ( Supply.hs, interpreted )
Ok, modules loaded: Supply.
ghci> runSupply next [1,2,3]
Loading package mtl-1.1.0.0 ... linking ... done.
(Just 1,[2,3])
ghci> runSupply (liftM2 (,) next next) [1,2,3]
((Just 1,Just 2),[3])
ghci> runSupply (liftM2 (,) next next) [1]
((Just 1,Nothing),[])

또한 State 모나드가 새지 않는 것도 확인할 수 있습니다.

ghci> :browse Supply
data Supply s a
next :: Supply s (Maybe s)
runSupply :: Supply s a -> [s] -> (a, [s])
ghci> :info Supply
data Supply s a   -- Defined at Supply.hs:17:8-13
instance Monad (Supply s) -- Defined at Supply.hs:17:8-13

난수 제공하기

Supply 모나드를 난수 생성기로 쓰려고 한다면, 몇가지 어려움을 당면합니다. 가능하면, 이 모나드로 무한 난수 스트림을 제공하고 싶을 것입니다. StdGenIO 모나드 안에서 받아올 순 있지만, 작업이 끝나면 다른 StdGen을 반드시 “도로 넣어야” 합니다. 그러지 않으면 StdGen을 쓰는 다음 코드 조각도 같은 상태에 있게 될 겁니다. 이건 충분히 재앙이 될 수 있는, 매번 같은 난수가 나오는 상황을 의미합니다.

지금까지 본 System.Random 모듈의 일부분으로 생각하면, 이 요구조건을 만족시키긴 어렵습니다. 타입에서 StdGen 하나를 받고 다른 StdGen을 되돌려주는 걸 보장하는 getStdRandom을 쓸 수 있습니다.

ghci> :type getStdRandom
getStdRandom :: (StdGen -> (a, StdGen)) -> IO a

난수를 받을 때 새 StdGen도 받기 위해 random을 사용할 수 있습니다. 무한 난수 리스트를 받기 위해 randoms를 사용할 수 있습니다. 하지만 어떻게 무한 난수 리스트StdGen을 동시에 받을 수 있을까요?

난수 생성기 하나를 받고 두 난수 생성기로 바꿔주는 RandomGen 타입 클래스의 split 함수에 답이 있습니다. 난수 생성기를 이처럼 분할하는 건 가능하다는 건 매우 이상해 보입니다. 이건 순수 함수형 환경에서 매우 유용하지만, 비순수 언어에선 필요하지도 않고 제공하지도 않을 것입니다.

split 함수로 얻는 StdGen 하나는 runSupply에 넘겨줄 무한 난수 리스트를 생성하는 데 사용할 수 있고, 다른 하나는 IO 모나드에 넘겨줍니다.

-- file: ch15/RandomSupply.hs
import Supply
import System.Random hiding (next)

randomsIO :: Random a => IO [a]
randomsIO =
    getStdRandom $ \g ->
        let (a, b) = split g
        in (randoms a, b)

만약 우리가 이 함수를 제대로 구현했다면, 우리 예제는 호출할 때마다 매번 다른 값을 반환해야 합니다.

ghci> :load RandomSupply
[1 of 2] Compiling Supply           ( Supply.hs, interpreted )
[2 of 2] Compiling RandomSupply     ( RandomSupply.hs, interpreted )
Ok, modules loaded: RandomSupply, Supply.
ghci> (fst . runSupply next) `fmap` randomsIO

<interactive>:1:17:
    Ambiguous occurrence `next'
    It could refer to either `Supply.next', imported from Supply at RandomSupply.hs:4:0-12
                                              (defined at Supply.hs:32:0)
                          or `System.Random.next', imported from System.Random
ghci> (fst . runSupply next) `fmap` randomsIO

<interactive>:1:17:
    Ambiguous occurrence `next'
    It could refer to either `Supply.next', imported from Supply at RandomSupply.hs:4:0-12
                                              (defined at Supply.hs:32:0)
                          or `System.Random.next', imported from System.Random

runSupply 함수는 실행한 모나딕 액션의 결과와 쓰고 남은 리스트를 반환한다는 걸 떠올리세요. 우리가 무한 난수 리스트를 넘겼기 때문에, fst를 합성해서 ghci가 결과를 출력할 때 난수 해일에 빠지는 걸 방지합니다.

또다른 골프 라운드

쌍의 한 원소에 함수를 적용하고 다른 원소는 냅둔 채 그 원소만 바꾼 새 쌍을 만드는 건 표준 코드가 될 만큼 하스켈에서 빈번했습니다.

Control.Arrow 모듈엔 firstsecond라는 그런 동작을 하는 함수가 있습니다.

ghci> :m +Control.Arrow
ghci> first (+3) (1,2)
(4,2)
ghci> second odd ('a',1)
('a',True)

(실제로, “겹친 인스턴스 없는 JSON 타입클래스” 절에서 이미 second 함수를 봤습니다.) 우리 randomsIO 정의에 first를 활용해 한 줄 짜리로 만들 수 있습니다.

-- file: ch15/RandomGolf.hs
import Control.Arrow (first)

randomsIO_golfed :: Random a => IO [a]
randomsIO_golfed = getStdRandom (first randoms . split)

인터페이스와 구현 분리하기

이전 장에서, 어떻게 Supply의 상태를 유지하기 위해 State 모나드를 사용하는 걸 숨기는지 봤습니다.

코드를 조립이 편리하게 만들기 위한 또다른 중요한 방법은 인터페이스—코드가 무엇을 할 수 있는지—와 그 구현—어떻게 하는지—를 분리하는 것입니다.

System.Random에 있는 표준 난수 생성기는 꽤 느리다고 합니다. 우리가 Supply에 난수를 공급하는 데 randomsIO 함수를 쓰면, next 액션은 그리 빠르지 못할 것입니다.

이 문제를 해결하는 한 가지 효과적인 방법은 더 나은 난수 생성기를 Supply에 제공하는 겁니다. 하지만 이 생각인 일단 제쳐두고, 더 범용적인 다른 대안을 생각해봅시다. 우리는 타입클래스를 사용해서 모나드로 할 수 있는 동작과 어떻게 동작하는지를 분리할 것입니다.

-- file: ch15/SupplyClass.hs
class (Monad m) => MonadSupply s m | m -> s where
    next :: m (Maybe s)

이 타입클래스는 모든 서플라이 모나드가 반드시 구현해야 하는 인터페이스를 정의하고 있습니다. 또한 몇가지 낯선 언어 확장을 쓰기 때문에 유심히 봐야 합니다. 각각의 확장은 이어지는 절에서 다룰 것입니다.

다중 인자 타입클래스

타입클래스 안에 있는 MonadSupply s m을 어떻게 읽어야 할까요? 괄호를 추가한다면 (MonadSupply s) m이 되고 다소 명확해집니다. 즉, Monad인 타입 변수 m에 한해서 , 이걸 타입클래스 MonadSupply s의 인스턴스로 만들 수 있습니다. 보통의 타입클래스와 다르게, 이건 인자를 가지고 있습니다.

이 언어 확장은 타입클래스가 인자를 2개 이상 가지도록 허용하기 때문에 MultiParamTypeClasses라는 이름이 붙었습니다. 인자 sSupply 타입의 타입 인자 s와 역할이 같습니다. snext 함수가 넘겨주는 값의 타입을 나타냅니다.

MonadSupply s의 정의에 (>>=)return을 넣을 필요가 없다는 걸 알아두세요. 타입 클래스의 문맥(슈퍼클래스)이 이미 MonadSupply sMonad인 것을 요구하기 때문입니다.

함수 종속

앞에서 무시한 조각을 다시 보면, | m -> s함수 종속functional dependency이고, 대개 fundep이라고 부릅니다. |를 “오른쪽을 만족하는”, 화살표 ->를 “고유하게 결정하는”이라고 읽을 수 있습니다. 함수 종속은 ms 사이의 관계를 구축합니다.

함수 종속의 허용 여부는 FunctionalDependencies 언어 프라그마컴파일러 지시자에 따라 결정됩니다.

관계를 선언하는 이면의 목적은 타입 검사기를 도와주는 것입니다. 하스켈 타입 검사기는 기본적으로 정리 증명기고, 그 동작 방식은 매우 보수적인 걸 상기하세요. 타입 검사기는 증명이 반드시 종료되는 걸 요구합니다. 끝나지 않는 증명은 컴파일러가 포기하거나 무한 루프에 빠지는 걸 초래합니다.

함수 종속으로, 타입 검사기가 MonadSupply s 문맥에서 사용한 모나드 m을 만날 때마다, s 타입만이 그것과 같이 사용할 수 있는 유일한 타입이라고 알려줍니다. 함수 종속을 생략한다면, 타입 검사기는 에러 메시지를 출력하고 포기할 겁니다.

ms 사이의 관계가 뭘 의미하는지 묘사하긴 어려우므로, 이 타입클래스의 인스턴스를 봅시다.

-- file: ch15/SupplyClass.hs
import qualified Supply as S

instance MonadSupply s (S.Supply s) where
    next = S.next

여기서 타입 S.Supply s로 타입 변수 m을 교체합니다. 함수 종속 덕분에 타입 검사기는 S.Supply s 타입을 발견하면 이 타입을 타입클래스 MonadSupply s의 인스턴스로 쓸 수 있다는 걸 알게 됩니다.

함수 종속이 없었다면 타입 검사기는 MonadSupply s의 타입 인자와 Supply s의 타입 인자 사이의 관계를 밝혀내지 못했을 테고, 에러를 내며 컴파일을 중지할 겁니다. 정의 그 자체는 컴파일 될 테지만, 우리가 처음 사용하는 시점에서 타입 에러가 발생할 겁니다.

S.Supply Int를 예를 들어 마지막 추상화 한 단계를 벗겨봅시다. 함수 종속이 없어도 이 타입을 MonadSupply s의 인스턴스로 선언할 수 있습니다. 하지만 이 인스턴스를 사용하는 코드를 짜면 컴파일러는 S.SupplyInt 인자와 타입클래스의 s 인자와 같아야 한다는 걸 모르고 에러를 출력할 겁니다.

함수 종속을 이해하는 건 어려울 수 있고, 단순한 사용을 넘어서면 대개 실제로 동작하게 만들기 어렵습니다. 다행히도 함수 종속의 주된 사용처는 이처럼 문제를 일으키키 힘들 단순한 상황입니다.

모듈 제작 마무리하기

SupplyClass.hs 파일에 우리가 만든 타입클래스와 인스턴스를 저장하고, 아래와 같은 모듈 헤더를 추가해야 합니다.

-- file: ch15/SupplyClass.hs
{-# LANGUAGE FlexibleInstances, FunctionalDependencies,
             MultiParamTypeClasses #-}

module SupplyClass
    (
      MonadSupply(..)
    , S.Supply
    , S.runSupply
    ) where

컴파일러가 우리 인스턴스 선언을 납득하기 위해선 FlexibleInstances 확장이 필요합니다. 이 확장은 컴파일러의 타입 검사기가 일부 상황에서 증명이 종료되는 걸 보장하게 만들어 인스턴스 작성 규칙을 느슨하게 합니다. 여기서 FlexibleInstances가 필요한 건 함수 종속 때문이지만, 자세한 이유는 안타깝게도 이 책의 범위를 벗어납니다.

언제 언어 확장이 필요한지 아는 법

GHC가 일부 코드를 어떤 언어 확장이 없어서 컴파일하지 못 하면, 무슨 언어 확장을 써야 하는지 알려줍니다. 예를 들어 GHC가 코드를 컴파일 하는 데 FlexibleInstances 지원이 필요하다고 판단하면, -XFlexibleInstances 옵션과 함께 컴파일해보라고 제안할 겁니다. -X 옵션은 LANGUAGE 지시자와 마찬가지로 특정 확장을 활성화하는 효과가 있습니다.

마지막으로, 이 모듈에서 runSupplySupply 명칭을 다시 내보내는 점을 주목하세요. 다른 모듈에서 그 명칭을 정의했더라도 그걸 내보내는 것 역시 적법합니다. 우리 경우엔, 이건 사용자 코드에서 Supply 모듈도 가져올 필요 없이 SupplyClass 모듈만 가져와도 되는 걸 의미합니다. 이걸로 우리 코드의 사용자는 염두에 둘 “움직이는 부분”의 개수를 줄일 수 있습니다.

모나드 인터페이스 프로그래밍

아래는 Supply 모나드에서 값 두 개를 가져와 문자열로 조립해 반환하는 간단한 함수입니다.

-- file: ch15/Supply.hs
showTwo :: (Show s) => Supply s String
showTwo = do
  a <- next
  b <- next
  return (show "a: " ++ show a ++ ", b: " ++ show b)

이 코드는 결과 타입 때문에 Supply 모나드에 묶여있습니다. 이 함수의 타입을 바꿔 MonadSupply 인터페이스를 구현한 임의의 모나드를 대상으로 일반화할 수 있습니다. 함수의 본체는 바뀌지 않았다는 걸 주목하세요.

-- file: ch15/SupplyClass.hs
showTwo_class :: (Show s, Monad m, MonadSupply s m) => m String
showTwo_class = do
  a <- next
  b <- next
  return (show "a: " ++ show a ++ ", b: " ++ show b)

Reader 모나드

State 모나드는 가변적인 상태를 코드 사이사이에서 전달하도록 도와줬습니다. 때때로 우린 프로그램 설정같은 어떤 불변 상태를 전달하고 싶을 때도 있습니다. State 모나드를 이 목적으로 사용할 순 있지만, 예기치 않게 바꾸지 말아야 할 상태를 바꾸는 사고가 생길 수 있습니다.

모나드는 잠시 잊어버리고 우리가 필요한 특성을 가진 함수가 뭘 해야 하는지 생각해봅시다. 이 함수는 넘겨준 데이터를 나타내는 (환경environment에서 따온) 타입 e 값을 받아 다른 타입 a를 결과로 반환합니다. 우리가 원하는 전체 타입은 e -> a가 됩니다.

이 타입을 편리한 Monad 인스턴스로 바꾸기 위해, newtype으로 감싸겠습니다.

-- file: ch15/SupplyInstance.hs
newtype Reader e a = R { runReader :: e -> a }

이걸 Monad 인스턴스로 만드는 건 큰일은 아닙니다.

-- file: ch15/SupplyInstance.hs
instance Monad (Reader e) where
    return a = R $ \_ -> a
    m >>= k = R $ \r -> runReader (k (runReader m r)) r

e 타입 값을 평가 중인 식의 환경이라고 생각할 수 있습니다. 환경이 어떻든 간에 return은 동일한 동작을 해야하기 때문에 우리가 만든 return은 환경을 무시합니다.

(>>=)의 정의는 약간 더 복잡하지만, 현재 계산과 연쇄할 계산에 환경—여기선 변수 r—을 제공하기만 하면 됩니다.

이 모나드 안에서 동작하는 코드는 환경을 어떻게 가져올까요? 간단히 ask를 호출하면 됩니다.

-- file: ch15/SupplyInstance.hs
ask :: Reader e e
ask = R id

아래 액션 연쇄에서 환경에 저장한 값은 변하지 않기 때문에, ask를 호출할 때마다 같은 값을 반환합니다. 우리 코드는 ghci에서 테스트하기 쉽습니다.

ghci> runReader (ask >>= \x -> return (x * 3)) 2
Loading package old-locale-1.0.0.0 ... linking ... done.
Loading package old-time-1.0.0.0 ... linking ... done.
Loading package random-1.0.0.0 ... linking ... done.
6

Reader 모나드는 대개 GHC에 딸려오는 표준 mtl에 포함돼 있고, Control.Monad.Reader 모듈에서 찾을 수 있습니다. 이 모나드는 대개 복잡한 코드에서 유용하기 때문에, 처음 이 모나드를 보면 좀 쓸모없어 보일 수 있습니다. 우린 자주 프로그램 깊숙한 곳에서 설정 정보의 한 조각을 접근해야 할 때가 있습니다. 그 정보를 일반 인자로 넘기려면 우리 코드를 힘들게 갈아 엎어야 할 것입니다. 이 정보를 모나드 배관에 숨겨서 중간에 낀 설정에 상관 없는 함수들은 그 인자들을 볼 필요가 없게 됩니다.

Reader 모나드를 사용하는 명확한 동기는 몇몇 모나드를 조합해 새 모나드를 만드는 주제를 다루는 18장. 모나드 변환기에서 볼 것입니다. 그 장에서 State 모나드로 일부 값을 변경하고, Reader 모나드로 나머지 값들은 불변으로 남기는 방법으로 상태에 대한 섬세한 조작을 하는 법을 볼 것입니다.

자동 타입클래스 선언으로 돌아가서

Reader 모나드도 알았으니 MonadSupply 타입클래스 인스턴스를 만드는 데 써먹어 봅시다. 예제를 간단히 하기 위해서, MonadSupply의 목적을 위반하겠습니다. next 액션은 매번 다른 값을 반환하는 게 아니라 같은 값을 반환할 겁니다.

Reader 타입을 곧바로 MonadSupply의 인스턴스로 만드는 건 안 좋은 생각입니다. 그러면 모든 ReaderMonadSupply로 동작할 수 있고, 보통 이건 말이 안 됩니다.

대신, Reader에 기반한 newtype을 만들 겁니다. 이 newtype은 우리가 내부적으로 Reader를 쓴다는 사실을 숨깁니다. 이 타입은 반드시 우리가 신경쓰는 두 타입클래스의 인스턴스로 만들어야 합니다. GeneralizedNewtypeDeriving를 활성화하면 GHC가 힘든 작업을 대신 해 줄 겁니다.

-- file: ch15/SupplyInstance.hs
newtype MySupply e a = MySupply { runMySupply :: Reader e a }
    deriving (Monad)

instance MonadSupply e (MySupply e) where
    next = MySupply $ do
             v <- ask
             return (Just v)

    -- more concise:
    -- next = MySupply (Just `liftM` ask)

새 타입을 MonadSupply가 아니라 MonadSupply e의 인스턴스로 만들어야 한다는 사실에 주목하세요. 타입 인자를 빠뜨리면 컴파일러는 불만을 터뜨릴 겁니다.

MySupply 타입을 시험해보기 위해 먼저 아무 MonadSupply 인스턴스와 동작하는 간단한 함수를 짜보겠습니다.

-- file: ch15/SupplyInstance.hs
xy :: (Num s, MonadSupply s m) => m s
xy = do
  Just x <- next
  Just y <- next
  return (x * y)

이 함수를 Supply 모나드와 randomsIO 함수와 같이 사용하면 기대한 대로 매번 다른 값을 얻을 것입니다.

ghci> (fst . runSupply xy) `fmap` randomsIO
-15697064270863081825448476392841917578
ghci> (fst . runSupply xy) `fmap` randomsIO
17182983444616834494257398042360119726

MySupply 모나드는 newtype으로 두 번 감쌌기 때문에, 따로 실행 함수를 만들면 더 쉽게 사용할 수 있습니다.

-- file: ch15/SupplyInstance.hs
runMS :: MySupply i a -> i -> a
runMS = runReader . runMySupply

이 실행함수로 xy 액션을 적용하면 매번 같은 값을 얻게 됩니다. 우리 코드는 그대로지만, 다른 MonadSupply 구현 안에서 실행시켰기 때문에 동작이 변한 것입니다.

ghci> runMS xy 2
4
ghci> runMS xy 2
4

MonadSupply 타입클래스와 Supply 모나드처럼 거의 모든 하스켈 모나드는 인터페이스와 구현을 분리해 놨습니다. 예를 들어 State 모나드에 “속한” 것처럼 소개한 getput은 사실 MonadState 타입클래스의 메서드고, State 타입은 이 타입클래스의 인스턴스입니다.

마찬가지로 표준 Reader 모나드는 ask 메서드를 가진 MonadReader의 인스턴스입니다.

위에서 말한 인터페이스와 구현 분리가 설계적 깔끔함으로 가지는 매력 외에도, 나중에 알게 될 실용적인 활용처도 있습니다. 18장. 모나드 변환기에서 모나드를 조합할 때, GeneralizedNewtypeDeriving과 타입클래스를 사용해 많은 수고를 줄일 것입니다.

IO 모나드 숨기기

IO 모나드가 양날의 칼인 이유는 너무 강력하기 때문입니다. 주의해서 타입을 사용하는 게 프로그래밍 실수를 피하는 걸 도와준다고 하면, IO 모나드는 거기서 눈엣가시가 됩니다. IO 모나드는 우리가 할 수 있는 것을 제한하지 않기 때문에 모든 종류의 사고에 우리를 취약하게 합니다.

어떻게 이 힘을 제어할 수 있을까요? 우리가 어떤 코드 조각이 로컬 파일시스템은 읽고 쓸 수 있지만 네트워크는 접근할 수 없도록 보장하고 싶다고 해 봅시다. 일반적인 IO 모나드는 그런 식으로 제한하지 않기 때문에 사용할 수 없습니다.

newtype 사용하기

파일을 읽고 쓰는 작은 기능 집합을 제공하는 모듈을 만들어봅시다.

-- file: ch15/HandleIO.hs
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module HandleIO
    (
      HandleIO
    , Handle
    , IOMode(..)
    , runHandleIO
    , openFile
    , hClose
    , hPutStrLn
    ) where
    
import System.IO (Handle, IOMode(..))
import qualified System.IO

IOnewtype으로 감싸 제한된 IO를 만드는 첫번째 걸음을 딛겠습니다.

-- file: ch15/HandleIO.hs
newtype HandleIO a = HandleIO { runHandleIO :: IO a }
    deriving (Monad)

이젠 익숙할 데이터 생성자 말고 타입 생성자와 runHandleIO 실행 함수만 내보내는 방법을 썼습니다. 이게 HandleIO 안에서 HandleIO가 감싸고 있는 IO 모나드를 얻는 걸 막아줄 겁니다.

우리에게 남은 건 우리 모나드가 허용할 동작 각각을 감싸는 겁니다. 이건 IO 각각을 HandleIO 데이터 생성자로 감싸면 됩니다.

-- file: ch15/HandleIO.hs
openFile :: FilePath -> IOMode -> HandleIO Handle
openFile path mode = HandleIO (System.IO.openFile path mode)

hClose :: Handle -> HandleIO ()
hClose = HandleIO . System.IO.hClose

hPutStrLn :: Handle -> String -> HandleIO ()
hPutStrLn h s = HandleIO (System.IO.hPutStrLn h s)

이제 제한된 HandleIO 모나드를 입출력에 사용할 수 있습니다.

-- file: ch15/HandleIO.hs
safeHello :: FilePath -> HandleIO ()
safeHello path = do
  h <- openFile path WriteMode
  hPutStrLn h "hello world"
  hClose h

runHandleIO로 이 액션을 실행합니다.

ghci> :load HandleIO
[1 of 1] Compiling HandleIO         ( HandleIO.hs, interpreted )
Ok, modules loaded: HandleIO.
ghci> runHandleIO (safeHello "hello_world_101.txt")
Loading package old-locale-1.0.0.0 ... linking ... done.
Loading package old-time-1.0.0.0 ... linking ... done.
Loading package filepath-1.1.0.0 ... linking ... done.
Loading package directory-1.0.0.0 ... linking ... done.
Loading package mtl-1.1.0.0 ... linking ... done.
ghci> :m +System.Directory
ghci> removeFile "hello_world_101.txt"

만약 허용하지 않은 액션을 HandleIO 모나드 안에서 연속sequence하려고 하면, 타입 시스템에서 막을 겁니다.

ghci> runHandleIO (safeHello "goodbye" >> removeFile "goodbye")

<interactive>:1:36:
    Couldn't match expected type `HandleIO a'
           against inferred type `IO ()'
    In the second argument of `(>>)', namely `removeFile "goodbye"'
    In the first argument of `runHandleIO', namely
        `(safeHello "goodbye" >> removeFile "goodbye")'
    In the expression:
        runHandleIO (safeHello "goodbye" >> removeFile "goodbye")

예상치 못한 경우를 대비한 설계

HandleIO 모나드엔 작지만 중요한 문제가 있습니다. 때때로 탈출구가 필요할 가능성을 고려하지 않았단 점입니다. 우리가 이런 모나드를 정의한다면, 부득이하게 우리 모나드가 허용하지 않은 입출력 액션을 수행해야 할 때도 생길 겁니다.

일반적인 상황에서 견고한 코드를 짜기 쉬우라고 이런 모나드를 정의한 것이지, 예기치 못한 상황이 없으라고 한 게 아닙니다. 그러니 우리 스스로 쓸 탈출구를 만들어 봅시다.

Control.Monad.Trans 모듈은 “표준 탈출구”를 MonadIO 타입클래스에 정의했습니다. IO 액션을 다른 모나드에 심을 수 있는 liftIO 함수가 그것입니다.

ghci> :m +Control.Monad.Trans
ghci> :info MonadIO
class (Monad m) => MonadIO m where liftIO :: IO a -> m a
    -- Defined in Control.Monad.Trans
instance MonadIO IO -- Defined in Control.Monad.Trans

이 타입클래스를 위한 구현은 간단합니다. 그냥 IO를 우리 데이터 생성자로 감쌀 겁니다.

-- file: ch15/HandleIO.hs
import Control.Monad.Trans (MonadIO(..))

instance MonadIO HandleIO where
    liftIO = HandleIO

liftIO를 현명하게 사용함으로써, 우린 필요한 곳에서 족쇄를 풀고 IO 액션을 호출할 수 있습니다.

-- file: ch15/HandleIO.hs
tidyHello :: FilePath -> HandleIO ()
tidyHello path = do
  safeHello path
  liftIO (removeFile path)

MonadIO와 자동 유도deriving

HandleIOderiving 구문에 타입클래스를 추가해서 컴파일러가 자동으로 MonadIO 인스턴스를 유도하게 할 수도 있었을 겁니다. 실제로도 이건 일반적인 전략입니다. 단지 이전 MonadIO 코드와 분리해서 보여주기 위해 그러지 않았습니다.

타입 클래스 사용하기

실제 구현에 얽매였다는 점이 다른 모나드에서 IO를 숨기는 것의 단점입니다. 만약 HandleIO를 다른 모나드와 바꾸려면, 우린 HandleIO를 쓰는 모든 액션의 타입을 바꿔야 합니다.

대안으로 파일을 다루는 모나드에서 우리가 원하는 인터페이스를 노출하는 타입클래스를 만드는 방법이 있습니다.

-- file: ch15/MonadHandle.hs
{-# LANGUAGE FunctionalDependencies, MultiParamTypeClasses #-}

module MonadHandle (MonadHandle(..)) where

import System.IO (IOMode(..))

class Monad m => MonadHandle h m | m -> h where
    openFile :: FilePath -> IOMode -> m h
    hPutStr :: h -> String -> m ()
    hClose :: h -> m ()
    hGetContents :: h -> m String

    hPutStrLn :: h -> String -> m ()
    hPutStrLn h s = hPutStr h s >> hPutStr h "\n"

여기선 모나드 타입과 파일 핸들 타입 둘 다 추상화하는 걸 택했습니다. 타입 검사기를 위해 함수 종속을 사용했습니다. 모든 MonadHandle 인스턴스는 쓸 수 있는 핸들 타입이 제각기 하나만 있을 겁니다. IO 모나드를 이 타입클래스의 인스턴스로 만들면, 일반 Handle을 사용하게 될 겁니다.

-- file: ch15/MonadHandleIO.hs
{-# LANGUAGE FunctionalDependencies, MultiParamTypeClasses #-}

import MonadHandle
import qualified System.IO

import System.IO (IOMode(..))
import Control.Monad.Trans (MonadIO(..), MonadTrans(..))
import System.Directory (removeFile)

import SafeHello

instance MonadHandle System.IO.Handle IO where
    openFile = System.IO.openFile
    hPutStr = System.IO.hPutStr
    hClose = System.IO.hClose
    hGetContents = System.IO.hGetContents
    hPutStrLn = System.IO.hPutStrLn

MonadHandle 또한 Monad여야 하기 때문에, 파일을 다루는 코드를 어떤 모나드에서 실행하는지 신경쓸 일 없이 do 표기법으로 짤 수 있습니다.

-- file: ch15/SafeHello.hs
safeHello :: MonadHandle h m => FilePath -> m ()
safeHello path = do
  h <- openFile path WriteMode
  hPutStrLn h "hello world"
  hClose h

IO를 이 타입클래스의 인스턴스로 만들었기에 이 액션을ghci에서 실행할 수 있습니다.

ghci> safeHello "hello to my fans in domestic surveillance"
Loading package old-locale-1.0.0.0 ... linking ... done.
Loading package old-time-1.0.0.0 ... linking ... done.
Loading package filepath-1.1.0.0 ... linking ... done.
Loading package directory-1.0.0.0 ... linking ... done.
Loading package mtl-1.1.0.0 ... linking ... done.
ghci> removeFile "hello to my fans in domestic surveillance"

타입클래스를 쓰는 방법의 좋은 점은, 우리 코드가 쓰지 않거나 구현에 신경쓰지 않는, 바탕으로 쓰는 모나드를 코드를 많이 건드리지 않고도 다른 모나드로 바꿀 수 있다는 점입니다. 예를 들어, IO를 출력하는 즉시 압축해 파일에 기록하는 모나드로도 바꿀 수 있습니다.

모나드의 인터페이스를 타입클래스로 정의하는 덴 다른 장점도 있습니다. 이건 다른 사람이 우리 구현을 newtype 래퍼 안에 숨기게 하고, 노출하고 싶은 타입클래스만 인스턴스로 자동 선언하게 만듭니다.

격리와 테스트

safeHello 함수가 실제로 IO 타입을 안 쓰기 때문에, 입출력을 못 하는 모나드도 쓸 수 있습니다. 이로인해 일반적으로 부수 효과를 가지는 코드를 완전히 순수한, 통제되는 환경에서 테스트할 수 있게 됩니다.

이걸 해보기 위해, 입출력을 수행하진 않지만 나중에 쓸 파일에 관련한 이벤트를 기록하는 모나드를 만들겠습니다.

-- file: ch15/WriterIO.hs
data Event = Open FilePath IOMode
           | Put String String
           | Close String
           | GetContents String
             deriving (Show)

“새 모나드 사용하기: 직접 만들어 봅시다!” 절에서 Logger 타입을 고안하긴 했지만, 여기선 표준이고 더 일반적인 Writer 모나드를 쓰겠습니다. 다른 mtl 모나드처럼 Writer 모나드의 API도 타입클래스로 제공하고, 그 타입클래스 이름은 MonadWriter입니다. 가장 유용한 메서드는 값을 기록하는 tell입니다.

ghci> :m +Control.Monad.Writer
ghci> :type tell
tell :: (MonadWriter w m) => w -> m ()

아무 Monoid 타입이나 기록할 수 있습니다. 리스트 타입도 Monoid기에 Event 리스트에 기록할 겁니다.

Writer [Event]MonadHandle의 인스턴스로 만들 수도 있지만, 이게 더 특수 목적 모나드를 만들기 저렴하고, 쉽고, 안전합니다.

-- file: ch15/WriterIO.hs
newtype WriterIO a = W { runW :: Writer [Event] a }
    deriving (Monad, MonadWriter [Event])

실행 함수는 단순히 우리가 추가한 newtype 래퍼를 제거하고, 일반 Writer 실행 함수를 호출합니다.

-- file: ch15/WriterIO.hs
runWriterIO :: WriterIO a -> (a, [Event])
runWriterIO = runWriter . runW

이 코드를 ghci에서 실행하면, 함수의 파일 액세스 기록을 줄 것입니다.

ghci> :load WriterIO
[1 of 3] Compiling MonadHandle      ( MonadHandle.hs, interpreted )
[2 of 3] Compiling SafeHello        ( SafeHello.hs, interpreted )
[3 of 3] Compiling WriterIO         ( WriterIO.hs, interpreted )
Ok, modules loaded: SafeHello, MonadHandle, WriterIO.
ghci> runWriterIO (safeHello "foo")
((),[Open "foo" WriteMode,Put "foo" "hello world",Put "foo" "\n",Close "foo"])

Writer 모나드와 리스트

우리가 tell을 호출할 때마다 Writer 모나드는 mappend를 호출합니다. 리스트의 mappend(++)이고, 이런 반복적인 추가는 비싸기 때문에, Writer에 쓰기엔 실용적이지 않습니다. 위에선 단지 단순함을 위해 리스트를 사용했습니다.

실사용 코드에서 리스트같은 동작을 하는 Writer 모나드가 필요하다면, 추가하는데 더 나은 특성을 가진 타입을 쓰세요. 그런 타입 중 하나로 “데이터로서의 함수 활용하기” 절에서 소개한 차이 리스트difference list가 있습니다. 자신만의 차이 리스트 구현을 고민할 필요도 없는 게, 잘 짠 라이브러리를 Hackage, 하스켈 패키지 데이터베이스에서 다운받을 수 있습니다. 아니면 “일반 목적 시퀀스” 절에서 소개한 Data.Sequence모듈의 Seq 타입을 쓸 수도 있습니다.

다시 보는 임의 입출력

IO를 제한하는데 타입클래스를 활용하면 기존의 입출력 액션을 보존할 수 있습니다. 그러기 위해 MonadIO를 타입클래스에 제약 조건으로 넣을 수 있습니다.

-- file: ch15/MonadHandleIO.hs
class (MonadHandle h m, MonadIO m) => MonadHandleIO h m | m -> h

instance MonadHandleIO System.IO.Handle IO

tidierHello :: (MonadHandleIO h m) => FilePath -> m ()
tidierHello path = do
  safeHello path
  liftIO (removeFile path)

하지만 이 방법엔 문제가 하나 있습니다. 추가한 MonadIO 제약 조건이 우리 코드를 순수한 환경에서 테스트할 수 없게 만듭니다. 어떤 테스트가 부수 효과를 일으킬지 더 이상 구분할 수 없게 되기 때문입니다. 대안으로 이 타입 제약을 모든 함수를 “감염시키는” 타입클래스에서 실제 입출력이 필요한 함수쪽으로만 옮기는 것이 있습니다.

-- file: ch15/MonadHandleIO.hs
tidyHello :: (MonadIO m, MonadHandle h m) => FilePath -> m ()
tidyHello path = do
  safeHello path
  liftIO (removeFile path)

MonadIO가 없는 함수에는 순수한 프로퍼티 테스트를 사용할 수 있고, 나머지에는 전통적인 유닛 테스트를 쓸 수 있습니다.

불행히도, 우린 문제 하나를 다른 문제로 바꾼 것에 불과합니다. MonadIOMonadHandle 제약 조건을 둘 다 가진 코드를 MonadHandle만 제약 조건으로 가진 코드에서 사용할 수 없습니다. 만약 우리가 이 사실을 MonadHandle만 사용한 코드 깊숙한 곳에서 발견한다면, MonadIO 제약 조건도 필요하게 되고, 그 곳에 이르는 모든 경로에 모두 제약 조건을 추가해야 할 것입니다.

임의 입출력 작업을 허용하는 건 위험하고, 우리가 코드를 개발하고 테스트하는데 상당한 영향을 끼칩니다. 자유도를 늘리는 것과, 쉬운 추론과 테스트 중 하나를 택해야만 한다면 보통 후자를 선호할 겁니다.

연습문제

  1. QuickCheck로 열리지 않은 파일 핸들에 쓰기를 시도하는지 MonadHandle 모나드 안에서 액션을 테스트하세요. safeHello에 시도해보세요.
  2. 닫힌 핸들에 쓰기를 시도하는 액션을 작성해보세요. 독자의 테스트가 이 버그를 잡아내나요?
  3. URL 인코딩 된 문자열에선 key&key=1&key=2 같이 같은 키가 여러 번 나오거나, 값이 있거나 없을 수 있습니다. 이런 문자열을 키값으로 나타내는 데 어떤 타입을 사용하겠습니까? 모든 정보를 정확하게 읽어내는 파서를 작성해보세요.
저작자 표시 비영리 동일 조건 변경 허락
신고

Real World Haskell 14장 번역: 모나드Real World Haskell 14장 번역: 모나드

Posted at 2015.01.25 02:31 | Posted in 지식저장소/읽은 책 요약
14장. 모나드

14장. 모나드

도입부

7장 입출력에서, 우린 IO 모나드에 대해 얘기는 했지만 의도적으로 바깥 세계와 소통하는 것에만 초점을 맞춰 논의했습니다. 우린 모나드가 무엇인지 말하진 않았습니다.

우린 이미 7장 입출력에서 IO 모나드로 쉽게 작업할 수 있는 것을 보았습니다. 표기법의 차이는 제쳐두고, IO 모나드로 코드를 짜면 다른 절차 지향 언어와도 많이 차이가 나지 않았습니다.

이전 장들에서 우리가 실용적인 문제를 다룰 때 도입한 구조도, 이제 곧 보겠지만 사실 모나드입니다. 우리는 모나드가 문제를 해결하는 데 명백유용한 도구라는 걸 보여주려고 합니다. 모나드 사용이 얼마나 쉬운지 보여주기 위해 이 장에서 모나드를 몇가지 정의할 것입니다.

이전 코드 예제 되새기기

Maybe 연쇄

10장 코드 예제 분석: 이진 자료 파싱에서 짰던 parseP5 함수를 다른 측면에서 살펴봅시다.

-- file: ch10/PNM.hs
matchHeader :: L.ByteString -> L.ByteString -> Maybe L.ByteString

-- "nat" here is short for "natural number"
getNat :: L.ByteString -> Maybe (Int, L.ByteString)

getBytes :: Int -> L.ByteString
         -> Maybe (L.ByteString, L.ByteString)

parseP5 s =
  case matchHeader (L8.pack "P5") s of
    Nothing -> Nothing
    Just s1 ->
      case getNat s1 of
        Nothing -> Nothing
        Just (width, s2) ->
          case getNat (L8.dropWhile isSpace s2) of
            Nothing -> Nothing
            Just (height, s3) ->
              case getNat (L8.dropWhile isSpace s3) of
                Nothing -> Nothing
                Just (maxGrey, s4)
                  | maxGrey > 255 -> Nothing
                  | otherwise ->
                      case getBytes 1 s4 of
                        Nothing -> Nothing
                        Just (_, s5) ->
                          case getBytes (width * height) s5 of
                            Nothing -> Nothing
                            Just (bitmap, s6) ->
                              Just (Greymap width height maxGrey bitmap, s6)

이 함수를 소개할 땐, 함수가 복잡해질수록 페이지의 오른쪽으로 진행해서 곤란했습니다. 우린 이 난간 계단같은 코드를 (>>?) 함수로 제어할 수 있었습니다.

-- file: ch10/PNM.hs
(>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>? _ = Nothing
Just v  >>? f = f v

우린 Maybe 값을 반환하는 함수를 연쇄할 수 있도록 주의깊게 (>>?)의 타입을 골랐습니다. 그 결과 한 함수의 결과 타입이 다음 함수의 인자 타입과 일치하는 한, Maybe로 감싸서 반환하는 함수들을 무한히 연쇄할 수 있었습니다. (>>?)의 본체는 우리가 짠 함수 연쇄chain, 이하 체인에서 Nothing이나 완전히 평가한 값을 반환하는 것으로 내부적으로 단축 평가short-circuit하는 것을 숨기고 있습니다.

암시적 상태

(>>?)parseP5를 가지런히 하는데 유용했던 것과 동시에, 우리는 파싱하면서 문자열 조각을 조금씩 읽어야 했습니다. 이 때문에 현재 문자열 값을 터플로 감싸 Maybe체인 아래로 넘겨야 했습니다. 체인 안의 각각의 함수는 파싱한 결과와 아직 파싱하지 않은 나머지 문자열을 각각 터플의 원소로 넣었습니다.

-- file: ch10/PNM.hs
parseP5_take2 :: L.ByteString -> Maybe (Greymap, L.ByteString)
parseP5_take2 s =
    matchHeader (L8.pack "P5") s      >>?
    \s -> skipSpace ((), s)           >>?
    (getNat . snd)                    >>?
    skipSpace                         >>?
    \(width, s) ->   getNat s         >>?
    skipSpace                         >>?
    \(height, s) ->  getNat s         >>?
    \(maxGrey, s) -> getBytes 1 s     >>?
    (getBytes (width * height) . snd) >>?
    \(bitmap, s) -> Just (Greymap width height maxGrey bitmap, s)

skipSpace :: (a, L.ByteString) -> Maybe (a, L.ByteString)
skipSpace (a, s) = Just (a, L8.dropWhile isSpace s)

또 다시, 반복적인 작업 패턴을 맞닥뜨립니다. 문자열을 읽고, 결과를 반환하고, 나머지 문자열을 다음 파싱 함수에 넘겨줍니다. 하지만, 이 패턴은 더 까다롭습니다. 만약 우리가 또 다른 정보를 체인의 아래로 건네고 싶다면, 각각의 2터플을 3터플로 바꿔야 하므로 체인의 거의 모든 원소를 수정해야만 하게 됩니다.

우리는 이 문제를 현재 문자열을 다루는 책임을 체인 안의 각각의 함수가 아니라 체인을 엮는 함수가 지게 해 해결했습니다.

-- file: ch10/Parse.hs
(==>) :: Parse a -> (a -> Parse b) -> Parse b

firstParser ==> secondParser = Parse chainedParser
  where chainedParser initState =
          case runParse firstParser initState of
            Left errMessage ->
                Left errMessage
            Right (firstResult, newState) ->
                runParse (secondParser firstResult) newState

뿐만 아니라 자세한 파싱 상태를 ParseState 안에 숨겼습니다. getStateputState 함수조차 파싱 상태를 조사하진 않아, ParseState를 아무리 바꿔도 이미 작성한 코드에 아무런 영향이 없게 되었습니다.

공유하는 패턴 찾기

위 예제들을 자세히 봐도 공통점이 많아 보이진 않습니다. 일단, 둘 다 함수 연쇄에 관련이 있고, 세부사항을 숨겨 더 간결한 코드를 짜도록 도와줍니다. 하지만, 한 걸음 물러나 넓게 봅시다.

먼저, 타입 정의를 살펴 봅시다.

-- file: ch14/Maybe.hs
data Maybe a = Nothing
             | Just a
-- file: ch10/Parse.hs
newtype Parse a = Parse {
      runParse :: ParseState -> Either String (a, ParseState)
    }

두 타입의 공통점은 오른쪽 어딘가에 나타나는 타입 인자 하나가 정의 왼쪽에 있다는 것입니다. 그러므로 두 타입은 어떤 타입을 담을지 모르는 일반적generic 타입입니다.

다음으로, 두 타입을 위해 우리가 작성한 체인 함수를 살펴보겠습니다.

ghci> :type (>>?)
(>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b
ghci> :type (==>)
(==>) :: Parse a -> (a -> Parse b) -> Parse b

이 함수들은 감쪽같이 비슷한 타입을 가지고 있습니다. 우리가 이 타입 생성자를 타입 변수로 바꾼다면, 좀 더 추상화된 한 타입을 얻게 됩니다.

-- file: ch14/Maybe.hs
chain :: m a -> (a -> m b) -> m b

마지막으로, 둘 다 각각 “평범한” 값을 받아 대상 타입에 “주입”하는 함수를 가지고 있습니다. Maybe는 단순히 Just 타입 생성자지만, Parse의 주입자injector는 더 복잡합니다.

-- file: ch10/Parse.hs
identity :: a -> Parse a
identity a = Parse (\s -> Right (a, s))

다시, 세부 사항이나 복잡도를 보자는 것이 아닙니다. 우리가 보려는 것은 각각의 타입이 다음과 같은 “주입자” 함수를 가지고 있다는 사실입니다.

-- file: ch14/Maybe.hs
inject :: a -> m a

이 세 가지 속성과, 이것들을 어떻게 같이 사용할 지에 관한 규칙이, 하스켈에서의 모나드를 정의합니다. 위 목록을 압축한 형태로 상기해봅시다.

  • 타입 생성자 m.

  • 한 함수의 출력을 다른 함수의 인자로 연쇄할 m a -> (a -> m b) -> m b 타입 함수

  • 평범한 값을 체인 안으로 주입할 a -> m a 타입 함수. 즉, 타입 a를 타입 생성자 m으로 감싸는 함수.

Maybe 타입을 모나드로 만드는 세 가지 속성은 그 타입 생성자 Maybe a, 우리의 연쇄 함수 (>>?), 주입자 함수 Just입니다.

Parse의 경우, 대응하는 각각의 속성은 타입 생성자 Parse a, 연쇄 함수 (==>), 주입자 함수 identity입니다.

연쇄 함수와 주입자가 어떻게 동작해야 암시적 상태별로 중요하지 않기 때문에, 일부러 언급하지 않았습니다. 사실, 모나드는 매우 간단하기 때문에 하스켈 코드 곳곳에서 쓰고 있습니다. 수많은 일반적인 프로그래밍 패턴이 모나드 구조를 가지고 있는데, 암시적 데이터 전달이나, 첫번째가 실패했을 때 두번째를 보지 않고 선택하는 체인의 단축 평가의 예가 있습니다.

모나드 타입클래스

연쇄와 주입의 개념과 모나드에 넣고 싶은 타입을 하스켈 타입클래스에서 확인할 수 있습니다. 표준 프렐류드Prelude는 이미 Monad라는 이름을 가진 그러한 타입클래스를 정의했습니다.

-- file: ch14/Maybe.hs
class Monad m where
    -- chain
    (>>=)  :: m a -> (a -> m b) -> m b
    -- inject
    return :: a -> m a

여기서, (>>=)는 체인 함수입니다. 우린 이걸 이미 “시퀀싱”장에서 봤습니다. 이 함수는 왼쪽의 계산 결과를 오른쪽의 인자로 묶기 때문에 보통 “바인드bind”라고 부릅니다.

주입자 함수는 return입니다. “리턴의 속성”에서 봤듯이, return을 이름으로 고른 것은 좀 안타깝습니다. 이 이름은 이미 절차 지향 언어에서 쉽게 이해할 수 있는 뜻을 가지고 널리 쓰고 있기 때문입니다. 하스켈에선, 이 함수는 동작에 훨씬 제약을 덜 받습니다. 심지어, return을 함수의 중간에서 호출해도 체인을 일찍 종료하지도 않습니다. 이 함수의 이름에서 동작을 연상하는 한 가지 유용한 방법은 이 함수가 (a 타입의) 순수한 값을 (m a 타입의) 모나드 값으로 되돌려준다고 이해하는 것입니다.

(>>=)returnMonad 타입클래스의 핵심 함수지만, 모나드 타입클래스는 다른 두 함수를 추가로 정의합니다. 첫째는 (>>)then입니다. (>>=)와 마찬가지로 연쇄를 하지만, 왼쪽의 결과 값을 무시합니다.

-- file: ch14/Maybe.hs
    (>>) :: m a -> m b -> m b
    a >> f = a >>= \_ -> f

우리는 액션을 특정 순서로 실행시키고 싶지만 그 결과는 신경쓰지 않을 때 이 함수를 씁니다. 이건 좀 의미없어 보일 수 있습니다. 왜 우리가 함수의 리턴 값에 신경을 안 쓸가요? 하지만, 우리가 딱 이것을 나타내는 (==>&) 컴비네이터를 이미 정의했었단 걸 떠올려보세요. 아니면, print같은 조사할 필요가 없는 빈 자리를 채우기만 하는 값을 반환하는 함수를 생각하셔도 됩니다.

ghci> :type print "foo"
print "foo" :: IO ()

만약 (>>=)를 쓴다면, 우변 함수로 반드시 인자를 무시하는 함수를 제공해야 합니다.

ghci> print "foo" >>= \_ -> print "bar"
"foo"
"bar"

하지만 (>>)을 쓴다면, 우리는 쓸모없는 함수를 생략할 수 있습니다.

ghci> print "baz" >> print "quux"
"baz"
"quux"

위에서 봤듯이, (>>)의 기본 구현은 (>>=)를 사용해서 정의합니다.

둘째 곁다리 Monad 함수는 에러메시지를 받고 함수 체인을 실패시키는 fail입니다.

-- file: ch14/Maybe.hs
    fail :: String -> m a
    fail = error

fail을 조심하세요

상당한 Monad 인스턴스가 지금 본 fail의 기본 구현을 재정의하지 않았고, 그런 모나드는 failerror를 사용합니다. error를 호출하면 호출자가 붙잡지 못 하거나 예상하지 못한 예외를 던지기 때문에 보통 매우 안 좋습니다.

비록 독자가 당장 fail이 잘 구현된 모나드 안에 있다는 걸 알더라도, 여전히 쓰지 않는 걸 추천합니다. 나중에 코드를 리팩토링하다가 이전에 안전했던 fail이 새 문맥에서 위험해질 수 있다는 걸 잊어버리고 스스로 문제를 일으키기 매우 쉽기 때문입니다.

이건 10장. 코드 예제 분석: 이진 데이터 파싱에서 개발했던 파서를 떠올려보기 위한, 그 파서의 Monad 인스턴스입니다.

-- file: ch10/Parse.hs
instance Monad Parse where
    return = identity
    (>>=) = (==>)
    fail = bail

잠깐의 전문 용어 시간

아마도 독자가 낯설어 할 용어가 여럿 있습니다. 정식 용어는 아니지만, 일반적으로 쓰이므로 알아두면 좋습니다.

  • 모나딕”은 단순히 “모나드와 관계된”이란 의미입니다. 모나딕 타입Monad 타입클래스의 인스턴스고, 모나딕 은 모나딕 타입을 가지고 있습니다.

  • 우리가 어떤 타입이“모나드다”라고 말할 땐, 실제론 이 타입이 Monad 타입클래스의 인스턴스라고 말하는 것을 줄인 것입니다. Monad의 인스턴스가 되는 건 우리에게 타입 생성자, 주입자 함수, 체인 함수 모나딕 3박자를 제공합니다.

  • 마찬가지로, “Foo 모나드”라는 말은 Foo라는 타입과, 그 타입의 Monad 인스턴스를 말하는 것입니다.

  • 액션”은 모나딕 값의 다른 이름입니다. 이 단어는 아마도 print "foo"같은 모나딕 값이 관측할 수 있는 부수 효과를 가질 수 있는 I/O 모나드의 도입에서 유래한 것일 겁니다. 조금 드물지만 모나딕 값을 반환하는 함수도 액션이라고 부를 수도 있습니다.

새 모나드 사용하기: 직접 만들어 봅시다!

도입부에서, 이전에 작성한 일부 코드가 이미 모나딕 형태인 것을 확인했습니다. 모나드가 무엇인지 알아가기 시작했고, Monad 타입클래스도 봤으니, 우리가 모나드로 무엇을 할지 예상하며 만들어봅시다. 첫 시작으로 모나드 인터페이스를 정의하고, 그걸 사용할 것입니다. 한번 이 작업을 끝마치면, 마지막으로 그걸 만들 것입니다.

순수한 코드는 작성하기 놀라울 정도로 깔끔하지만, 물론 입출력을 수행할 수 없습니다. 때때로, 우린 파일에 로그 정보를 저장하지 않고 우리가 내린 판단의 기록을 가지고 싶을 수 있습니다. 이 작업을 도와줄 작은 라이브러리 하나를 개발해봅시다.

“glob 패턴을 정규 표현식으로 변환하기”장에서 만든 globToRegex 함수를 떠올려봅시다. 우린 그 함수가 변환한 특별한 패턴 시퀀스들의 기록을 유지하도록 수정할 것입니다. 익숙한 코드를 다시 다루는 이유는 같은 코드의 모나딕이 아닌 버전과 모나딕 버전을 비교하기 위해섭니다.

시작으로, 우리는 결과 타입을 Logger 타입 생성자로 감쌀 것입니다.

-- file: ch14/Logger.hs
globToRegex :: String -> Logger String

정보 은폐

우린 Logger 모듈 내부를 일부러 추상적으로 유지할 겁니다.

-- file: ch14/Logger.hs
module Logger
    (
      Logger
    , Log
    , runLogger
    , record
    ) where

이렇게 세부 사항을 감추는 덴 두 가지 장점이 있습니다. 우리가 모나드를 구현하는 방법에 상당한 유연성을 허용하고, 사용자에겐 단순한 인터페이스를 제공합니다.

Logger 타입은 단지 타입 생성자입니다. 우린 사용자가 이 타입의 값을 만들 필요가 없도록 생성자를 드러내지 않을 겁니다. 사용자가 쓸 수 있는 건 타입 시그니처를 작성할 때 필요한 Logger 뿐입니다.

Log 타입은 시그니처를 더 읽기 쉽게 하기 위해 만든, 그냥 문자열 리스트의 동의어입니다. 구현을 단순하게 유지하기 위해 문자열 리스트를 사용할 것입니다.

-- file: ch14/Logger.hs
type Log = [String]

라이브러리 사용자에게 값 생성자를 주는 것 대신, runLogger라는 기록을 첨부한 액션을 평가하는 함수를 제공할 겁니다. 이 함수는 액션의 결과와 결과가 계산되는 동안 기록한 것들을 반환합니다.

-- file: ch14/Logger.hs
runLogger :: Logger a -> (a, Log)

제어 가능한 탈출

Monad 타입클래스는 값을 모나드 족쇄에서 빼낼 수 있는 어떤 수단도 제공하지 않습니다. 우리는 단지 return으로 모나드에 갑을 주입할 수 있습니다. (>>=)로 모나드에서 값을 빼낼 수 있지만, 이 빼낸 값을 사용하는 오른쪽 함수 또한 자신의 결과를 모나드로 감싸야 합니다.

대부분의 모나드는 runLogger같은 함수를 가지고 있습니다. 두드러진 예외는 프로그램을 종료하는 것으로만 탈출할 수 있는 IO 모나드입니다.

모나드 실행 함수는 코드를 모나드 안에서 실행하고 그 결과를 꺼냅니다. 제공하는 방법으로는 대개 이런 함수들로만 값에서 모나드 래퍼를 벗겨낼 수 있습니다. 그러므로 모나드 제작자는 모나드 안에 있는 것을 꺼내는 데 완전한 제어권을 가집니다.

일부 모나드는 실행 함수를 여럿 가지고 있습니다. 우리 경우엔, runLogger를 대체할 만한 함수를 생각해볼 수 있습니다. 로그 메시지만 리턴하는 함수와, 로그메시지는 버리고 단지 결과만 반환하는 함수로도 만들 수 있을 겁니다.

흔적 남기기

Logger 액션을 실행하면, 사용자 코드는 무언가 기록하기 위해 record를 호출합니다.

-- file: ch14/Logger.hs
record :: String -> Logger ()

기록이 모나드 배관 안에서 일어나기에, 이 액션의 결과는 어떤 정보도 주지 않습니다.

일반적으로 모나드는 하나나 그 이상의 record같은 도우미 함수를 제공합니다. 이런 도우미 함수들은 우리가 그 모나드의 특수한 작용에 접근하는 수단이 됩니다.

우리 모듈은 LoggerMonad또한 정의하고 있습니다. 사용자 모듈이 이 모나드를 사용하려면 이 정의만 있으면 충분합니다.

아래는 ghci에서, 우리가 만든 모나드가 어떻게 동작하는지 보는 시연입니다.

ghci> let simple = return True :: Logger Bool
ghci> runLogger simple
(True,[])

기록을 첨부한 액션을 runLogger로 실행하면, 쌍pair 하나를 돌려받습니다. 첫째 원소는 우리 코드의 결과이고, 둘째 원소는 액션이 실행되는 동안 기록된 항목의 목록입니다. 우리는 아무것도 기록하지 않았으므로, 목록이 비어있습니다. 이걸 고쳐봅시다.

ghci> runLogger (record "hi mom!" >> return 3.1337)
(3.1337,["hi mom!"])

Logger 모나드 사용하기

아래는 우리가 Logger 모나드 안에서 glob 패턴을 정규식으로 바꾸는 걸 시작하는 방법을 보여줍니다.

-- file: ch14/Logger.hs
globToRegex cs =
    globToRegex' cs >>= \ds ->
    return ('^':ds)

언급할 가치가 있는 몇가지 코딩 스타일 특징이 있습니다. 함수 본체가 이름의 아랫줄에서 시작하는데 이러면 수평 여백을 확보할 수 있습니다. 또한 줄 끝에 익명 함수의 인자를 “매달아”놨습니다. 이건 모나딕 코드의 흔한 관습입니다.

(>>=)의 타입을 기억하세요. 바인드는 Logger 래퍼 안에서 값을 끄집어내, 이 꺼낸 값을 오른쪽 함수에 전달합니다. 오른쪽에 있는 함수는 반대로 자신의 결과를 Logger로 감쌉니다. 이것이 바로 return의 역할입니다. 순수한 값을 받아서 모나드 타입 생성자로 감쌉니다.

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type (globToRegex "" >>=)
(globToRegex "" >>=) :: (String -> Logger b) -> Logger b

심지어 거의 아무것도 하지 않는 함수를 작성했더라도, 반드시 return으로 결과를 맞는 타입이 되도록 감싸야합니다.

-- file: ch14/Logger.hs
globToRegex' :: String -> Logger String
globToRegex' "" = return "$"

record를 로그 항목을 저장하기 위해 호출하려면, 다음 액션을 연쇄하기 위해 (>>=) 대신 (>>)을 사용합니다.

-- file: ch14/Logger.hs
globToRegex' ('?':cs) =
    record "any" >>
    globToRegex' cs >>= \ds ->
    return ('.':ds)

이게 (>>=)에서 왼쪽의 결과만 무시하는 변종이라는 걸 떠올립시다. 우린 record의 결과가 항상 ()인 걸 알고있고, 그걸 입력받아도 별 의미가 없습니다.

우린 코드를 더 가지런히 하기 위해 “시퀀싱” 절에서 본 do 표기법을 쓸 수 있습니다.

-- file: ch14/Logger.hs
globToRegex' ('*':cs) = do
    record "kleene star"
    ds <- globToRegex' cs
    return (".*" ++ ds)

대부분의 경향은 두 줄이 넘어가면 do 표기법을 쓰는 거지만, do 표기법을 쓸지 (>>=)를 명시하고 익명 함수를 쓸지는 거의 취향 문제입니다. 두 스타일간에 한 가지 중요한 차이점이 있긴 하지만, “do 블록 해체하기” 절에서 다시 다룰 것입니다.

문자 클래스도 비슷한 맥락으로 파싱합니다.

-- file: ch14/Logger.hs
globToRegex' ('[':'!':c:cs) =
    record "character class, negative" >>
    charClass cs >>= \ds ->
    return ("[^" ++ c : ds)
globToRegex' ('[':c:cs) =
    record "character class" >>
    charClass cs >>= \ds ->
    return ("[" ++ c : ds)
globToRegex' ('[':_) =
    fail "unterminated character class"

순수 코드와 모나딕 코드 섞기

지금까지 본 카드로 볼 때, 모나드는 중대한 결정이 있는 듯 합니다. 모나딕 값을 감싸는 타입 생성자가 순수하고 평범한 일반 함수를 모나딕 래퍼 안에 갇힌 값에 적용하는 걸 방해합니다. 아래는 명백한 문제의 간단한 묘사입니다. Logger 모나드 안에서 돌아가는 문자열을 반환하는 사소한 코드 몇 줄이 있다고 생각해봅시다.

ghci> let m = return "foo" :: Logger String

문자열의 길이를 알고 싶다면 단순히 length를 호출하면 되지만, 문자열이 감싸여 있기 때문에 타입이 일치하지 않습니다.

ghci> length m
<interactive>:1:7:
    Couldn't match expected type `[a]'
           against inferred type `Logger String'
    In the first argument of `length', namely `m'
    In the expression: length m
    In the definition of `it': it = length m

우리가 지금까지 이 문제를 우회한 방법은 다음과 같습니다.

ghci> :type m >>= \s -> return (length s)
m >>= \s -> return (length s) :: Logger Int

문자열을 빼내기 위해 (>>=)을 쓰고, length를 호출하는 작은 익명 함수 하나를 만들어 다시 return으로 그 결과를 감쌉니다.

하스켈 코드에선 자주 이럴 필요가 생깁니다. 지름길이 이미 존재한다고 해도 별로 놀랍지 않을 겁니다. “펑터 소개” 절에서 펑터를 위해 도입한 리프팅 기법을 여기서 사용합니다. 순수 함수를 펑터로 리프팅하는 건 대개 펑터 안의 값을 꺼내고, 함수를 호출한 뒤, 그 결과를 다시 같은 생성자로 감싸는 작업을 포함합니다.

우리는 모나드에서 정확히 같은 일을 하고 있습니다. Monad 타입클래스가 이미 값을 감싸고 풀 줄 아는 (>>=)return 함수를 제공하고, liftM 함수는 모나드 구현의 세부 사항은 몰라도 되기 때문입니다.

-- file: ch14/Logger.hs
liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f m = m >>= \i ->
            return (f i)

우리가 어떤 타입이 Functor 타입클래스의 인스턴스라고 선언하려면, 그 타입에 맞는 fmap을 작성해야만 합니다. 대조적으로, liftM는 모나드 내부의 어떤 것도 알 필요가 없습니다. 그것들은 (>>=)return으로 추상화되었기 때문입니다. 우리는 적절한 타입 제한과 함께 딱 한번만 인스턴스를 작성하면 됩니다.

Control.Monad 모듈에서 liftM 함수를 이미 정의해놓았습니다.

liftM이 어떻게 가독성을 높이는지 보기 위해, 두 코드를 비교할 것입니다. 먼저, liftM을 안 쓰는 익숙한 종류의 코드입니다.

-- file: ch14/Logger.hs
charClass_wordy (']':cs) =
    globToRegex' cs >>= \ds ->
    return (']':ds)
charClass_wordy (c:cs) =
    charClass_wordy cs >>= \ds ->
    return (c:ds)

(>>=)와 익명 함수 쪼가리를 liftM으로 제거할 수 있습니다.

-- file: ch14/Logger.hs
charClass (']':cs) = (']':) `liftM` globToRegex' cs
charClass (c:cs) = (c:) `liftM` charClass cs

fmap이 그랬듯이, 대개 liftM은 연산자 형태로 사용합니다. 이런 표현식을 읽는 쉬운 방법은 “왼쪽의 순수 함수를 오른쪽의 모나딕 액션의 결과에 적용한다” 입니다.

liftM 함수는 Control.Monad가 더 긴 체인을 짤 수 있도록 제공하는 곁다리 함수만큼이나 유용합니다. 우리의 globToRegex' 함수 마지막 구문에서 하나를 볼 수 있습니다.

-- file: ch14/Logger.hs
globToRegex' (c:cs) = liftM2 (++) (escape c) (globToRegex' cs)

escape :: Char -> Logger String
escape c
    | c `elem` regexChars = record "escape" >> return ['\\',c]
    | otherwise           = return [c]
  where regexChars = "\\+()^$.{}]|"

위에서 사용한 liftM2 함수 정의는 다음과 같습니다.

-- file: ch14/Logger.hs
liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c
liftM2 f m1 m2 =
    m1 >>= \a ->
    m2 >>= \b ->
    return (f a b)

liftM2는 첫째 액션을 실행하고 둘째 액션을 실행한 다음 두 결과를 순수 함수 f로 조합해 그 결과를 감쌉니다. Control.Monad에는 liftM2의 변종이 liftM5까지 있습니다.

몇가지 오해 바로잡기

어떻게 돌아가는지 느끼기 위해 모나드 사용 예제를 충분히 보았습니다. 계속하기 전에, 곧 소개할 몇가지 반복되는 모나드에 관한 미신이 있습니다. 독자는 이런 주장들을 “고스란히” 듣게 될 테니, 잘 벼린 반박으로 준비할 필요가 있습니다.

  • 모나드는 이해하기 어려울 수 있다. 우린 이미 모나드가 몇가지 문제에서 “자연스럽게 떨어진” 것을 봤습니다. 우린 몇가지 구체적인 예시를 들고 거기서 어떤 공통점을 찾을 수 있는지 고찰하는 것이 모나드를 이해하는 데 최선의 핵심인 것을 알고 있습니다.

  • 모나드는 입출력과 절차 지향 코딩에만 유용하다. 우리가 하스켈에서 모나드를 입출력에 사용하는 것 외에도, 모나드는 수많은 용도로 애용됩니다. 우린 이미 모나드를 연쇄 계산의 단축 평가나, 복잡한 상태 숨기기, 로깅에 써봤습니다. 그럼에도, 아직 수박의 겉을 핥은 것에 불과합니다.

  • 모나드는 하스켈에서만 쓴다. 하스켈은 아마 모나드를 가장 드러내놓고 쓰는 언어입니다. 하지만 다른 언어로 모나드를 쓰는 사람들은 C++에서 Ocaml까지 걸쳐 있습니다. 모나드는 do 표기법과, 강력한 타입 시스템과 타입 추론, 언어 문법에 힘입어 하스켈에서 특히 다루기 쉬울 뿐입니다.

  • 모나드는 평가의 순서를 제어하기 위한 것이다.
    역자 주: 아래와 이어집니다.

Logger 모나드 작성하기

Logger 타입의 정의는 매우 간단합니다.

-- file: ch14/Logger.hs
newtype Logger a = Logger { execLogger :: (a, Log) }

이건 첫째 원소가 액션의 결과고 둘째 원소가 액션 실행 중 기록한 메시지 목록인 쌍입니다.

이 터플을 구별되는 타입으로 만들기 위해 newtype으로 감쌌습니다. runLogger 함수는 터플을 래퍼에서 꺼냅니다. 기록을 첨부한 액션을 실행하기 위해 드러낸 함수 runLogger는 단지 execLogger의 동의어입니다.

-- file: ch14/Logger.hs
runLogger = execLogger

record 도우미 함수는 우리가 넘긴 메시지 하나만 원소로 가진 리스트를 만듭니다.

-- file: ch14/Logger.hs
record s = Logger ((), [s])

우리가 결과가 들어가는 자리에 넣은 대로 이 액션의 결과는 ()입니다.

return으로 Monad 인스턴스 작성을 시작합시다. 매우 간단합니다. return은 아무것도 기록하지 않고, 인자를 튜플의 결과 자리에 넣어줍니다.

-- file: ch14/Logger.hs
instance Monad Logger where
    return a = Logger (a, [])

모나드의 심장인 (>>=)는 좀 더 흥미롭습니다. 바인드는 새 결과와 로그를 반환하기 위해 액션과 모나딕 함수를 결합합니다.

-- file: ch14/Logger.hs
    -- (>>=) :: Logger a -> (a -> Logger b) -> Logger b
    m >>= k = let (a, w) = execLogger m
                  n      = k a
                  (b, x) = execLogger n
              in Logger (b, w ++ x)

어떻게 되는 건지 하나씩 짚어봅시다. runLogger를 액션에서 m에서 결과 a를 얻는 데 사용하고, a를 모나딕 함수 k에 넘겨줍니다. 마찬가지로 결과 b를 추출하고, 마지막 액션의 결과 자리에 집어넣습니다. 로그 wx를 연결해 새 로그를 반환합니다.

순차적 로깅, 비순차적 평가

(>>=)의 정의는 왼쪽에서 기록한 메시지가 오른쪽에서 기록한 것보다 새 로그를 만들 때 더 앞에 나오는 걸 보장합니다. 하지만, 값 ab를 언제 평가하는진 알 수 없습니다. (>>=)는 게으릅니다.

모나드의 여러 다른 측면과 마찬가지로, 엄격함 또한 모나드의 구현자에게 달려있습니다. 이 엄격함은 모든 모나드가 공유하는 상수가 아닙니다. 실제로, 일부 모나드는 제각각의 엄격함 수준을 가진 다양한 특성을 제공하기도 합니다.

Writer 모나드

Logger 모나드는 mtl패키지의 Control.Monad.Writer 모듈에서 찾을 수 있는 표준 Writer 모나드의 특수화된 버전입니다. 우린 Writer를 사용한 예제를 “타입 클래스 사용하기” 절에서 보여줄 것입니다.

Maybe 모나드

Maybe 타입은 거의 가장 단순한 Monad 인스턴스입니다. 이 모나드는 결과가 없을 수도 있는 계산을 나타냅니다.

-- file: ch14/Maybe.hs
instance Monad Maybe where
    Just x >>= k  =  k x
    Nothing >>= _ =  Nothing

    Just _ >> k   =  k
    Nothing >> _  =  Nothing

    return x      =  Just x

    fail _        =  Nothing

많은 수의 계산식을 Maybe(>>=)(>>)으로 체인을 만들면, 그 중 하나만 Nothing을 반환해도, 나머지 계산식은 일절 평가하지 않습니다.

하지만 그 체인이 완전히 단축 평가되진 않는다는 점에 주의하세요. 체인 안의 (>>=)(>>)은 일단 왼쪽의 Nothing을 비교하고, Nothing을 오른쪽에 넘기고, 이걸 끝까지 반복합니다. 이 점을 잊어버리기 쉽습니다. 체인 안의 계산식이 실패할 때, 이어지는 Nothing의 생성, 연쇄, 소모는 비용이 싸긴 하지만, 공짜는 아닙니다.
역자 주: 원문 댓글에 따르면 2012년부터 체인에서도 단축 평가가 지원된다고 한다.

Maybe 모나드 실행하기

Maybe 모나드를 실행하기 적절한 함수는 maybe입니다. (모나드를 “실행하는 것”은 모나드를 평가하고 모나드 래퍼가 제거된 결과를 반환하는 걸 말한다는 걸 기억하세요.)

-- file: ch14/Maybe.hs
maybe :: b -> (a -> b) -> Maybe a -> b
maybe n _ Nothing  = n
maybe _ f (Just x) = f x

첫째 인자는 결과가 Nothing일 때 반환할 값입니다. 둘째 인자는 결과가 Just로 감싸여있을 때 그 안의 값을 꺼내 적용할 함수입니다. 함수를 적용한 결과를 돌려줍니다.

Maybe 타입이 너무 단순하기 때문에, 단순히 Maybe 값에 패턴 매칭을 시도하는 방법도 maybe를 호출하는 것 만큼이나 일반적입니다. 상황에 따라 어느 한 쪽이 더 가독성이 높습니다.

Maybe 적용과 좋은 API 디자인

아래는 Maybe를 모나드로 사용하는 예제입니다. 고객의 이름이 주어졌을 때, 그들의 통신사의 청구서 수령지를 찾고 싶습니다.

-- file: ch14/Carrier.hs
import qualified Data.Map as M

type PersonName = String
type PhoneNumber = String
type BillingAddress = String
data MobileCarrier = Honest_Bobs_Phone_Network
                   | Morrisas_Marvelous_Mobiles
                   | Petes_Plutocratic_Phones
                     deriving (Eq, Ord)

findCarrierBillingAddress :: PersonName
                          -> M.Map PersonName PhoneNumber
                          -> M.Map PhoneNumber MobileCarrier
                          -> M.Map MobileCarrier BillingAddress
                          -> Maybe BillingAddress

첫번째 버전은 군더더기 case 식을 가지고 오른쪽으로 진행하는 끔찍한 사다리입니다.

-- file: ch14/Carrier.hs
variation1 person phoneMap carrierMap addressMap =
    case M.lookup person phoneMap of
      Nothing -> Nothing
      Just number ->
          case M.lookup number carrierMap of
            Nothing -> Nothing
            Just carrier -> M.lookup carrier addressMap

Data.Map 모듈의 lookup 함수는 모나딕 리턴 타입을 가지고 있습니다.

ghci> :module +Data.Map
ghci> :type Data.Map.lookup
Data.Map.lookup :: (Ord k, Monad m) => k -> Map k a -> m a

다르게 보면, 받은 키가 맵에 있으면, lookup은 찾은 값을 return으로 모나드 안에 넣습니다. 아니면 fail을 호출합니다. 우리 생각에 형편없지만, 그럼에도 API 디자인에서 흥미로운 부분입니다.

  • 장점으론, lookup을 호출한 모나드에 따라 성공했을 때와 실패했을 때의 동작을 재정의할 수 있습니다. 더욱이, lookup 그 자체는 그 동작이 무엇인지 모르고 신경쓰지도 않습니다.

    위쪽의 case 식은 lookup의 결과를 Maybe 타입과 비교하므로 타입 검사에 문제가 없습니다.

  • 문제는, 물론 fail을 부적절한 모나드에서 사용하면 귀찮은 예외를 던진다는 겁니다. 우린 이미 fail 사용에 대해 경고했으니, 여기서 반복하지 않을 겁니다.

실제론, 모두들 Maybelookup의 결과 타입으로 사용합니다. 저렇게 개념적으로 간단한 함수의 결과 타입에 필요없는 일반화를 제공하고 있습니다. lookupMaybe을 반환하도록 짰어야 했습니다.

API에 대한 의심은 제껴두고, 못생긴 우리 코드를 생각합시다. Maybe가 모나드임을 활용해 더 감각적으로 사용할 수 있습니다.

-- file: ch14/Carrier.hs
variation2 person phoneMap carrierMap addressMap = do
  number <- M.lookup person phoneMap
  carrier <- M.lookup number carrierMap
  address <- M.lookup carrier addressMap
  return address

찾기가 하나라도 실패하면 처음의 case식처럼 (>>=)(>>)의 정의로 함수 전체의 결과가 Nothing이 된다고 유도됩니다.

이 버전은 훨씬 깔끔하지만, return은 필요하지 않습니다. 미적으론 코드를 더 가지런히 만들어주고, 아마 절차 지향 프로그래머의 눈엔 더 친숙하겠지만, 의미만 따지면 이건 필요없습니다. 아래는 동등한 코드입니다.

-- file: ch14/Carrier.hs
variation2a person phoneMap carrierMap addressMap = do
  number <- M.lookup person phoneMap
  carrier <- M.lookup number carrierMap
  M.lookup carrier addressMap

“부분 적용의 어색함” 절에서 Data.Map 모듈의 타입 시그니처는 부분 적용하기가 좀 성가셨습니다. lookup 함수가 좋은 예입니다. 인자를 flip 해주기만 해도, 함수를 한 줄로 짤 수 있게 됩니다.

-- file: ch14/Carrier.hs
variation3 person phoneMap carrierMap addressMap =
    lookup phoneMap person >>= lookup carrierMap >>= lookup addressMap
  where lookup = flip M.lookup

리스트 모나드

Maybe 타입이 값이 없거나 하나인 상황을 표현할 수 있는 반면에, 몇 개가 될 지 모르는 결과를 넘겨주고 싶은 상황이 많이 있습니다. 분명 리스트가 이 목적에 딱 알맞습니다. 리스트의 타입은 우리가 리스트를 모나드로 쓸 수 있을 거라고 암시합니다. 리스트의 타입 생성자가 자유 변수 하나를 가졌기 때문입니다. 그리고 아니나다를까, 우린 리스트를 모나드로 쓸 수 있습니다.

단순히 프렐류드의 리스트 타입의 Monad 인스턴스를 보여주기보다, 인스턴스가 어떤 모양을 가져야만 할지 생각해봅시다. 이건 하기 쉽습니다. (>>=)return의 타입을 찾고, 조금 치환한 다음에 익숙한 리스트 함수를 사용할 수 있는지 확인할 겁니다.

둘 중에 좀 더 명백한 건 return입니다. 우리는 return이 타입 a를 받고, 그걸 타입 생성자 m으로 감싸 m a 타입을 주는 걸 압니다. 또한 우리는 여기서 타입 생성자가 []인 걸 압니다. 타입 변수 m을 이 타입 생성자로 치환하면 타입 [] a를 얻습니다. (물론, 실제 적법한 표기입니다!), 그리고 더 친숙한 형태인 [a]로 다시 쓸 수 있습니다.

우린 이제 리스트를 위한 returna -> [a] 타입을 가져야만 하는 것을 압니다. return을 구현하는 데 몇가지 가능성이 있습니다. return은 빈 리스트나 원소 1개짜리singleton, 싱글턴 리스트, 혹은 무한 리스트를 반환할 수 있습니다. 지금까지의 모나드 지식에 의하면 가장 그럴 듯한 동작은 싱글턴 리스트입니다. 이건 정보를 버리지 않고, 무한히 반복하지도 않습니다.

-- file: ch14/ListMonad.hs
returnSingleton :: a -> [a]
returnSingleton x = [x]

만약 (>>=) 타입에 return에서 했던 것과 같은 치환을 하면, 바인드가 [a] -> (a -> [b]) -> [b] 타입을 가져야만 하는 걸 알 수 있습니다. 이건 map의 타입과 가까워 보입니다.

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type map
map :: (a -> b) -> [a] -> [b]

map의 인자 타입 순서가 일치하지 않지만, 고치기 쉽습니다.

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type flip map
flip map :: [a] -> (a -> b) -> [b]

아직 문제가 남아있습니다. flip map의 두번째 인자는 a -> b지만, 리스트 (>>=)의 두번째 인자는 a -> [b]입니다. 여기선 무엇을 해야할까요?

조금 더 치환을 해보고 타입에 무슨 일이 일어나는지 살펴봅시다. flip map 함수는 어떤 타입 b를 결과로 반환할 수 있습니다. 만약 flip map의 타입 시그니처에 나오는 두 b[b]로 바꾸면 타입 시그니처는 a -> (a -> [b]) -> [[b]]가 될 것입니다. 즉, 리스트에 리스트를 반환하는 함수를 매핑하면, 우리는 리스트의 리스트를 받게 됩니다.

ghci> flip map [1,2,3] (\a -> [a,a+100])
[[1,101],[2,102],[3,103]]

흥미롭게도, 우린 아직 얼마나 타입 시그니처가 밀접한지 확인하지 못했습니다. (>>=)의 타입은 [a] -> (a -> [b]) -> [b]이지만, flip map에 리스트를 반환하는 함수를 짝지은 타입은 [a] -> (a -> [b]) -> [[b]]입니다. 아직 타입 하나가 불일치합니다. 우린 단지 불일치하는 타입을 타입 시그니처 맨 끝으로 옮겼을 뿐입니다. 하지만, 우리의 저글링은 헛된 게 아니었습니다. 이제 [[b]]를 받아 [b]를 반환하는 함수가 필요하고, concat이 써달라고 우릴 부르고 있습니다.

ghci> :type concat
concat :: [[a]] -> [a]

타입은 map의 인자를 뒤집고 그 결과를 concat해 1중 리스트로 만들어야 한다고 암시합니다.

ghci> :type \xs f -> concat (map f xs)
\xs f -> concat (map f xs) :: [a] -> (a -> [a1]) -> [a1]

이게 바로 리스트의 (>>=)입니다.

-- file: ch14/ListMonad.hs
instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)

바인드는 리스트 xs의 모든 원소에 f를 적용하고, 그 결과를 1중리스트로 만들기 위해 접합합니다.

두 핵심 Monad 정의로, 남은 비핵심 함수인 (>>)fail의 구현은 명백해 보입니다.

-- file: ch14/ListMonad.hs
    m1 >> m2 = concat (map (\_ -> m2) m1)
    fail _ = []

리스트 모나드 이해하기

리스트 모나드는 익숙한 하스켈 도구인 리스트 조건제시식List comprehension과 유사합니다. 이 유사성을 두 리스트의 데카르트 곱을 계산해서 보겠습니다. 먼저, 리스트 조건제시식입니다.

-- file: ch14/CartesianProduct.hs
comprehensive xs ys = [(x,y) | x <- xs, y <- ys]

이번만, 모나딕 코드에 레이아웃 표기법 대신 괄호 표기법을 쓰겠습니다. 이러면 모나딕 코드가 리스트 조건제시식과 얼마나 비슷한지 확 보일 겁니다.

-- file: ch14/CartesianProduct.hs
monadic xs ys = do { x <- xs; y <- ys; return (x,y) }

유일한 차이점을 조립하는 값이 리스트 조건제시식처럼 앞에 온 게 아니라 연속되는 식의 맨 끝에 온다는 점입니다. 두 함수의 결과조차 같습니다.

ghci> comprehensive [1,2] "bar"
[(1,'b'),(1,'a'),(1,'r'),(2,'b'),(2,'a'),(2,'r')]
ghci> comprehensive [1,2] "bar" == monadic [1,2] "bar"
True

초기의 리스트 모나드 때문에 납득하기 힘들 수 있으니, 데카르트 곱 예제로 돌아가 자세히 살펴봅시다. 이번엔, 괄호대신 들여쓰기를 쓰겠습니다.

-- file: ch14/CartesianProduct.hs
blockyDo xs ys = do
    x <- xs
    y <- ys
    return (x, y)

xs의 각각의 원소로, x를 바꿔가면서 한번씩 함수의 나머지 부분을 평가합니다. ys도 마찬가지로 y에 각각의 원소를 바인딩하고 나머지 부분을 한번씩 평가합니다.

실제 여기 있는 건 2중 루프입니다! 이건 모나드의 중요한 사실을 조명합니다. 어떤 모나드를 사용할 지 알기 전까지 모나드 코드 블록이 어떤 동작을 할 지 예측할 수 없습니다.

이제 코드를 더 명시적으로 살필 텐데, 일단 밑바탕 구조를 명확히 하기 위해 먼저 do 표기법을 없애봅시다. 중첩 루프를 명백히 하기 위해 일부러 독특하게 들여쓰기를 했습니다.

-- file: ch14/CartesianProduct.hs
blockyPlain xs ys =
    xs >>=
    \x -> ys >>=
    \y -> return (x, y)

blockyPlain_reloaded xs ys =
    concat (map (\x ->
                 concat (map (\y ->
                              return (x, y))
                         ys))
            xs)

만약 xs[1,2,3]이라면, 그 다음 두 줄은 x1인 채로 평가되고, 그 다음 2, 마지막으로 3인 채 평가합니다. 만약 ys[True, False]면, 마지막 줄은 여섯 번 평가됩니다. x1이고 yTrue인 한 번, 다시 x1이고 yFalse인 한 번... 으로 쭉. return 식은 각각의 터플을 원소 1개짜리 리스트로 감쌉니다.

리스트 모나드 동작시키기

이건 간단한 무차별 대입 제약조건 검사기입니다. 정수 하나를 주면, 곱해서 그 정수가 나오는(이게 제약조건입니다) 모든 쌍을 찾아줍니다.

-- file: ch14/MultiplyTo.hs
guarded :: Bool -> [a] -> [a]
guarded True  xs = xs
guarded False _  = []

multiplyTo :: Int -> [(Int, Int)]
multiplyTo n = do
  x <- [1..n]
  y <- [x..n]
  guarded (x * y == n) $
    return (x, y)

ghci에서 돌려봅시다.

ghci> multiplyTo 8
[(1,8),(2,4)]
ghci> multiplyTo 100
[(1,100),(2,50),(4,25),(5,20),(10,10)]
ghci> multiplyTo 891
[(1,891),(3,297),(9,99),(11,81),(27,33)]

do 블록 해체하기

하스켈의 do 구문은 설탕 구문syntactic sugar의 예입니다. do 구문은 (>>=)과 익명 함수를 쓰지 않고 모나딕 코드를 짜는 대안을 제공합니다. 설탕 털기Desugaring는 설탕 구문에서 핵심 언어로의 변환입니다.

do 블록의 설탕을 터는 규칙은 이해하기 쉽습니다. 우린 컴파일러가 do 키워드가 없을 때까지 기계적으로 이 규칙을 do 블록에 적용한다고 생각해도 됩니다.

do 키워드 뒤에 액션 하나만 오면 액션 그 자체로 바뀝니다.

-- file: ch14/Do.hs
doNotation1 =
    do act
-- file: ch14/Do.hs
translated1 =
    act

액션이 하나 이상 이어진 do 키워드는 첫번째 액션으로 바꾸고, (>>)do를 나머지 액션 앞에 넣습니다. 이 규칙을 계속 적용하면 do 전체가 (>>)으로 이어집니다.

-- file: ch14/Do.hs
doNotation2 =
    do act1
       act2
       {- ... etc. -}
       actN
-- file: ch14/Do.hs
translated2 =
    act1 >>
    do act2
       {- ... etc. -}
       actN

finalTranslation2 =
    act1 >>
    act2 >>
    {- ... etc. -}
    actN

<- 표기법 변환은 눈여겨 볼 가치가 있습니다. <-의 왼쪽은 일반적인 하스켈 패턴입니다. 변수 하나일 수도 있고, 더 복잡한 무언가일 수도 있습니다. 가드 표현식은 쓸 수 없습니다.

-- file: ch14/Do.hs
doNotation3 =
    do pattern <- act1
       act2
       {- ... etc. -}
       actN
-- file: ch14/Do.hs
translated3 =
    let f pattern = do act2
                       {- ... etc. -}
                       actN
        f _     = fail "..."
    in act1 >>= f

이 왼쪽 패턴을 let 바인딩에서 (위의 예에선 f인) 고유한 이름을 가진 지역 함수로 바꿉니다. <-의 오른쪽 액션은 (>>=)로 아까의 지역함수와 연결합니다.

여기서 놀라운 부분은, 만약 패턴 매칭이 실패하면 지역 함수는 모나드의 fail 구현을 호출한다는 겁니다. 아래는 Maybe 모나드를 사용한 예입니다.

-- file: ch14/Do.hs
robust :: [a] -> Maybe a
robust xs = do (_:x:_) <- Just xs
               return x

Maybe 모나드의 fail 구현은 단순히 Nothing을 반환합니다. 위의 패턴 매칭이 실패하면 우리는 Nothing을 결과로 얻습니다.

ghci> robust [1,2,3]
Just 2
ghci> robust [1]
Nothing

마지막으로, 우리가 let 표현식을 do 블록 안에서 사용하면, 대개 in 키워드는 생략할 수 있습니다. 블록 안의 이어지는 액션은 반드시 let 키워드에 맞춰 정렬해야 합니다.

-- file: ch14/Do.hs
doNotation4 =
    do let val1 = expr1
           val2 = expr2
           {- ... etc. -}
           valN = exprN
       act1
       act2
       {- ... etc. -}
       actN
-- file: ch14/Do.hs
translated4 =
    let val1 = expr1
        val2 = expr2
        valN = exprN
    in do act1
          act2
          {- ... etc. -}
          actN

프로그래밍 가능한 세미콜론으로서의 모나드

“오프사이드 규칙은 필수가 아닙니다” 절에서, 들여쓰기를 사용하는 게 하스켈에서의 관례라고 했지만, 필수는 아닙니다. do 블록을 들여쓰기 대신 명시적 구조를 사용해 작성할 수 있습니다.

-- file: ch14/Do.hs
semicolon = do
  {
    act1;
    val1 <- act2;
    let { val2 = expr1 };
    actN;
  }
-- file: ch14/Do.hs
semicolonTranslated =
    act1 >>
    let f val1 = let val2 = expr1
                 in actN
        f _ = fail "..."
    in act2 >>= f

이런 식으로 명시적 구조를 쓰는 경우가 드물긴 하지만, 식을 구분하기 위해 세미콜론을 사용한다는 사실을 적절한 표어를 제시합니다. 모나드는 일종의 “프로그래밍 가능한 세미콜론”입니다. (>>)(>>=)의 동작이 모나드마다 다르기 때문입니다.

왜 설탕을 털어내나요?

(>>=)를 명시적으로 코드에 적음으로써, 단순히 액션을 연속하는 게 아니라, 컴비네이터로 함수를 엮어내고 있다는 사실을 상기할 수 있습니다.

독자가 모나드에 대해 초보자라고 느낀다면, 설탕 구문인 do 표기법보다 (>>=)를 명시적으로 적는 게 바람직할 겁니다. 대부분의 프로그래머에게, 실제 무엇이 일어나는지 반복적으로 강화를 하는 건 상황을 명료하게 유지하도록 도와줍니다. (절차 지향 프로그래머에겐 IO 모나드에서 좀 떨어져서, do 블록이 액션의 연속에 불과하다고 가정하는 게 쉬울 수 있습니다.)

모나드에 좀 더 익숙해지면, 함수를 짤 때 더 적절한 스타일을 고를 수 있습니다. 실제로, 독자가 다른 사람의 모나딕 코드를 읽게 되면, 일반적이진 않지만 드물지도 않게 do 표기법과 (>>=) 둘 다 함수 하나에서 혼용한 것을 보게 될 겁니다.

do 표기법을 쓰든 안 쓰든 간에 (=<<) 함수를 자주 볼 수 있습니다. 이건 (>>=)를 뒤집은 버전입니다.

ghci> :type (>>=)
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
ghci> :type (=<<)
(=<<) :: (Monad m) => (a -> m b) -> m a -> m b

(=<<)로 오른쪽에서 왼쪽으로 진행하는 일반적인 하스켈 스타일에서 모나딕 함수를 편하게 합성할 수 있습니다.

-- file: ch14/CartesianProduct.hs
wordCount = print . length . words =<< getContents

상태 모나드

이 장의 앞 부분에서 10장. 코드 사례 분석: 바이너리 데이터 포맷 파싱에 나온 Parse가 모나드라는 걸 알아냈습니다. Parse는 두 가지 논리적으로 구별되는 면모가 있습니다. 하나는 파싱 실패와 자세한 메시지를 제공하는 것이고, 이건 Either 타입으로 나타냈습니다. 다른 하나는 암시적 상태를 전달하는 것이고, 우리 경우엔 파싱하고 남은 ByteString이었습니다.

하스켈 프로그램에선 표준 라이브러리가 State라는 이름의 딱 이 목적을 위한 모나드를 제공할 정도로 상태를 읽고 쓸 필요가 있었습니다. 이 모나드는 Control.Monad.State 모듈에 있습니다.

우리의 Parse 타입이 ByteString을 상태로 전달한 데 비해, State 모나드는 아무 타입이나 전달할 수 있습니다. 이 미정 타입을 s라고 부르겠습니다.

우리가 상태로 하려는 명백하고 일반적인 작업이 뭘까요? 상태를 건네고, 그걸 조사하고, 결과와 새 상태값을 생성합니다. 결과가 어떤 타입 a가 될 수 있다고 합시다. 아까의 생각을 타입 시그니처로 표현하면 s -> (a, s)입니다. 상태 s를 받고, 그걸로 무언가 하고, 결과 a와 아마 새 상태일 s를 반환합니다.

유사 상태 모나드

유사 State 모나드를 짜보고, 진짜를 확인해봅시다. 위에서 설명한 대로 명백한 타입을 가진 타입 정의부터 시작합시다.

-- file: ch14/SimpleState.hs
type SimpleState s a = s -> (a, s)

우리 모나드는 결과를 산출하기도 하며 한 상태를 다른 상태로 바꾸는 함수입니다. 이 때문에, 상태 모나드는 때때로 상태 변환기 모나드라고도 부릅니다.

예. 이건 타입 동의어이지, 새 타입이 아닙니다. 고로 살짝 꼼수를 쓰겠습니다. 지금은 참고 기다려주세요. 이건 이어지는 설명을 간단하게 만듭니다.

이 장의 앞에서 모나드는 타입 변수 하나를 받는 타입 생성자 하나를 가진다고 했습니다. 그리고 아직 우리는 인자를 2개 받는 타입을 가졌습니다. 여기에서 핵심은 우리가 함수를 부분 적용 할 수 있듯이 타입도 부분 적용이 가능하다는 걸 이해하는 겁니다. 예제를 따라가면 이해하기 쉽습니다.

-- file: ch14/SimpleState.hs
type StringState a = SimpleState String a

여기서 타입 변수 sString을 묶었습니다bind. 그래도 StringState 타입은 아직 타입 인자 a를 가지고 있습니다. 이제 우리가 모나드에 알맞은 타입 생성자를 가진 게 드러났습니다. 즉, 우리의 모나드 타입 생성자는 SimpleState 혼자가 아니라 SimpleState s입니다.

모나드를 만드는 데 필요한 다음 재료는 return 함수입니다.

-- file: ch14/SimpleState.hs
returnSt :: a -> SimpleState s a
returnSt a = \s -> (a, s)

이 함수는 현재 결과와 상태를 받아 “터플로 만들” 뿐입니다. 독자는 이제 여러 인자를 받는 하스켈 함수는 단일 인자 함수가 엮인 거라는 개념에 할 익숙할 텐데, 안 그런 경우를 대비해 returnSt가 얼마나 간단한지 친숙한 방법으로 보겠습니다.

-- file: ch14/SimpleState.hs
returnAlt :: a -> SimpleState s a
returnAlt a s = (a, s)

우리 모나딕 퍼즐의 마지막 조각은 (>>=)의 정의입니다. 여기는, 표준 라이브러리 State(>>=)에서 실제 변수 이름을 따왔습니다.

-- file: ch14/SimpleState.hs
bindSt :: (SimpleState s a) -> (a -> SimpleState s b) -> SimpleState s b
bindSt m k = \s -> let (a, s') = m s
                   in (k a) s'

저 한 글자짜리 변수 이름들은 딱히 가독성에 도움이 안 되니, 더 의미 있는 이름으로 바꿀 수 있는지 봅시다.

-- file: ch14/SimpleState.hs
-- m == step
-- k == makeStep
-- s == oldState

bindAlt step makeStep oldState =
    let (result, newState) = step oldState
    in  (makeStep result) newState

이 정의를 이해하기 위해, steps -> (a, s) 타입의 함수라는 걸 기억하세요. 우리가 이걸 평가하면 터플을 받고, 이 터플을 s -> (a, s) 타입의 새 함수를 반환하는 데 사용해야 합니다. 아마도 bindAlt의 타입 시그니처에서 SimpleState 타입 동의어를 지우고 인자와 결과의 타입을 확인하는 게 더 파악하기 쉬울 겁니다.

-- file: ch14/SimpleState.hs
bindAlt :: (s -> (a, s))        -- step
        -> (a -> s -> (b, s))   -- makeStep
        -> (s -> (b, s))        -- (makeStep result) newState

상태 읽고 수정하기

상태 모나드의 (>>=)return 정의는 배관처럼 동작합니다. 이 함수들은 상태 조각을 전달하지만, 어떤 식으로든 건드리진 않습니다. 상태로 유용한 작업을 하기 위해 몇가지 또다른 간단한 함수가 필요합니다.

-- file: ch14/SimpleState.hs
getSt :: SimpleState s s
getSt = \s -> (s, s)

putSt :: s -> SimpleState s ()
putSt s = \_ -> ((), s)

getSt 함수는 단순히 현재 상태를 얻어 결과로 반환합니다. 반면 putSt는 현재 상태를 무시하고 상태를 입력으로 갈아치웁니다.

진짜 상태 모나드를 만들 수 있을까?

이전 절에서 썼던 유일한 단순화 요령은 SimpleState 타입 정의 대신 타입 동의어를 사용한 것입니다. 만약 우리가 동시에 newtype 래퍼를 사용했다면, 추가적인 감싸기와 풀기가 우리 코드를 파악하기 힘들게 했을 겁니다.

Monad 인스턴스를 정의하기 위해, (>>=)return 말고도 타입 생성자도 제공해야 합니다. 이 사실은 우리를 State진짜 정의로 이끕니다.

-- file: ch14/State.hs
newtype State s a = State {
      runState :: s -> (a, s)
    }

우리의 s -> (a, s) 타입을 State 생성자로 감쌌을 뿐입니다. 하스켈의 레코드 구문으로 타입을 정의해서, State 값을 생성자에서 꺼내는 runState 함수를 자동으로 만들었습니다. runState의 타입은 State s a -> s -> (a, s)입니다.

return의 정의는 함수를 State 생성자로 감쌌다는 것만 빼면 SimpleState와 거의 동일합니다.

-- file: ch14/State.hs
returnState :: a -> State s a
returnState a = State $ \s -> (a, s)

(>>=)의 정의는 약간 더 복잡해졌습니다. State 래퍼를 없애기 위해 runState를 써야 하기 때문입니다.

-- file: ch14/State.hs
bindState :: State s a -> (a -> State s b) -> State s b
bindState m k = State $ \s -> let (a, s') = runState m s
                              in runState (k a) s'

이 함수는 이전 버전 bindSt와 몇몇 값을 감싸고 푸는 점에서만 다릅니다. 장부 업무에서 “실제 업무”를 분리함으로써, 정말 무엇이 일어나는지 더 명백하게 만들었습니다.

마찬가지로 약간의 감싸기를 추가해서 상태를 읽고 수정하는 함수도 수정했습니다.

-- file: ch14/State.hs
get :: State s s
get = State $ \s -> (s, s)

put :: s -> State s ()
put s = State $ \_ -> ((), s)

상태 모나드 사용하기: 랜덤 값 생성

우린 이미 이진 데이터를 파싱하기 위한 상태 모나드의 선배 격인 Parse를 사용해 봤습니다. 그 땐 우리가 조작하는 상태의 타입을 Parse 타입에 직접 연결했습니다.

대조적으로 State 모나드는 임의 타입의 상태를 인자로 받습니다. State ByteString같이 상태의 타입을 제공합니다.

상태 모나드는 절차 지향 언어를 배운 경험이 있다면 다른 모나드보다 더 친숙할 겁니다. 무엇보다도, 절차 지향 언어는 암시적인 상태를 전달하고, 일부분을 읽고, 할당으로 다른 것을 변경하는 것이 주이고, 이건 또한 상태 모나드의 용도이기도 합니다.

그러므로 쓸데없이 상태 모나드를 사용하라고 응원하는 것보다, 유사 난수 생성을 예로 들어 상태 모나드를 어떻게 간단히 적용할 수 있는지 보여줄 겁니다. 절차 지향 언어에선, 대개 고르게 분포한 유사 난수를 얻기 쉽습니다. 예를 들어 C에선, 스스로 갱신하는 전역 상태를 이용해 난수를 생성하는 rand 함수가 있습니다.

하스켈의 표준 난수 생성 모듈은 System.Random입니다. 이 모듈은 숫자 뿐만 아니라 임의 타입의 난수를 만들 수 있습니다. 이 모듈은 IO 모나드 안에 있는 몇가지 간편한 함수를 담고 있습니다. 예를 들어, C의 rand 함수를 허술하게 따라하면 다음이 됩니다:

-- file: ch14/Random.hs
import System.Random

rand :: IO Int
rand = getStdRandom (randomR (0, maxBound))

(randomR 함수는 생성할 난수 값의 폐구간(양 끝을 포함하는 범위)을 인자로 받습니다.)

System.Random 모듈은 Int 값 난수의 근원을 정의하도록 돕는 RandomGen 타입클래스를 제공합니다. StdGen 타입은 RandomGen의 인스턴스입니다. StdGen은 유사 난수를 생성합니다. 만약 우리가 진짜 난수인 외부 원천을 가졌다면 그걸 RandomGen의 인스턴스로 만들어 유사 난수 대신 진짜 난수 값을 얻을 수 있을 겁니다.

또다른 타입클래스 Random은 어떻게 특정 타입의 랜덤 값을 앋는지 지정합니다. 랜덤 모듈은 모든 일반적인 단순한 타입에 Random 인스턴스를 정의했습니다.

덧붙이자면, 위의 rand 정의는 IO 모나드 안에 있는 내장 전역 난수 생성기를 읽고 수정합니다.

순수를 위한 첫번째 시도

IO 모나드를 가능한 한 피하라고 누누히 강조했는데, 단지 난수 값을 얻기 위해 IO 모나드로 끝어들인다면 부끄러울 겁니다. 실제로, System.Random은 순수한 난수 생성 함수를 가지고 있습니다.

순수함의 전통적인 단점은, 우리가 난수 생성기를 얻거나 만든 후, 우리가 만든 곳에서 필요한 것까지 운반해야 한다는 것입니다. 마침내 호출하면, 그건 난수 생성기를 반환합니다. 기억하세요. 우린 순수한 코드를 짜기 때문에 이미 존재하는 생성기의 상태를 바꿀 수 없습니다.

만약 불변성을 잊어버리고 함수 안에서 같은 생성기를 계속 쓴다면, 우린 정확히 같은 “난수”를 매번 받게 됩니다.

-- file: ch14/Random.hs
twoBadRandoms :: RandomGen g => g -> (Int, Int)
twoBadRandoms gen = (fst $ random gen, fst $ random gen)

말할 것도 없이, 행복할 수 없는 결과를 초래합니다.

ghci> twoBadRandoms `fmap` getStdGen
Loading package old-locale-1.0.0.0 ... linking ... done.
Loading package old-time-1.0.0.0 ... linking ... done.
Loading package random-1.0.0.0 ... linking ... done.
Loading package mtl-1.1.0.0 ... linking ... done.
(945769311181683171,945769311181683171)

randomrandomR에 넘겨주는 범위로 사용자가 제공한 범위대신 미리 정해진 범위를 사용합니다. getStdGen 함수는 IO 모나드에서 전역 표준 난수 생성기의 현재 값을 받아옵니다.

유감스럽게도, 정확히 전달하고 생성기를 연속적으로 사용하는 것은 별로 보기 좋지 않습니다. 여기 간단한 예입니다.

-- file: ch14/Random.hs
twoGoodRandoms :: RandomGen g => g -> ((Int, Int), g)
twoGoodRandoms gen = let (a, gen') = random gen
                         (b, gen'') = random gen'
                     in ((a, b), gen'')

하지만 이제 우린 생성기를 숨기는 데 좋은 후보로 보이는 상태 모나드를 알고 있습니다. 상태 모나드는 우리가 변할 수 있는 상태를 깔끔히 관리하게 하는 동시에 파일 수정이나 네트워크 연결 같은 예측 불가능한 부수 효과로부터 우리 코드가 안전함을 보장합니다. 상태 모나드의 순수함은 우리 코드의 동작을 추론하기 쉽게 만듭니다.

상태 모나드 안의 난수 값

이건 StdGen을 상태로 삼고 전달하는 상태 모나드입니다.

-- file: ch14/Random.hs
type RandomState a = State StdGen a

타입 동의어는 물론 필수는 아니지만, 편리합니다. 이건 타이핑을 다소 줄여주고, 우리가 StdGen을 다른 생성기로 바꾸고 싶을 때, 바꿔야 할 타입 시그니처 수를 줄여줍니다.

난수를 생성하는 건 이제 현재 생성기를 가져오고, 사용하고, 상태를 새 생성기로 교체하는 문제입니다.

-- file: ch14/Random.hs
getRandom :: Random a => RandomState a
getRandom =
  get >>= \gen ->
  let (val, gen') = random gen in
  put gen' >>
  return val

우린 이제 한 쌍의 난수를 얻는 함수를 이전에 봤던 모나딕 도구를 사용해 훨씬 간결하게 작성할 수 있습니다.

-- file: ch14/Random.hs
getTwoRandoms :: Random a => RandomState (a, a)
getTwoRandoms = liftM2 (,) getRandom getRandom

연습문제

  1. getRandomdo 표기법으로 다시 짜 보세요.

상태 모나드 실행하기

이미 말했듯이, 각각의 모나드는 자기만의 특별한 평가 함수를 가지고 있습니다. 상태 모나드에선 아래 몇가지에서 선택할 수 있습니다.

  • runState는 결과와 마지막 상태를 반환합니다.

  • evalState는 결과만 반환하고, 마지막 상태는 버립니다.

  • execState는 결과는 버리고, 마지막 상태만 반환합니다.

evalStateexecState함수는 단순히 fstsnd를 각각 runState에 합성한 겁니다. 때문에 셋 중에서 runState가 가장 중요합니다.

이건 getTwoRandoms 함수를 어떻게 구현하는지에 관한 완전한 예제입니다.

-- file: ch14/Random.hs
runTwoRandoms :: IO (Int, Int)
runTwoRandoms = do
  oldState <- getStdGen
  let (result, newState) = runState getTwoRandoms oldState
  setStdGen newState
  return result

runState 호출은 표준 패턴을 따르고 있습니다. runState에 상태 모나드 안에 있는 함수와 처음 상태를 넘겨줍니다. 그러면 함수의 결과와 최종 상태를 반환합니다.

runState 호출을 감싸는 코드는 단지 전역 StdGen 값을 구하고, runTwoRandoms나 다른 난수 발생 함수가 바뀐 상태를 쓸 수 있도록 전역 StdGen을 바꿉니다.

조금 더 많은 상태는 어떤가요?

상태 하나만 전달하면서 그럴 듯한 코드를 짜는 건 좀 상상하기 힘듭니다. 한 번에 상태 여러 개를 끌어오고 싶다면, 일반적인 요령은 데이터 타입으로 관리하는 것입니다. 아래는 우리가 구한 난수의 개수를 기억하는 예제입니다.

-- file: ch14/Random.hs
data CountedRandom = CountedRandom {
      crGen :: StdGen
    , crCount :: Int
    }

type CRState = State CountedRandom

getCountedRandom :: Random a => CRState a
getCountedRandom = do
  st <- get
  let (val, gen') = random (crGen st)
  put CountedRandom { crGen = gen', crCount = crCount st + 1 }
  return val

이 예제는 호출할 때마다 원래 상태의 두 원소를 소모하고, 완전히 새로운 상태를 조립합니다. 우리는 일부분만 더 자주 읽거나 변경하고 싶을 듯 합니다. 이 함수는 우리가 지금까지 생성한 난수의 개수를 가져옵니다.

-- file: ch14/Random.hs
getCount :: CRState Int
getCount = crCount `liftM` get

이 예제는 왜 우리가 CountedRandom 상태를 레코드 구문으로 정의했는지 보여줍니다. 레코드 구문이 제공하는 접근자를 get과 연결해 상태의 일부분만 읽을 수 있습니다.

상태를 부분적으로 갱신하고 싶을 때, 코드가 매력적으로 보이진 않습니다.

-- file: ch14/Random.hs
putCount :: Int -> CRState ()
putCount a = do
  st <- get
  put st { crCount = a }

여기서 함수 대신에 레코드 갱신 구문을 사용했습니다. 식 st { crCount = a }crCount 필드만 a로 다른 st의 복제를 생성합니다. 이건 구문을 사용한 꼼수기 때문에, 함수를 사용할 때의 유연성은 얻을 수 없습니다. 레코드 구문은 하스켈의 일반적인 우아함을 드러내진 않지만, 최소한 돌아가게 만들긴 합니다.

getput을 합친 modify라는 이름의 함수가 있습니다. 이 함수는 인자로 상태 변환 함수를 받지만, 만족스럽지 못합니다. 우린 아직 레코드 갱신 구문의 어색함에서 빠져나오지 못 했습니다.

-- file: ch14/Random.hs
putCountModify :: Int -> CRState ()
putCountModify a = modify $ \st -> st { crCount = a }

모나드와 펑터

펑터와 모나드는 밀접한 연관이 있습니다. 이 용어들은 수학의 한 갈래인 범주론에서 빌려왔지만, 손상 없이 고스란히 의미를 가지고 있습니다.

범주론에서 모나드는 펑터로 만듭니다. 독자는 그러면 하스켈에서 Monad 타입클래스가 Functor 타입클래스의 서브클래스가 되어야 하지 않을까하고 기대할 수 있지만, 표준 프렐류드에는 그런 정의가 없습니다. 불행한 실수입니다.
역자 주: 고쳐질 것 같다고 함.

하지만 하스켈 라이브러리 제작자들은 우회법을 쓰고 있습니다. 누군가 Monad 인스턴스를 정의해 놓았다면, 그들은 거의 반드시 Functor 인스턴스도 정의해 놓습니다. Functor 타입클래스의 fmap 함수를 모나드에 사용할 수 있다고 기대해도 좋습니다.

fmap의 타입 시그니처를 일부 우리가 이미 본 표준 모나드 함수의 시그니처와 비교해보면, fmap이 모나드에서 뭘 하는지 힌트를 얻을 수 있습니다.

ghci> :type fmap
fmap :: (Functor f) => (a -> b) -> f a -> f b
ghci> :module +Control.Monad
ghci> :type liftM
liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r

짐작했겠지만, fmap은 순수 함수를 liftM처럼 모나드 안으로 리프팅합니다.

모나드를 보는 다른 방법

이제 모나드와 펑터의 관계를 알았으니, 리스트 모나드를 다시 보면 흥미로운 걸 찾을 수 있을 겁니다. 특히 리스트의 (>>=)정의를 보세요.

-- file: ch14/ListMonad.hs
instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)

f의 타입이 a -> [a]라는 걸 떠올리세요. map f xs를 호출하면, concat으로 “평탄화” 해야 하는 [[a]] 타입의 값을 얻게 됩니다.

MonadFunctor의 서브클래스였다면 뭘 할 수 있었을지 상상해보세요. 리스트의 fmapmap으로 정의했기에, (>>=)의 정의에서 mapfmap으로 바꿀 수 있습니다. 이 자체로는 신기하지 않지만, 더 진행할 수 있다고 가정해봅시다.

[[a]] -> [a] 타입의 concat 함수는 알다시피 리스트의 중첩을 평탄화합니다. 우리는 이 타입 시그니처를 리스트에서 모나드로 일반화해서 “한 단계 중첩을 줄여주는m (m a) -> m a 타입 시그니처를 얻을 수 있습니다. 이 타입을 가진 함수는 관습적으로 join이라고 이름이 붙었습니다.

joinfmap의 정의를 가지고 있다면, 모든 모나드에서 (>>=)가 매우 일반적이 돼 정의할 필요가 없어집니다. 이건 (>>=)의 일반적 정의를 가진 Monad 타입클래스의 다른 정의로 볼 만한 겁니다.

-- file: ch14/AltMonad.hs
import Prelude hiding ((>>=), return)

class Functor m => AltMonad m where
    join :: m (m a) -> m a
    return :: a -> m a

(>>=) :: AltMonad m => m a -> (a -> m b) -> m b
xs >>= f = join (fmap f xs)

두 모나드 정의 중 어느 것도 “더 낫지”는 않습니다. join이 있으면 (>>=)를 작성할 수 있고, 반대도 가능하기 때문입니다. 하지만 다른 관점은 참신할 수 있습니다.

모나딕 래핑을 한 단계 벗기는 건 사실 실제 상황에서 유용할 수 있습니다. Control.Monad 모듈에서 join의 일반적 정의를 찾을 수 있습니다.

-- file: ch14/MonadJoin.hs
join :: Monad m => m (m a) -> m a
join x = x >>= id

이건 join이 뭘 하는지에 관한 예입니다.

ghci> join (Just (Just 1))
Just 1
ghci> join Nothing
Nothing
ghci> join [[1],[2,3]]
[1,2,3]

모나드 법칙과 좋은 코딩 스타일

“펑터에 대해 더 생각해보기” 절에서, 펑터가 항상 어떻게 동작해야만 하는지 두 가지 규칙을 제시했습니다.

-- file: ch14/MonadLaws.hs
fmap id        ==   id 
fmap (f . g)   ==   fmap f . fmap g

모나드가 지켜야 하는 규칙도 있습니다. 아래에 있는 세가지 규칙을 모나드 법칙이라고 부릅니다. 하스켈 구현은 이 규칙을 강제하지 않습니다. 이 규칙을 지키는 건 Monad 인스턴스를 작성자에게 달렸습니다.

모나드 규칙은 단순히 “모나드는 날 놀래키지 말아야 한다”를 딱딱하게 말하는 방법입니다. 이론적으론 우린 이 절 전체를 넘어갈 수도 있을 겁니다. 하지만 그러면 부끄러울 겁니다. 법칙이 자칫 간과할 수도 있는 지혜를 담고 있기 때문입니다.

법칙 읽기

아래에 있는 각각의 법칙을 “=== 왼쪽의 식과 오른쪽의 식이 같다”고 읽을 수 있습니다.

첫째 모나드 법칙은 return(>>=)좌항등원이라는 것입니다.

-- file: ch14/MonadLaws.hs
return x >>= f            ===   f x

이걸 표현하는 다른 방법은 (>>=)로 곧바로 꺼낼 거라면 굳이 return으로 순수한 값을 싸맬 필요가 없다는 겁니다. return으로 감싸고 같은 함수에서 몇 줄 후에 (>>=)로 꺼내는 건 사실 모나드에 처음인 하스켈 프로그래머가 자주 저지르는 스타일 에러입니다. 아래는 do 표기법으로 작성한 같은 법칙입니다.

-- file: ch14/MonadLaws.hs
do y <- return x
   f y                    ===   f x

이 규칙은 우리 코딩 스타일에 실용적인 영향을 줍니다. 우리는 필요없는 코드를 짜고 싶지 않고, 이 법칙은 우리가 간결한 코드가 더 장황한 버전하고 동작이 동일할 거라고 짐작해도 좋도록 합니다.

둘째 모나드 법칙은 return(>>=)우항등원 이라는 것입니다.

-- file: ch14/MonadLaws.hs
m >>= return              ===   m

이 법칙도 (특히 절차 지향 언어에서 온 경우) 실제 프로그램에서 스타일에 영향을 줍니다. 블록의 마지막 액션이 제대로 된 결과를 반환했다면, return을 사용할 필요가 없습니다. 이 법칙을 do 표기법으로 봅시다.

-- file: ch14/MonadLaws.hs
do y <- m
   return y               ===   m

다시 한번, 모나드가 이 법칙을 지킨다고 가정하면, 더 긴 코드와 같은 효과를 가진다는 사실을 알고 더 짧은 코드로 짤 수 있습니다.

마지막 법칙은 결합 법칙과 관계가 있습니다.

-- file: ch14/MonadLaws.hs
m >>= (\x -> f x >>= g)   ===   (m >>= f) >>= g

이 법칙은 약간 이해하기 어려울 수 있기 때문에, 양쪽 식의 괄호 안을 봅시다. 우리는 왼쪽 식을 다음과 같이 재작성할 수 있습니다.

-- file: ch14/MonadLaws.hs
m >>= s
  where s x = f x >>= g

오른쪽 식도, 마찬가지로 재배열 할 수 있습니다.

-- file: ch14/MonadLaws.hs
t >>= g
  where t = m >>= f

이제 우리는 다음 두 식이 같다고 말할 수 있습니다.

-- file: ch14/MonadLaws.hs
m >>= s                   ===   t >>= g

이게 의미하는 것은 액션을 더 작은 부분으로 나눴을 때, 우리가 순서만 액션 순서만 지킨다면 어느 부분 액션을 새 액션으로 만들지는 중요하지 않다는 겁니다. 우리가 액션 세 개를 연쇄하고 있다면, 앞 두 개 액션이나, 뒤 두 개 액션 중 한 쪽을 먼저 치환하는 것 어느 것이든 가능합니다.

이 더 복잡한 법칙은 실용성이 있습니다. “메서드 추출”은 코드 뭉치를 잘라내 함수로 바꾼 다음, 잘라낸 곳에서 그 함수를 호출하는 기법을 칭하는 깜찍한 소프트웨어 리팩토링 용어입니다. 셋째 법칙으로 모나딕 하스켈 코드에 메서드 추출을 쓸 수 있단 걸 알 수 있습니다.

우린 각각의 모나드 법칙이 어떻게 더 나은 모나딕 코드를 짜는 데 필요한 통찰을 주는지 보았습니다. 처음 두 법칙은 return의 남용을 어떻게 피하는지 보여줬습니다. 셋째 규칙은 복잡한 액션을 여러 단순한 액션으로 안전하게 리팩토링 할 수 있다는 걸 알려줬습니다. 이제 제대로 된 모나드를 사용할 때 “내가 의도한 동작”을 할 거라는 직관이 깨지지 않을 거라는 지식을 가지고 자세한 내용은 신경 끌 수 있습니다.

그런데, 하스켈 컴파일러는 모나드가 실제 모나드 법칙을 따르는지는 보장하지 않습니다. 작성한 코드가 모나드 법칙을 만족하도록—혹은 가능하면 만족하는 걸 증명하도록— 하는 건 모나드 제작자의 책임입니다.

저작자 표시 비영리 동일 조건 변경 허락
신고

Real World Haskell 9장 번역Real World Haskell 9장 번역

Posted at 2015.01.16 15:10 | Posted in 지식저장소/읽은 책 요약

어쩌다 번역해 봤는데, 진 빠진다. 더 안할 듯. 원본 링크

9장. 입출력 사례 예제: 파일 시스템 검색 라이브러리

"내가 파일을 가지고 있지만, 어디에 있는 진 모르겠다"는 문제는 컴퓨터가 계층 파일 구조를 도입한 때 만큼이나 오랫동안 널리 있었습니다. 1974년 유닉스 5번째 판부터 find라는 명령어를 도입했고, find는 필수적인 명령어로 자리잡았습니다. 오랜 시간 다듬은 현재의 최신 기술로 현대 운영 체제는 발전한 문서 색인과 검색 능력을 가지게 됩니다.

프로그래머의 도구상자엔 아직 find같은 기능을 위한 중요한 장소가 있습니다. 이번 장에서, 우리는 하스켈 만으로 find의 여러 기능을 제공하는 라이브러리를 만들 것입니다. 이 라이브러리를 다양한 방법으로 만들어 보면서 제각기 어느 정도의 강력함을 가지는 지 알아볼 것입니다.

find 명령어

만약 유닉스 계열 운영 체제를 써본 적이 없거나, 열렬한 쉘 사용자가 아니라면, find를 들어본 적조차 없을 수도 있습니다. find는 디렉토리 목록을 주면 각각을 재귀적으로 검색해 표현식에 맞는 모든 항목을 출력해 주는 명령어입니다.

각각의 표현식은 "이 glob 패턴에 맞는 이름", "보통 파일", "이 날짜 이후에 수정한 파일" 등의 형식을 가지고 있습니다. 이 표현식들을 "and"나 "or" 연산자로 조합해 더 복잡한 표현식으로 조합할 수도 있습니다.

가벼운 시작: 디렉토리 재귀적으로 열거하기

라이브러리를 설계해보기 전에, 작은 문제들부터 풀어봅시다. 우리의 첫번째 문제는 디렉토리와 하위 디렉토리의 내용물을 재귀적으로 나열하는 것입니다.

-- file: ch09/RecursiveContents.hs
module RecursiveContents (getRecursiveContents) where

import Control.Monad (forM)
import System.Directory (doesDirectoryExist, getDirectoryContents)
import System.FilePath ((</>))

getRecursiveContents :: FilePath -> IO [FilePath]

getRecursiveContents topdir = do
  names <- getDirectoryContents topdir
  let properNames = filter (`notElem` [".", ".."]) names
  paths <- forM properNames $ \name -> do
    let path = topdir </> name
    isDirectory <- doesDirectoryExist path
    if isDirectory
      then getRecursiveContents path
      else return [path]
  return (concat paths)

filter 식은 디렉토리 내용에서 각각 현재 디렉토리와 부모 디렉토리를 의미하는 특별한 이름인 .과 ..을 제외해줍니다. 우리가 이걸 빼 놓는 걸 깜박한다면, 영원히 재귀하게 될 겁니다.

우리는 mapM의 인자가 뒤바뀐 것과 같은 forM을 이전 장에서 본 적이 있습니다.

ghci> :m +Control.Monad
ghci> :type mapM
mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
ghci> :type forM
forM :: (Monad m) => [a] -> (a -> m b) -> m [b]

반복문(이하 루프) 본체는 현재 디렉토리 항목이 디렉토리인지 아닌지 확인합니다. 만약 디렉토리라면, 그 디렉토리도 열거하기 위해 getRecursiveContents를 재귀적으로 호출합니다. 아니라면, 현재 항목의 이름을 담은 원소 하나짜리 리스트를 반환합니다. (return이 하스켈에서는 다른 의미를 가지는 걸 잊지 맙시다: return은 값을 모나드 타입 생성자로 감싸는 역할을 수행합니다.)

isDirectory변수를 사용했다는 점도 중요합니다. 파이썬같은 절차 지향 언어에선 일반적으로 if os.path.isdir(path)와 같이 작성합니다. 하지만 doesDirectoryExist 함수는 액션입니다; 이 함수의 리턴 타입은 IO Bool이지, Bool이 아닙니다. if 표현식이 Bool 타입 표현식을 필요로 하기 때문에 우리는 액션의 결과를 IO 타입 안에서 꺼내 Bool을 얻기 위해 <-를 써야 합니다. 그러면 이제 꺼낸 Boolif 표현식 안에 쓸 수 있게 됩니다.

루프 본체가 이름 리스트를 반환하므로 forM의 결과는 IO [[FilePath]]가 됩니다. 이걸 단일 리스트로 만들기 위해 concat을 쓸 수 있습니다.

익명 함수와 이름 있는 함수 복습

“익명 함수 (람다)”장에서, 익명 함수를 쓰면 안 되는 이유를 몇 가지 살펴봤습니다. 또한 익명 함수를 루프 본체로 써 봤습니다. 이건 하스켈에서 익명 함수의 가장 흔한 사용 예 중 하나입니다.

우리는 이미 forMmapM이 함수를 인자로 받는 것을 타입을 통해 살펴봤습니다. 대부분의 루프 본체는 프로그램에서 한 번만 나타나는 코드 블록입니다. 루프 본체를 딱 한 군데에서만 쓸 것 같다면, 그것에 이름을 줄 필요가 있을까요?

물론 때때로 정확히 같은 코드를 여러 다른 루프에 써야하는 일도 생깁니다. 이 경우에는 같은 익명 함수를 잘라내 붙여넣는 것보다, 이미 있는 익명 함수에 이름을 붙이는 것이 더 현실적입니다.

왜 mapM과 forM을 둘 다 제공하나요?

완전히 같지만 인자의 순서만 다른 두 함수가 있는 것이 좀 이상해 보일 수 있습니다. 하지만 mapM과 forM은 각각 다른 상황에서 편리합니다.

익명 함수를 루프 본체로 사용하는 위의 예를 생각해봅시다. 만약 우리가 forM대신 mapM을 사용한다면, properNames 변수를 루프 본체 뒤에 붙여야 할 것입니다. 또한 파싱이 제대로 되도록 익명 함수를 괄호로 감싸거나 한번만 쓸 이름을 붙여야 할 것입니다. 한 번 시도해보세요: 위의 코드를 복사하고, forMmapM으로 바꾸고, 코드 가독성에 어떤 영향을 주는지 확인해보세오.

반대로, 만약 루프 본체가 이미 이름을 가진 함수라면, 그리고 루프할 리스트가 복잡한 계산으로 표현된다면, 이건 mapM을 사용하면 되는 대표적인 경우가 될 것입니다.

여기서 mapM을 쓸지 forM을 쓸지 결정하는 스타일 규칙은 가장 간결한 코드가 되는 것을 고르는 것입니다. 루프 본체와 루프 데이터 표현식 계산이 둘 다 짧다면 둘 중 무엇을 써도 좋습니다. 만약 루프가 짧고, 데이터가 길다면 mapM을 쓰세요. 루프가 길고, 데이터가 짧다면, forM을 쓰세요. 둘 다 길다면, let이나 where로 하나를 짧게 만들면 됩니다. 약간의 연습으로 각각의 상황에서 어떤 접근 방법이 최선인지 쉽게 알 수 있을 것입니다.

순진한 탐색 함수

우리가 만든 getRecursiveContents 함수는 고민 없이 파일 검색기를 만드는 데 쓸 수 있습니다.

-- file: ch09/SimpleFinder.hs
import RecursiveContents (getRecursiveContents)

simpleFind :: (FilePath -> Bool) -> FilePath -> IO [FilePath]

simpleFind p path = do
  names <- getRecursiveContents path
  return (filter p names)

이 함수는 getRecursiveContents의 결과를 걸러낼 때 쓸 조건자predicate를 받습니다. 조건자로 완전한 경로가 전달되는데, 그래서 "확장자가 .c인 모든 파일을 찾아라"같은 일반적인 작업을 어떻게 시킬 수 있을까요?

System.FilePath 모듈은 파일 이름을 다루는 유용한 함수들을 많이 가지고 있습니다. 이번엔 우리는 takeExtension을 사용할 겁니다.

ghci> :m +System.FilePath
ghci> :type takeExtension
takeExtension :: FilePath -> String
ghci> takeExtension "foo/bar.c"
Loading package filepath-1.1.0.0 ... linking ... done.
".c"
ghci> takeExtension "quux"
""

이것으로 문제는 경로를 받고, 확장자를 추출해, ".c"하고 비교하는 함수를 만드는 것으로 간단해졌습니다.

ghci> :load SimpleFinder
[1 of 2] Compiling RecursiveContents ( RecursiveContents.hs, interpreted )
[2 of 2] Compiling Main             ( SimpleFinder.hs, interpreted )
Ok, modules loaded: RecursiveContents, Main.
ghci> :type simpleFind (\p -> takeExtension p == ".c")
simpleFind (\p -> takeExtension p == ".c") :: FilePath -> IO [FilePath]

simpleFind가 동작하긴 하지만, 몇가지 명백한 문제를 가지고 있습니다. 첫째로 조건자가 그다지 명확하지 못합니다. 조건자는 디렉토리 항목을 살펴볼 뿐, 그 항목이 파일인지 디렉토리인지는 구분하지 못 합니다. 즉 지금의 simpleFind.c로 끝나는 디렉토리도 결과에 포함한다는 얘깁니다.

둘째로 simpleFind는 우리에게 파일 시스템을 어떻게 순회할 지 전혀 제어권을 주지 않습니다. 이게 왜 중요한지 알기 위해, SVN으로 관리 중인 소스 파일들을 찾는 문제를 생각해봅시다. SVN은 .svn 디렉토리를 SVN이 관리하는 디렉토리마다 만들고 관리합니다. 각각의 .svn 디렉토리는 많은 파일과 하위 디렉토리를 가지고 있지만 우리의 관심사가 아닙니다. .svn을 포함한 경로를 제외하는 것으로 이 디렉토리 순회를 회피해 훨씬 효율을 올릴 수 있습니다. 예를 들어 우리가 45,000개의 파일 중 30,000개의 파일을 1,200개의 여러 .svn디렉토리에 저장한 SVN 폴더를 가지고 있다면 1,200개의 디렉토리 순회를 피하는 것이 30,000개의 파일을 제외하는 것보다 훨씬 저렴할 것입니다.

마지막으로, simpleFind는 엄격합니다. 왜냐하면 IO 모나드 안에서 실행하는 액션의 연쇄로 이루어졌기 때문입니다. 만약 우리가 백만 개의 파일을 순회한다면 꽤 긴 지연을 겪은 뒤 한꺼번에 백만 개의 이름을 받을 것입니다. 이것은 리소스 사용과 반응성 면에서 둘 다 안 좋습니다. 우리는 결과가 나오는 대로 처리하는 게으른 스트림을 더 선호할 겁니다.

이어지는 단락에서, 우리는 각각의 문제를 해결할 것입니다.

조건자: 순수함을 유지하면서, 약했지만 강력하게

우리 조건자는 파일 이름만 볼 수 있었습니다. 이건 우리가 원하는 다양한 행동을 제한합니다: 예를 들어, 주어진 크기보다 더 큰 파일만 열거하고 싶다면 어떨까요?

IO를 사용하자고 쉽게 반응할 수도 있습니다: 조건자의 타입을 FilePath -> Bool대신, FilePath -> IO Bool로 바꾸면 안 될까요? 이건 임의의 I/O작업을 조건자에서 할 수 있게 만들 겁니다. 매력적으로 보이지만, 이건 잠재적으로 문제를 가지고 있습니다: 조건자가 부수 효과를 가질 수 있다는 문제. IO 리턴 타입을 가진 함수는 어떤 부수 효과라도 일으킬 수 있습니다.

타입 시스템을 더 예측 가능하고 덜 장황한 코드를 짜는 데 활용하기 위해: "IO"를 사용하지 않는 것으로 조건자를 순수하게 유지할 것입니다. 이것은 조건자가 어떤 보기 싫은 부수효과도 가지지 않도록 합니다. 또한 위험해지지 않으면서 우리가 원하는 표현력을 얻기 위해 조건자에 좀 더 많은 정보를 제공할 것입니다.

하스켈의 이식성있는 System.Directory 모듈은 제한적이긴 하지만 유용한 메타데이터들을 제공해줍니다.

ghci> :m +System.Directory
  • doesFileExist와 doesDirectoryExist를 디렉토리 안 항목이 파일인지 디렉토리인지 확인하는 데 쓸 수 있습니다. 최근에 널리 쓰이게 된 지명 파이프나 하드 링크, 심볼릭 링크같은 다른 파일 타입들은 아직 이식성을 가지고 조사할 수 있는 방법이 없습니다.

    ghci> :type doesFileExist
    doesFileExist :: FilePath -> IO Bool
    ghci> doesFileExist "."
    Loading package old-locale-1.0.0.0 ... linking ... done.
    Loading package old-time-1.0.0.0 ... linking ... done.
    Loading package directory-1.0.0.0 ... linking ... done.
    False
    ghci> :type doesDirectoryExist
    doesDirectoryExist :: FilePath -> IO Bool
    ghci> doesDirectoryExist "."
    True
  • The getPermissions 함수로 어떤 작업이 해당 파일이나 디렉토리에 가능한지 확인할 수 있습니다.

    ghci> :type getPermissions
    getPermissions :: FilePath -> IO Permissions
    ghci> :info Permissions
    data Permissions
      = Permissions {readable :: Bool,
                     writable :: Bool,
                     executable :: Bool,
                     searchable :: Bool}
            -- Defined in System.Directory
    instance Eq Permissions -- Defined in System.Directory
    instance Ord Permissions -- Defined in System.Directory
    instance Read Permissions -- Defined in System.Directory
    instance Show Permissions -- Defined in System.Directory
    ghci> getPermissions "."
    Permissions {readable = True, writable = True, executable = False, searchable = True}
    ghci> :type searchable
    searchable :: Permissions -> Bool
    ghci> searchable it
    True

    (만약 ghci의 특별한 변수인 it이 떠오르지 않는다면 “타입으로의 첫걸음”을 돌아보세요.) 우리가 내용물을 열거할 권한이 있다면 그 디렉토리는 searchable한 것입니다. 파일은 절대 searchable할 수 없습니다.

  • 마지막으로, getModificationTime은 항목이 마지막으로 수정된 때를 알려줍니다.

    ghci> :type getModificationTime
    getModificationTime :: FilePath -> IO System.Time.ClockTime
    ghci> getModificationTime "."
    Mon Aug 18 12:08:24 CDT 2008

만약 우리가 이식성 있고 표준을 지키는 하스켈 코드를 고집한다면 이 함수들까지만 우리가 맘대로 쓸 수 있습니다. (파일 크기 또한 약간의 꼼수로 구할 수 있습니다. 아래를 보세요) 또한 이 함수들은 우리가 너무 방대한 예를 들 필요가 없이 배우고자 하는 원리를 설명하기에 충분합니다. 만약 더 요구조건이 많은 코드를 짜야 한다면, System.PosixSystem.Win32모듈이 두 주류 플랫폼에 대한 더 자세한 메타데이터를 제공해 줄 것입니다. 또한 Hackage에는 윈도에서 유닉스 계열의 API를 제공하는 unix-compat 패키지도 있습니다.

새롭고 더 강력한 조건자에는 얼마나 많은 데이터 조각이 필요할까요? 해당 항목의 Permissions를 보는 것으로 그것이 파일인지 디렉토리인지 알 수 있기 때문에, 우리는 doesFileExistdoesDirectoryExist의 결과를 참고할 필요가 없습니다. 그 결과 더 강력한 조건자가 필요로 하는 네 종류의 데이터를 알게 됩니다.

-- file: ch09/BetterPredicate.hs
import Control.Monad (filterM)
import System.Directory (Permissions(..), getModificationTime, getPermissions)
import System.Time (ClockTime(..))
import System.FilePath (takeExtension)
import Control.Exception (bracket, handle)
import System.IO (IOMode(..), hClose, hFileSize, openFile)

-- the function we wrote earlier
import RecursiveContents (getRecursiveContents)

type Predicate =  FilePath      -- path to directory entry
               -> Permissions   -- permissions
               -> Maybe Integer -- file size (Nothing if not file)
               -> ClockTime     -- last modified
               -> Bool

Predicate는 단지 4개의 인자를 가진 함수의 타입 동의어 입니다. 이것은 타이핑 작업을 줄이고 화면 공간을 절약해 우리를 도와줄 것입니다.

조건자의 리턴 타입이 IO Bool이 아니라 Bool이라는 데 주목해주세요: 조건자는 순수하고, 어떤 입출력 작업도 하지 않습니다. 이 타입으로 더 표현력 있는 조건자 함수를 잘 다듬습니다.

-- file: ch09/BetterPredicate.hs
-- soon to be defined
getFileSize :: FilePath -> IO (Maybe Integer)

betterFind :: Predicate -> FilePath -> IO [FilePath]

betterFind p path = getRecursiveContents path >>= filterM check
    where check name = do
            perms <- getPermissions name
            size <- getFileSize name
            modified <- getModificationTime name
            return (p name perms size modified)

코드를 따라가 봅시다. getFileSize는 곧 자세히 설명하므로, 지금은 넘어갑니다.

우리는 조건자 p를 호출하기 위해 filter를 사용할 수 없습니다. 왜냐하면 p의 순수성이 우리가 필요로하는 메타데이터를 얻기 위한 입출력 작업을 할 수 없게 만들기 때문입니다.

때문에 낯선 함수인 filterM을 도입합니다. 이건 기존의 filter 함수와 비슷하지만, 이 경우 filterM은 조건자가 입출력 작업을 할 수 있도록 조건자를 IO 모나드 안에서 평가합니다.

ghci> :m +Control.Monad
ghci> :type filterM
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]

check조건자는 순수한 조건자 p를 감싸는 입출력 가능한 래퍼wrapper입니다.check는 모든 "더러운" 입출력 작업을 p를 위해서 해주고, 그 결과 우리는 p가 원치 않는 부수효과를 낼 수 없도록 합니다. 메타데이터를 모든 다음, checkp를 호출해 return으로 p의 결과를 IO로 감쌉니다.

안전하게 파일 크기 조절하기

비록 System.Directory로 파일이 얼마나 큰지 알 수 없다지만, 유사하게 이식성 있는 System.IO 모듈을 사용해 구할 수 있습니다. 이 모듈은 hFileSize라는 연 파일의 크기를 바이트로 알려주는 함수를 가지고 있습니다. 아래는 그것을 감싸는 간단한 함수입니다.

-- file: ch09/BetterPredicate.hs
simpleFileSize :: FilePath -> IO Integer

simpleFileSize path = do
  h <- openFile path ReadMode
  size <- hFileSize h
  hClose h
  return size

이 함수는 동작하긴 하지만, 우리가 사용하기엔 아직 적절하지 않습니다. betterFind에서 우리는 getFileSize를 무차별적으로 모든 디렉토리 항목에 사용하고 있습니다; 만약 항목이 일반 파일이 아니면 이 함수는 Nothing을 반환하고, 크기는 Just로 감싸야 합니다. 그러지 않으면 함수는 일반 파일이 아니거나 (아마도 권한이 부족한 상황에서) 열 수 없을 때 예외를 던지고 감싸지 않은 크기를 반환할 겁니다.

아래는 더 안전한 버전의 함수입니다.

-- file: ch09/BetterPredicate.hs
saferFileSize :: FilePath -> IO (Maybe Integer)

saferFileSize path = handle (\_ -> return Nothing) $ do
  h <- openFile path ReadMode
  size <- hFileSize h
  hClose h
  return (Just size)

handle구문을 제외한 함수 본체는 거의 동일합니다.

위에 나온 예외 핸들러는 받은 예외를 무시하고 Nothing을 반환합니다. 뒤따라오는 함수 본체에 생긴 유일한 변화는 파일 크기를 Just로 감싼 것입니다.

saferFileSize 함수는 이제 제대로 된 타입 시그니처를 가지고, 더 이상 예외를 던지지 않을 것입니다. 하지만 아직 완전히 잘 동작하지는 않습니다. openFile은 성공하지만 hFileSize에서 예외가 생기는 디렉토리 항목이 있습니다. 이건 지명 파이프 같은 항목에서 발생할 수 있습니다. 이러한 예외는 handle에 의해 잡히지만, hClose는 일어나지 않을 것입니다.

하스켈 구현은 핸들을 더 이상 사용하지 않는 상황을 감지하면 자동으로 핸들을 닫습니다. 이것은 가비지 컬렉터가 실행되기 전까진 일어나지 않을 것이고, 다음 가비지 컬렉션이 실행될 때까지의 지연은 예측할 수 없습니다.

파일 핸들은 부족할 수 있는 리소스입니다. 밑단인 운영 체제에서 이 제한을 강제합니다. 예를 들어 리눅스에선, 한 프로세스는 기본으로 1024개 까지만 파일 핸들을 동시에 열 수 있습니다.

saferFileSize를 호출하는 betterFind를 사용하는 프로그램이 betterFind가 쓰레기 파일 핸들이 닫히기 전에 파일 핸들을 고갈내 프로그램을 크래시 낸다는 상상은 어렵지 않게 할 수 있습니다.

이건 특히 치명적이고 알아차리기 힘든 종류의 버그입니다: 이것은 합쳐지면 상당히 추적을 어렵게 하는 여러 면을 가지고 있습니다. 이 버그는 betterFind가 프로세스가 열 수 있는 파일 핸들 제한을 넘는 갯수의 비일반 파일을 맞닥뜨려야 하고 쌓인 쓰레기 파일 핸들이 닫히기 전에 다른 파일을 열려고 하는 호출자에게 반환되어야만 발생할 것입니다.

설상가상으로, 프로그램에서 더 이상 접근할 수 없는 데이터와 가비지 컬렉션되지 않은 데이터 때문에 발생하는 뒤따르는 에러가 있습니다. 이런 버그는 프로그램 구조와 파일시스템 내용, 프로그램 흐름이 가비지 컬렉터 실행과 얼마나 가까운지에 따라 갈립니다.

이런 종류의 문제는 개발 도중엔 간과하기 쉽지만, 나중에 현장에서 일어날 땐 (이런 이상한 문제가 항상 일어나듯이), 진단하기는 매우 힘들 것입니다.

다행히도, 우리는 함수를 더 짧게 만들면서도 이런 종류의 에러를 매우 쉽게 피할 수 있습니다.

획득-사용-해제 사이클

우리는 openFile이 성공하면 반드시 hClose를 호출해야 합니다. Control.Exception 모듈은 정확히 이 용도를 위한 bracket 함수를 제공합니다.

ghci> :type bracket
bracket :: IO a -> (a -> IO b) -> (a -> IO c) -> IO c

bracket 함수는 세 액션을 인자로 받습니다. 첫째 액션은 자원을 획득합니다. 둘째 액션은 자원을 해제합니다. 셋째 액션은 자원을 획득한 사이에 실행되는 액션입니다; 이걸 "사용" 액션이라고 부릅시다. 만약 "획득" 액션이 성공하면 "해제" 액션은 항상 호출될 것입니다. 이건 자원이 항상 해제될 것을 보장합니다. "사용"과 "해제" 액션에 전달되는 자원은 "획득" 액션에서 얻은 자원입니다.

만약 예외가 "사용" 액션 실행 중에 일어났다면, bracket은 “해제” 액션을 호출하고 예외를 다시 던집니다. 만약 “사용” 액션이 성공하면, bracket은 “해제” 액션을 호출하고, “사용” 액션에서 반환한 값을 반환합니다.

우리는 이제 완전히 안전한 함수를 작성할 수 있습니다: 이 함수는 예외를 던지지 않고, 프로그램 어딘가에서 이상한 실패를 일으킬 수 있는 쓰레기 파일 핸들을 축적하지도 않을 것입니다.

-- file: ch09/BetterPredicate.hs
getFileSize path = handle (\_ -> return Nothing) $
  bracket (openFile path ReadMode) hClose $ \h -> do
    size <- hFileSize h
    return (Just size)

bracket의 인자를 자세히 보세요. 첫째 인자는 파일을 열고, 연 파일 핸들을 반환합니다. 둘째 인자는 파일 핸들을 닫습니다. 셋째 인자는 단순히 파일 핸들에 hFileSize 를 호출하고 그 결과를 Just로 강쌉니다.

우리는 이 함수를 제대로 동작시키기 위해 brackethandle을 둘 다 써야 합니다. 전자는 우리가 쓰레기 파일 핸들을 축적하지 않는 것을 보장하고, 후자는 예외를 없애는 것을 보장합니다.

연습문제

  1. brackethandle의 순서가 중요할까요? 그 이유는?

조건자를 위한 도메인 언어Domain specific language

조건자를 만들기 위한 첫발을 내디뎌봅시다. 우리가 만들 조건자는 128KB가 넘는 C++ 소스 파일을 찾아낼 겁니다.

-- file: ch09/BetterPredicate.hs
myTest path _ (Just size) _ =
    takeExtension path == ".cpp" && size > 131072
myTest _ _ _ _ = False

이건 딱히 즐겁지 않습니다. 이 조건자는 4개의 인자를 받고, 항상 그 중 2개는 무시하며, 두 개의 등식을 을 정의하는 걸 요구합니다. 물론 개량의 여지가 있습니다. 우리가 더 간결한 조건자를 작성하는 걸 도와줄 약간의 코드를 만들어 봅시다.

때때로, 이러한 종류의 라이브러리는 임베디드 도메인 언어라고 부릅니다: 프로그래밍 언어의 내재된 기능만으로 (그래서 임베디드) 우리가 더 좁은 문제를 특별히 우아하게 해결하는 코드를 짭니다. (그래서 영역 한정)

첫 단계는 인자 중 하나를 반환하는 함수를 짜는 것입니다. 아래 함수는 Predicate에 넘긴 인자 중 경로를 추출합니다.

-- file: ch09/BetterPredicate.hs
pathP path _ _ _ = path

만약 우리가 타입 시그니처를 제공하지 않는다면, 하스켈 구현은 이 함수를 매우 일반화한 타입으로 추측할 겁니다. 이건 나중에 해석하기 힘든 에러 메시지를 초래할 수 있으므로, pathP에 타입을 줘 봅시다.

-- file: ch09/BetterPredicate.hs
type InfoP a =  FilePath        -- path to directory entry
             -> Permissions     -- permissions
             -> Maybe Integer   -- file size (Nothing if not file)
             -> ClockTime       -- last modified
             -> a

pathP :: InfoP FilePath

이제 다른 비슷한 구조를 가질 함수들을 정의할 때 간편히 사용할 수 있는 타입 동의어를 만들었습니다. 이 타입 동의어는 타입 인자를 받으므로 우리는 각기 다른 결과 타입을 지정할 수 있습니다.

-- file: ch09/BetterPredicate.hs
sizeP :: InfoP Integer
sizeP _ _ (Just size) _ = size
sizeP _ _ Nothing     _ = -1

(여기서 살짝 찝찝하지만, 파일이 아니거나 열 수 없는 파일에 대해선 -1을 반환합니다.)

사실, 우리가 이 장이 시작할 때 정의한 Predicate 타입은 얼핏 보기에 InfoP Bool과 같습니다. (그러므로 우리는 합법적으로 Predicate 타입을 지울 수 있습니다.)

pathPsizeP의 용도는 뭘까요? 약간의 접착제와 함께, 우리는 이걸 조건자 안에서 사용할 수 있습니다 (각각의 이름의 P 접미사는 “조건자”라는 걸 나타내기 위함입니다). 여기서부터 재밌어지기 시작합니다.

-- file: ch09/BetterPredicate.hs
equalP :: (Eq a) => InfoP a -> a -> InfoP Bool
equalP f k = \w x y z -> f w x y z == k

equalP의 타입 시그니처는 관심을 기울일 만 합니다. pathPsizeP 둘 다와 호환되는 InfoP a를 받습니다. 이건 a를 받습니다. 그리고 이미 Predicate와 타입 동의어인 걸 확인한 InfoP Bool을 반환합니다. 다시 말하자면, equalP는 조건자를 만듭니다.

equalP 함수는 받은 인자를 f에 넘겨 그 결과를 k와 비교하는, 조건자로 인정되는 익명 함수를 반환하는 것으로 동작합니다.

equalP 등식은 우리가 이걸 두 인자를 받는 함수라고 간주하는 부분을 강조합니다. 하스켈은 모든 함수를 커리하기 때문에, equalP를 꼭 이런 방식으로 작성할 필요는 없습니다. 익명 함수를 생략하고 커리로 대신해서, 동일한 함수를 재작성할 수 있습니다.

-- file: ch09/BetterPredicate.hs
equalP' :: (Eq a) => InfoP a -> a -> InfoP Bool
equalP' f k w x y z = f w x y z == k

탐구를 시작하기 전에, 우리 모듈을 ghci에 로딩해봅시다.

ghci> :load BetterPredicate
[1 of 2] Compiling RecursiveContents ( RecursiveContents.hs, interpreted )
[2 of 2] Compiling Main             ( BetterPredicate.hs, interpreted )
Ok, modules loaded: RecursiveContents, Main.

이 함수로 만든 간단한 조건자가 잘 동작하는지 확인해 봅시다.

ghci> :type betterFind (sizeP `equalP` 1024)
betterFind (sizeP `equalP` 1024) :: FilePath -> IO [FilePath]

실제로 betterFind를 호출한 게 아니라, 그저 표현식의 타입만 확인한 것입니다. 이제 우리는 정확히 특정 크기의 파일을 모두 열거하는 더 표현력있는 방법을 가지게 되었습니다. 이 성공은 계속할 자신감을 줍니다.

리프팅으로 보일러플레이트 피하기

equalP 말고도, 우리는 다른 이항 함수들을 만들고 싶습니다. 쓸데없이 장황해질 것 같기 때문에, 각각을 완벽하게 정의하지 않는 편을 선호할 것입니다.

이 문제를 다루기 위해, 하스켈의 강력한 추상화를 이용해봅시다. equalP의 정의를 취하고(==)을 직접 호출하는 대신 우리가 원하는 이항 연산을 또 다른 인자로 넘겨줄 것입니다.

-- file: ch09/BetterPredicate.hs
liftP :: (a -> b -> c) -> InfoP a -> b -> InfoP c
liftP q f k w x y z = f w x y z `q` k

greaterP, lesserP :: (Ord a) => InfoP a -> a -> InfoP Bool
greaterP = liftP (>)
lesserP = liftP (<)

greaterP같은, (>)같은 함수를 받아서 다른 문맥에서 동작하는 다른 함수로 변환하는 행위를 그 문맥으로 리프팅한다고 말합니다. 이건 lift가 함수 이름에 붙는 이유를 설명합니다. 리프팅은 우리가 코드를 재활용하고 보일러플레이트를 줄이도록 도와줍니다. 우리는 여러 모양새로 이 책의 나머지 부분에서 리프팅을 많이 사용할 것입니다.

우리가 함수를 리프트할 때, 원래 함수와 새 함수를 각각 리프트 안 된 함수unlifted와 리프트된 함수lifted라고 부릅니다.

어쨌든, liftP의 인자로써 q(리프트할 함수)의 위치는 다분히 계획적입니다. 이것은 우리가 greaterPlesserP를 간결하게 정의하는 걸 가능하게 만듭니다. API를 설계할 때 이런 부분 적용은 “최선”의 인자 순서를 찾아내는 걸 하스켈에서 다른 언어보다 더 중요하게 만듭니다. 부분 적용이 없는 언어에서는, 인자 순서는 단지 취향과 관습의 문지입니다. 하지만 하스켈에서 인자 위치를 부적절하게 정하는 것은, 부분 적용이 주는 간결해질 수 있는 기회를 잃는 게 됩니다.

컴비네이터로 그런 간결함을 일부 회복할 수도 있습니다. 예를 들어, forMControl.Monad 모듈에 2007년까지 없었습니다. 그 이전에는, 사람들은 flip mapM을 대신 사용했습니다.

ghci> :m +Control.Monad
ghci> :t mapM
mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
ghci> :t forM
forM :: (Monad m) => [a] -> (a -> m b) -> m [b]
ghci> :t flip mapM
flip mapM :: (Monad m) => [a] -> (a -> m b) -> m [b]

조건자 이어붙이기

조건자를 합성하고 싶다면, 물론 아래의 명백한 수작업을 할 수 있습니다.

-- file: ch09/BetterPredicate.hs
simpleAndP :: InfoP Bool -> InfoP Bool -> InfoP Bool
simpleAndP f g w x y z = f w x y z && g w x y z

이제 우리는 리프팅을 알고 있으니, 위에 있는 불리언 연산자를 리프팅해서 우리가 작성해야 하는 코드의 양을 줄이는 것이 더 자연스러워집니다.

-- file: ch09/BetterPredicate.hs
liftP2 :: (a -> b -> c) -> InfoP a -> InfoP b -> InfoP c
liftP2 q f g w x y z = f w x y z `q` g w x y z

andP = liftP2 (&&)
orP = liftP2 (||)

liftP2가 이전에 있었던 liftP와 비슷하다는 점에 주목하세요. 사실, 이게 더 일반적인데, 왜냐하면 liftPliftP2로 작성할 수 있기 때문입니다.

-- file: ch09/BetterPredicate.hs
constP :: a -> InfoP a
constP k _ _ _ _ = k

liftP' q f k w x y z = f w x y z `q` constP k w x y z

컴비네이터

하스켈에서, 다른 함수를 인자로 받아 새 함수를 반환하는 함수를 컴비네이터라고 부릅니다.

이제 우리는 여러 도우미 함수를 준비했으니, 이전에 정의했던 myTest 함수로 돌아가 봅시다.

-- file: ch09/BetterPredicate.hs
myTest path _ (Just size) _ =
    takeExtension path == ".cpp" && size > 131072
myTest _ _ _ _ = False

우리가 만든 새 컴비네이터를 사용하면 이 함수가 어떻게 보일까요?

-- file: ch09/BetterPredicate.hs
liftPath :: (FilePath -> a) -> InfoP a
liftPath f w _ _ _ = f w

myTest2 = (liftPath takeExtension `equalP` ".cpp") `andP`
          (sizeP `greaterP` 131072)

마지막 컴비네이터로 liftPath를 추가했는데, 파일 이름을 조작하는 건 흔한 작업이기 때문입니다.

새 연산자 정의하고 사용하기

우리의 도메인 언어를 새 중위 연산자를 정의해 더 심화시킬 수 있습니다.

-- file: ch09/BetterPredicate.hs
(==?) = equalP
(&&?) = andP
(>?) = greaterP

myTest3 = (liftPath takeExtension ==? ".cpp") &&? (sizeP >? 131072)

대응되는 리프트 안 된 연산자와 시각적으로 일관되기 위해 (==?)같은 이름을 골랐습니다.

myText3 정의의 괄호는 필수인데, 그 이유는 우리가 아직 하스켈에게 새 연산자에 대한 우선순위나 결합 방향을 지정하지 않았기 때문입니다. 하스켈은 이런 fixity 지정이 없는 연산자들을 반드시 infixl 9로 취급한다고 명시했습니다. 즉, 이 연산자들은 왼쪽에서 오른쪽으로, 가장 높은 우선순위로 평가된다는 뜻입니다. 만약 우리가 괄호를 생략한다면, 표현식은 끔찍하게 잘못된 (((liftPath takeExtension) ==? ".cpp") &&? sizeP) >? 131072로 해석될 겁니다.

우리는 새 연산자의 fixity 선언을 넣어 대응할 수 있습니다. 첫째 단계는 리프트되지 않은 연산자의 fixity를 우리가 흉내낼 수 있도록 확인하는 것입니다.

ghci> :info ==
class Eq a where
  (==) :: a -> a -> Bool
  ...
        -- Defined in GHC.Base
infix 4 ==
ghci> :info &&
(&&) :: Bool -> Bool -> Bool      -- Defined in GHC.Base
infixr 3 &&
ghci> :info >
class (Eq a) => Ord a where
  ...
  (>) :: a -> a -> Bool
  ...
        -- Defined in GHC.Base
infix 4 >

이것을 가지고, 이제 괄호가 없으면서 myTest3와 동일하게 해석되는 함수를 짤 수 있습니다.

-- file: ch09/BetterPredicate.hs
infix 4 ==?
infixr 3 &&?
infix 4 >?

myTest4 = liftPath takeExtension ==? ".cpp" &&? sizeP >? 131072

순회 제어

파일 시스템을 순회할 때, 우리 자신에게 어떤 디렉토리를 들어갈지 말지, 혹은 언제 들어갈지에 대한 제어를 주고 싶습니다. 이걸 허용하는 쉬운 방법은 함수 안에서 주어진 디렉토리의 하위 디렉토리 리스트를 받아 다른 리스트를 반환하는 것입니다. 반환한 리스트는 원소가 제거되었을 수도 있고, 원래 리스트와 순서가 다르거나, 혹은 둘 다일 수도 있습니다. 가장 간단한 제어 함수인 id는 리스트를 있는 그대로 돌려줄 겁니다.

다양성을 위해, 표현의 일부분을 바꿔볼 것입니다. InfoP a로 일관하는 대신 내부적으로 나타내는 건 비슷하지만 일반적인 대수적 데이터 타입을 사용할 겁니다.

-- file: ch09/ControlledVisit.hs
data Info = Info {
      infoPath :: FilePath
    , infoPerms :: Maybe Permissions
    , infoSize :: Maybe Integer
    , infoModTime :: Maybe ClockTime
    } deriving (Eq, Ord, Show)

getInfo :: FilePath -> IO Info

“간단히 쓸 수 있는” 접근자를 얻기 위해 infoPath같은 레코드 구문을 사용했습니다. traverse 함수의 타입은 위에서 제안한 대로 간단합니다. 파일이나 폴더의 Info 를 얻기 위해 getInfo 액션을 호출할 겁니다.

-- file: ch09/ControlledVisit.hs
traverse :: ([Info] -> [Info]) -> FilePath -> IO [Info]

traverse의 정의는 짧지만, 빽빽합니다.

-- file: ch09/ControlledVisit.hs
traverse order path = do
    names <- getUsefulContents path
    contents <- mapM getInfo (path : map (path </>) names)
    liftM concat $ forM (order contents) $ \info -> do
      if isDirectory info && infoPath info /= path
        then traverse order (infoPath info)
        else return [info]

getUsefulContents :: FilePath -> IO [String]
getUsefulContents path = do
    names <- getDirectoryContents path
    return (filter (`notElem` [".", ".."]) names)

isDirectory :: Info -> Bool
isDirectory = maybe False searchable . infoPerms

여기서 어떤 기법도 소개하진 않을 테지만, 이건 우리가 맞닥뜨린 함수 중 가장 밀도 높은 함수 중 하나입니다. 줄 단위로 짚어가면서 어떻게 되는지 설명해 봅시다. 처음 두 줄은 우리가 이미 본 코드를 말 그대로 복사한 것과 같기에 어떤 까다로운 점도 없습니다.

contents 변수에 할당할 때부터 흥미진진해집니다. 이 줄을 오른쪽에서 왼쪽으로 읽어보세요. 우리는 이미 names가 디렉토리 항목이라는 걸 알고 있습니다. 현재 디렉토리가 각각의 원소의 앞쪽에 붙고, 현재 디렉토리 자체도 리스트에 추가되는 것을 확인할 수 있습니다. 그 후 getInfo를 얻어낼 경로에 적용하기 위해 mapM을 사용합니다.

그 다음 줄은 더 빽빽합니다. 다시 오른쪽에서 왼쪽으로 읽으면, 이줄의 마지막 요소가 문단 끝까지 이어지는 익명 함수의 정의를 시작하고 있는 걸 볼 수 있습니다. 주어진 Info 값에 따라, 이 함수는 디렉토리를 재귀적으로 방문하거나 (여기에 path를 다시 방문하지 않도록 추가로 확인하고), (traverse의 결과 타입에 맞추기 위해) 그 값을 단일 원소 리스트로 반환합니다.

사용자가 제공한 순회 제어 함수 order에서 반환한 Info 리스트의 원소 각각에 forM으로 이 함수를 적용합니다.

줄 시작에서, 리프팅 기법을 새 문맥에서 사용했습니다. liftM 함수는 일반 함수 concat을 받아 IO 모나드로 리프팅합니다. 달리 말하자면, 이 함수는 (IO [[Info]] 타입인) forM의 결과에서 IO 모나드의 내용물을 꺼내 (우리가 원하는 [Info] 타입을 반환하는) concat으로 붙인 다음 , 그 결과를 다시 IO 모나드 안에 집어넣습니다.

마지막으로, getInfo 함수를 정의하는 걸 잊으면 안 됩니다.

-- file: ch09/ControlledVisit.hs
maybeIO :: IO a -> IO (Maybe a)
maybeIO act = handle (\_ -> return Nothing) (Just `liftM` act)

getInfo path = do
  perms <- maybeIO (getPermissions path)
  size <- maybeIO (bracket (openFile path ReadMode) hClose hFileSize)
  modified <- maybeIO (getModificationTime path)
  return (Info path perms size modified)

여기서 주목할 딱 하나는 예외를 던지는 IO 액션의 결과를 Maybe로 감싸는 유용한 컴비네이터인 maybeIO입니다.

연습문제

  1. 알파벳 역순 순서로 디렉토리 트리를 순회하려면 traverse에 어떤 함수를 넘겨야 할까요?

  2. id를 제어함수로 쓰면, traverse id전위 순회를 합니다: 즉 자식 전에 부모 디렉토리를 먼저 반환합니다. traverse가 자신을 먼저 반환하는 후위 순회를 하도록 하는 제어 함수를 작성해 보세요.

  3. “조건자 이어붙이기”에서 조건자와 컴비네이터를 빌려와서 그것들이 이번에 새로 만든 Info 타입에 동작하도록 해보세요.

  4. 순회 제어와 결과를 거르는 데에 조건자를 각각 받는 traverse의 래퍼 함수를 작성해 보세요.

밀도, 가독성, 학습 절차

하스켈에서 traverse만큼 조밀한 코드는 이상하지 않습니다. 표현력을 얻는 것은 중요하고, 이러한 스타일의 코드를 짜거나 읽는 것은 약간의 연습을 필요로 합니다.

비교를 위해, 덜 조밀한 같은 코드를 여기 준비했습니다. 아마 하스켈에 덜 익숙한 프로그래머에겐 더 친숙할 것입니다.

-- file: ch09/ControlledVisit.hs
traverseVerbose order path = do
    names <- getDirectoryContents path
    let usefulNames = filter (`notElem` [".", ".."]) names
    contents <- mapM getEntryName ("" : usefulNames)
    recursiveContents <- mapM recurse (order contents)
    return (concat recursiveContents)
  where getEntryName name = getInfo (path </> name)
        isDirectory info = case infoPerms info of
                             Nothing -> False
                             Just perms -> searchable perms
        recurse info = do
            if isDirectory info && infoPath info /= path
                then traverseVerbose order (infoPath info)
                else return [info]

바꾼 것은 약간의 치환을 한 것이 전부입니다. 마음껏 부분 적용과 함수 합성을 하는 대신 where 블록에 지역 함수를 정의했습니다. maybe 컴비네이터 자리엔 case 표현식을 사용했습니다. 또 liftM을 쓰는 대신 직접 concat을 리프팅했습니다.

조밀한 것이 전반적으로 좋다고 말하는 것이 아닙니다. 원래의 traverse 함수는 줄 각각이 짧았습니다. 우리는 줄 길이를 줄이고 코드를 명확하게 하기 위해 지역 변수 (usefulNames)와 지역 함수 (isDirectory)를 추가했습니다. 이 이름들은 설명적입니다. 함수 합성과 파이프라이닝을 하긴 하지만, 가장 긴 파이프라인도 세 개의 원소만 담고 있을 뿐입니다.

유지보수가 가능한 하스켈 코드를 짜는 열쇠는 밀도와 가독성 간의 균형을 맞추는 것입니다. 이 연속체에서 독자의 코드가 떨어지는 부분은 독자의 경험 수준에 영향을 받을 듯 합니다.

  • 초보 하스켈 프로그래머 앤드류는 표준 라이브러리로 원하는 바를 이루는 방법을 잘 모릅니다. 그 결과, 이미 많이 존재하는 코드를 알지도 못하고 중복시킵니다.

  • 잭은 몇달간 프로그래밍을 해왔고, (.)으로 긴 코드 파이프라인을 짜는 것을 숙달했습니다. 그의 프로그램을 살짝 바꿀 필요가 있을 때마다, 그는 새 파이프라인을 처음부터 짜야 합니다: 그는 기존의 파이프라인을 더 이상 이해하지 못 하고, 어떻게 짰든 간에 코드는 변화에 매우 약합니다.

  • 모니카는 코딩을 상당기간 해왔습니다. 그녀는 하스켈 라이브러리와 탄탄한 코드를 짜는 관용구에 충분히 익숙하지만, 너무 조밀한 스타일은 지양합니다. 그녀의 코드는 유지보수가 편하고, 요구 조건을 바꿀꿀 때마다 리팩토링이 쉬운 것을 발견합니다.

순회를 보는 다른 방법

traverse 함수로 betterFind 함수보다 더 많은 제어가 가능해졌지만, 아직 중요한 결점이 남아있습니다: 우리는 디렉토리 안으로 재귀하는 것을 피할 수 있지만, 트리 안의 모든 항목의 리스트를 만들기 전까지 다른 항목을 걸러낼 수 없습니다. 만약 우리가 3개의 파일을 찾기 위해 100,000개의 파일을 담고있는 뒤져야 한다면, 3개로 걸러낸 결과를 얻기 전에 100,000개의 원소를 가진 리스트를 만들게 될 것입니다.

한 가지 대안으로 리스트를 조립할 때마다 적용할 필터 함수를 traverse에 새 인자로 주는 것이 있습니다. 이렇게 하면 우리가 필요한 만큼만 리스트를 할당할 것입니다.

하지만, 이 방법도 약점이 있는데: 우리가 최대 3개 항목만 원하고, 그 항목이 100,000개의 항목을 순회하는 동안 맨 처음 3개에서 전부 발견한다면, 우리는 나머지 99,997개의 항목을 무의미하게 순회할 것입니다. 이건 딱히 억지로 생각한 예가 아닙니다. 예를 들어, Maildir의 메일 보관함 형식은 이메일 수신함을 각각의 메일 파일을 가진 디렉토리로 저장합니다. 메일 수신함을 나타내는 한 디렉토리가 수만 개의 파일을 가지고 있는 것을 흔한 일입니다.

우리는 앞서 본 두 함수의 약점을 다른 관점에서 바라봄으로써 해결할 수 있습니다. 파일시스템 순회를 디렉토리 계층구조를 접는 것으로 생각하면 어떨까요?

친숙한 접기 함수인 foldrfoldl'은 결과를 누적하는 것으로 리스트를 순회한다는 개념을 알맞게 일반화 합니다. 리스트를 접는다는 개념을 디렉토리 트리로 확장하는 것은 쉽지 않지만, 우리는 접기에 제어 요소를 넣고 싶습니다. 우리는 이 제어를 대수적 데이터 타입으로 나타낼 것입니다.

-- file: ch09/FoldDir.hs
data Iterate seed = Done     { unwrap :: seed }
                  | Skip     { unwrap :: seed }
                  | Continue { unwrap :: seed }
                    deriving (Show)

type Iterator seed = seed -> Info -> Iterate seed

Iterator 타입은 우리가 접기에 쓸 함수를 위한 편리한 별명을 제공합니다. 이 타입은 씨앗과 디렉토리 항목을 나타내는 Info값을 받고 새 씨앗과 Iterate 타입 생성자로 나타내고 있는 접기 함수를 위한 명령을 반환합니다.

  • 명령이 Done이면, 즉시 순회를 중단합니다. 그러고 결과를 Done 으로 감싸 반환할 것입니다.

  • 명령이 Skip이고 현재 Info가 디렉토리를 나타내면, 그 디렉토리 안으로 순회하지 않고 넘어갑니다.

  • 전부 아니면, 감싼 값을 다음 접기 함수의 입력으로 넘기고 순회를 계속 합니다.

이번 폴드는 논리적으로 왼쪽 접기 종류입니다. 왜냐하면 맞닥뜨리는 첫째 항목부터 접기를 시작할 것이고, 각 단계의 씨앗은 이전 단계의 결과이기 때문입니다.

-- file: ch09/FoldDir.hs
foldTree :: Iterator a -> a -> FilePath -> IO a

foldTree iter initSeed path = do
    endSeed <- fold initSeed path
    return (unwrap endSeed)
  where
    fold seed subpath = getUsefulContents subpath >>= walk seed

    walk seed (name:names) = do
      let path' = path </> name
      info <- getInfo path'
      case iter seed info of
        done@(Done _) -> return done
        Skip seed'    -> walk seed' names
        Continue seed'
          | isDirectory info -> do
              next <- fold seed' path'
              case next of
                done@(Done _) -> return done
                seed''        -> walk (unwrap seed'') names
          | otherwise -> walk seed' names
    walk seed _ = return (Continue seed)

이 코드를 작성한 방식에 몇 가지 흥미로운 점이 있습니다. 첫째로 여분의 인자를 넘기는 것을 막기 위해 영역을 사용한 것입니다. 최상위 foldTree 함수는 fold의 최종 결과에서 생성자를 벗겨내기 위한 단순한 래퍼입니다.

fold가 지역함수라서 foldTreeiter 인자를 따로 넘겨줄 필요가 없습니다. 이미 바깥 영역에 접근할 수 있기 때문이죠. 마찬가지로 walk 또한 바깥 영역에 있는 path를 볼 수 있습니다.

또 달리 주목할 점은 이전 함수에선 forM에서 익명 함수를 호출한 것 대신 walk라는 꼬리 호출 함수를 사용했다는 것입니다. 필요하다면 고삐를 잡아 빨리 멈출 수 있습니다. 반복자가 Done을 반환하도록 해서 말이죠.

foldwalk를 호출하고 walkfold를 재귀적으로 호출해 하위 디렉토리를 순회합니다. 각각의 함수는 Iterate로 감싼 씨앗을 반환합니다. walkfold를 호출하고 그 결과를 조사해 계속 진행할 지 Done이어서 중단해야 할 지를 판단합니다. 이런 식으로, 호출자가 제공한 반복자는 Done을 반환하는 것으로 상호 재귀적인 호출을 단번에 끝낼 수 있습니다.

반복자는 실제로 어떻게 보일까요? 여기 SVN 메타데이터 디렉토리를 제외하고 최대 3개의 비트맵 파일을 찾는 약간 복잡할 수 있는 예제가 있습니다.

-- file: ch09/FoldDir.hs
atMostThreePictures :: Iterator [FilePath]

atMostThreePictures paths info
    | length paths == 3
      = Done paths
    | isDirectory info && takeFileName path == ".svn"
      = Skip paths
    | extension `elem` [".jpg", ".png"]
      = Continue (path : paths)
    | otherwise
      = Continue paths
  where extension = map toLower (takeExtension path)
        path = infoPath info

이걸 사용하려면, IO [FilePath]를 반환해주는 foldTree atMostThreePictures []를 호출합니다.

물론 반복자는 저렇게까지 복잡해질 필요는 없습니다. 이건 발견한 디렉토리의 갯수를 세는 반복자입니다.

-- file: ch09/FoldDir.hs
countDirectories count info =
    Continue (if isDirectory info
              then count + 1
              else count)

여기선 처음 foldTree에 넘기는 씨앗은 숫자 0이 되어야 할 겁니다.

연습문제

  1. 호출자가 디렉토리 안 항목의 순회 순서를 바꿀 수 있도록 foldTree를 수정해보세요.

  2. foldTree 함수는 전위 순회를 합니다. 호출자가 순회 순서를 결정할 수 있도록 수정해보세요.

  3. foldTree가 받는 반복자를 표현하는 컴비네이터 라이브러리를 만들어 보세요. 그것이 독자가 작성하는 반복자를 더 간단명료하게 만드나요?

유용한 코딩 지침

좋은 하스켈 코딩 습관은 경험에서 많이 나오지만, 우리는 독자가 더 빨리 가독성있는 코드를 작성할 수 있는 일반적인 팁을 약간 가지고 있습니다.

“탭 VS 공백에 관한 언급” 장에서 언급했다시피, 하스켈 소스에서 절대 탭을 쓰지 마세요. 공백을 쓰세요.

만약 어떤 부분의 코드가 귀신처럼 영리한 것을 자랑스럽게 생각하는 자기 자신을 발견한다면, 일단 멈추고 한 달간 그 코드를 보지 않은 후에 자신이 다시 그 코드를 이해할 수 있을지 생각해 보세요.

타입이나 변수 이름을 합성어로 짓는 관습적인 방법은 “Camel case” 입니다. myVariableName이 예시가 됩니다. 이 스타일이 하스켈 코드에서 가장 보편적입니다. 명명법에 어떤 취향을 가졌던 간에, 표준이 아닌 관습을 따르면 당신의 하스켈 코드는 다른 읽는 사람의 눈에 다소 이상하게 보일 것입니다.

하스켈로 상당히 많은 시간 작업을 해보기 전까지, 작은 함수를 작성하기 전에 몇 분간 라이브러리 함수를 찾아보세요. 이건 특히 리스트나 Maybe, Either같은 널리 쓰는 타입에 해당됩니다. 만약 표준 라이브러리가 정확히 당신이 원하는 기능을 제공하지 않으면, 몇 가지 함수를 합성해서 원하는 결과를 얻을 수 있을 겁니다.

세 개나 네 개 이상의 연쇄된 합성 함수 파이프라인은 읽기 힘듭니다. 만약 그런 파이프라인이 있다면 let이나 where 블록으로 그걸 더 작은 조각으로 쪼개세요. 각각의 파이프라인 원소에 의미있는 이름을 붙인 후 다시 이어 붙이세요. 만약 원소에 적절한 이름이 떠오르지 않으면, 스스로 이게 무엇을 하는지 설명할 수 있는지 확인해보세요. 만약 대답이 “아니오”라면, 코드를 단순화하세요.

80열 이상 텍스트 에디터를 조절하기 쉽다고 해도, 이 너비는 아직 매우 일반적입니다. 더 긴 줄은 80열 짜리 텍스트 에디터 창에서 줄 바꿈되기 마련이고, 가독성을 심하게 해치게 됩니다. 한 줄에 최대 80글자까지만 들어가도록 다루면 당신이 한 줄에 휘갈기는 코드의 양도 제한합니다. 이건 각각의 줄이 덜 복잡해지고, 그 결과 더 이해하기 쉽도록 도와줄 겁니다.

일반적인 레이아웃 스타일

독자가 레이아웃 규칙을 제대로 지켜서 파싱에 애매함을 초래하지 않는 한 하스켈 구현은 당신을 야단치지 않을 겁니다. 그렇긴 하지만, 몇몇 레이아웃 패턴이 널리 쓰이고 있습니다.

in 키워드는 이어지는 표현식 바로 아래에 let 키워드 맞춰 곧바로 정렬됩니다.

-- file: ch09/Style.hs
tidyLet = let foo = undefined
              bar = foo * 2
          in undefined

in의 들여쓰기를 다르게 하거나 표현식 끝에 “매달리게” 해도 적법하지만, 다음 코드는 일반적으로 이상하게 보일 것입니다.

-- file: ch09/Style.hs
weirdLet = let foo = undefined
               bar = foo * 2
    in undefined

strangeLet = let foo = undefined
                 bar = foo * 2 in
    undefined

반면에 do는 줄 끝에 매다는 것이 다음 라인의 시작에 붙이는 것보다 더 일반적입니다.

-- file: ch09/Style.hs
commonDo = do
  something <- undefined
  return ()

-- not seen very often
rareDo =
  do something <- undefined
     return ()

중괄호와 세미콜론은 적법하지만 거의 쓰지 않습니다. 그 자체엔 아무 문제가 없습니다. 이것들은 단지 희소성만으로 코드를 어색하게 만듭니다. 이것들은 프로그램이 레이아웃 규칙을 구현하지 않고 하스켈 코드를 짜는 경우를 의도한 것이지, 사람이 쓰는 것을 의도하지 않았습니다.

-- file: ch09/Style.hs
unusualPunctuation =
    [ (x,y) | x <- [1..a], y <- [1..b] ] where {
                                           b = 7;
 a = 6 }

preferredLayout = [ (x,y) | x <- [1..a], y <- [1..b] ]
    where b = 7
          a = 6

만약 등식의 우변을 새 줄에서 시작한다면, 대개 그것이 정의하는 변수나 함수 이름보다 약간 더 들여쓰기 합니다.

-- file: ch09/Style.hs
normalIndent =
    undefined

strangeIndent =
                           undefined

들여쓰기에 쓰는 실제 공백 개수는 같은 파일 내에서도 자주 변합니다. 2, 3, 4개의 공백이 엇비슷하게 많이 쓰입니다. 공백 하나도 적법하지만, 잘 구분되지 않기에 잘못 읽기 쉽습니다.

where 구문을 들여쓸 땐, 그걸 잘 드러나도록 들여쓰는 게 가장 좋습니다.

-- file: ch09/Style.hs
goodWhere = take 5 lambdas
    where lambdas = []

alsoGood =
    take 5 lambdas
  where
    lambdas = []

badWhere =           -- legal, but ugly and hard to read
    take 5 lambdas
    where
    lambdas = []

연습문제

이 장의 파일을 찾는 코드가 학습 용도로 괜찮긴 하지만, 실제 시스템 프로그래밍 작업에선 별로 이상적이지 않습니다. 하스켈의 이식성 있는 입출력 라이브러리는 정보를 많이 노출하지 않아 궁금하고 복잡한 질의를 허용하지 않기 때문입니다.

  1. 이 장의 코드를 System.PosixSystem.Win32같은 네이티브 API를 사용해 독자의 플랫폼으로 포팅해보세요.

  2. 디렉토리 항목을 누가 소유하고 있는지 확인하는 기능을 독자의 코드에 추가해 보세요. 이 정보를 조건자에서도 쓸 수 있도록 만들어 보세요.

저작자 표시 비영리 동일 조건 변경 허락
신고

Practical Programming in Tcl and Tk 4th 요약 - chap25. Pack관리자Practical Programming in Tcl and Tk 4th 요약 - chap25. Pack관리자

Posted at 2013.03.24 13:50 | Posted in 지식저장소/읽은 책 요약

음... 책을 보고 예제를 안 짜니 왠지 잊어버릴것만 같은 느낌.


이 책을 보게 된 이유는 Apkzipper를 Tcl/Tk로 짜려고 생각했기 때문.


처음엔 문법이 굉장히 단순하고 크로스플랫폼 GUI라니! 라고 생각을 했지만, 역시 사용층이 적다는 건 좀 문제였다 ㅠㅠ

게다가 언어 자체가 TclOO를 제외하면 절차지향적이라서... 아직 익숙하지 않아서 그런지 좀 어려움을 느꼈다.

결정적으로 문법이 단순하다고 코딩이 단순한 것은 아니었다는 것. 표준 함수라든가 그런 것들도 알아야 쉬이 짤 수 있는 것인데. 결국 배우는데 오래 걸리게 되었다. (허투루 배우다가 헤맨 것도 한 몫 할 것이다)


좀 이상한 잡설이었다. chap25이전은 대충대충 넘어가 버려서 이번부터라도 따로 정리해두려고 한다.


Part III. Tk Basics의 세번째 챕터인데, 그 이전에 나온 Tk의 기본적인 사항들은 넘어간다. 


윈도우즈 API로 코딩해본 사람들이면 좀 짜증나게 생각되는 부분이 있을 것이다. 바로 창의 위치를 지정해 주는 것.

좌표 하나하나 값을 매겨줘야 하는데, 여간 귀찮은 것이 아니다.


Tk에는 배치 관리자Geometry Manager (굉장히 의역...인데 별로 안 좋으려나;;) 라는게 있어서, 좌표를 일일히 매기지 않고도 창의 모양을 짜임새 있게 만들어 준다. 

Tk에는 이 배치 관리자가 3가지 있는데, pack, grid, place가 그것이다. 그리고 이 관리자 중 하나를 선택하지 않으면 버튼 하나조차 넣을 수 없다.

일단 편하게 쓰기 위해선 외워야 하는 건 필수인 것 같고, 이제 pack 관리자에 대해서 알아보자.


pack은 가장 편하게 쓸 수 있는 관리자다. 말 그대로 '넣어'준다.

가장 간단한 예제로 버튼 한개를 넣어보자.


pack [button .b -text 꽥!]


단순의 극치긴 하다. 이게 점점 복잡해지는 이유는 다른 여러개를 넣기 위해서 세부사항을 지정해주는 옵션을 추가하기 때문이다.


이제 pack으로 만들 목표를 하나 잡아보자. pack으로 다음과 같은 입력대화상자를 만들기 되게 쉽다.



아직은 이렇게 만들 순 없다. 아마도 저 클릭! 버튼이 성가실 것이다 ㅋㅋ

그럼 이렇게 만들기 위해선 뭐가 필요할까?


1. 붙일 위치를 지정해주는 -side옵션

pack 위젯경로 옵션 순인데, -side 다음에 top, bottom, left, right 중 하나를 쓸 수 있다. 그 효과는 다음 예제로 알아보자.


pack [button .b -text 꽥!]
pack [button .c -text 오른쪽] -side right

pack [button .d -text 왼쪽] -side left

pack [button .e -text 아래쪽] -side bottom



ㅇ? 대충 비슷하긴 한데 저 아래쪽 버튼이 거슬린다. 왜 아래로 안 가고 가운데 들어간 거냐.

왜 이렇게 되는 건지 알려면 구멍 모델Cavity model을 알아야 한다. pack 관리자는 이 알고리즘으로 위젯을 삽입하기 때문이다.

간단하다. pack관리자는 새로운 위젯을 삽입할 때 남은 구멍공간에 삽입한다. 아래 그림을 일단 보자.



일단 꽥! 버튼이 위쪽 주황색 공간을 먼저 차지한다. pack을 할 때 -side옵션을 지정하지 않으면 top으로 기본설정된기 때문.

그 다음 오른쪽 버튼과 왼쪽 버튼이 순서대로 각각 하늘색 공간 (나머지 공간의 왼쪽, 오른쪽)을 차지한다.

그럼 초록색 공간이 남는데, 이런 남은 공간이 구멍Cavity이고, 여기에 새로운 위젯이 상하좌우 방향으로 공간을 할당받는 것이다. 아무것도 배정되지 않았을 때는 전체가 구멍이라고 생각하면 된다.


이제 아래쪽 버튼을 추가하게 되면 저 초록색 공간의 아래쪽 부분을 배정받게 되는 것이다. 만약 공간이 부족하다면 창이 저절로 늘어날 것[각주:1]이다.

그리고 이런 공간 점유는 순서대로 먼저 먹는 위젯이 임자기 때문에, 위젯 삽입 순서Stacking order도 중요하다.

이제 위의 코드에 다음 코드를 추가로 넣어보자. 결과가 납득이 갈 것이다.




pack [button .f -text 왼쪽2] -side left

pack [button .g -text 왼쪽3] -side left




이제 위에서 본 입력 대화상자 예제를 만들 수 있게 되었다. 실제로 만들어보고 싶은 사람들을 위해 일단 접어두겠다.

하지만 아래부터는 또 이 코드를 쓸 것이므로 만들어보고 싶은 사람은 지금 만들어보자.

코드




2. -expand 옵션

이제 저 입력 대화상자 크기를 늘려보겠다.



... 이건 좀 아닌 것 같다. 문제가 뭘까.

이 상황에서 각각의 패킹 공간을 살펴보면 이렇다.


왼쪽 엔트리가 저 구멍공간을 다 차지하면 좋을텐데, 이럴 땐 -expand true를 설정하면 사용할 수 있는 구멍이 있을 때 자동으로 패킹공간을 늘어나게 할 수 있다.

이제 다음 코드를 실행해보면





pack config .l -expand true

pack config .e -expand true








3. -fill 옵션

아직 뭔가 부족하다. 엔트리의 패킹 공간(Packing space)은 늘어났는데 위젯의 크기(Display space)는 안 늘어난 것이다.

이제 다음의 코드도 실행해보자.





pack config .e -fill x








이제 좀 괜찮아 보인다. 

-fill 옵션은 none, x, y, both 4가지로 설정할 수 있다.


이제 중요한 부분은 끝났다. 나머지는 덜 중요한 것들이다. 알면 좋지만서도.


4. -padx, -pady, -ipadx, -ipady

바로 위 그림의 "이름을 알려주세요"라벨이 사실 이게 적용되어있다. (스샷의 귀찮음으로 통합)

-pad 옵션은 위젯이 배치될 때 바깥부분에 여백을 주는 것이고, -ipad는 안쪽에 여백을 주는 것인데, 지금 위 사진의 라벨은 -ipadx 3 -pady 3이 걸려있다. 경계면이 보이는건 label -relief sunken이라서 그렇다. (이거였나, 하튼)

x y축의 여백을 조절한다는 건 알 거고, 리스트로 여백을 따로 설정할 수도 있긴 하다.

ipad는 별로 티는 안나지만, 저 텍스트 부분의 영역이 줄어든다.


5. -anchor

expand옵션 설명할 때 나왔는데 저렇게 위젯의 크기보다 패킹 크기가 더 커서 공간이 널널해진 경우가 있다.

anchor nw 같은 식으로 설정하면 북서쪽, 즉 패킹공간 내 좌상단에 위젯이 붙어버린다.

기본값은 center이다.


6. etc

일단 패킹 순서가 중요하다는 건 알 것이다. 그 패킹 순서를 바꾸는 옵션이 -before, -after이다.


이건 안 쓰게 될까나...

raise

pack slaves

pack info










  1. 그런데 창이 저절로 늘어나게 하고 싶지 않다면 어떻게 하면 좋을까? 그때는 propagate 서브커맨드를 쓰면 된다. pack propagate . false를 치면 이런 창 크기 맞춤이 비활성화 된다. [본문으로]
저작자 표시 비영리 동일 조건 변경 허락
신고

C로 배우는 알고리즘 - 복습 겸 요약 7C로 배우는 알고리즘 - 복습 겸 요약 7

Posted at 2012.11.22 21:23 | Posted in 지식저장소/읽은 책 요약

5. 정렬 - 분포수세기, 퀵 정렬, 기수 정렬, 힙 정렬, 병합 정렬



5. 분포 수 세기

 Distribution Counting


각각의 자료의 수를 세어 들어갈 위치를 계산하는 방법이다. 자료의 종류만큼의 배열을 준비해야 한다.

기수정렬에서 응용되어 엄청난 성능을 발휘한다고 한다. 메모리를 많이 먹는다 뿐이지 그렇게 나쁘진 않다.

다만 사용 조건이 좀 까다로워서 기수 정렬에서 응용하는 것 같다.

또 하나, 이건 Single byte string search에선 유용할 것 같다.. 다만 Everything처럼 부분 문자열검색을 하는데 쓰긴 어렵겠지. 그건 따로 String search 알고리즘을 배워야 하나,...


이름

'세어서' 정렬을 하니까 그런가.


방법

나름 설명: 각각의 원소 종류들 개수를 세어 누적도수분포표를 만든다. 그러면 각각의 종류의 원소들이 정렬되었을 때 맨 오른쪽자리를 알 수 있다. 오른쪽부터 다시 세면서 누적도수분포표를 깎아가며 채워넣는다.


특징

1. 메모리를 먹는다. 사본을 생성하기 때문에 입력자료만큼의 메모리가 추가로 필요하고, 또 자료의 종류만큼의 메모리가 필요하다.

2. 시간복잡도는.. 교재엔 안 나오지만 O(N)일 것 같다. 그리고 입력자료의 배열에 영향을 받지 않는다. (즉, 자료의 크기에만 영향을 받는다.)

3. 안정성이 있다.

4. 결론: 분포 수 세기는 데이터의 종류가 적은 (혹은 중복된 자료수가 많은) 자료에 적합하다.

5. if문이 없는 정렬법이라 그런지 굉장히 빠르다.


최적화

딱히 최적화라기보다, 저 안정성이라는게 앞에서부터 채워넣는방식으로 알고리즘을 짜면 사라진다. 안정성을 부여하기 위해 뒤에서부터 자료를 채워넣는다.



6. 퀵 정렬

 Quick sort

분할해서 정복한다는 개념에선 쉘 정렬과도 비슷하다. 또한 어떤 임의의 값이 성능에 영향을 끼치는 것도 유사하다면 유사하겠지.

만들려고 할 때 괜히 욕심부려서 배열 안 쓰고 포인터 썼다가 피봄. 아직 미숙한 건가...

일반적으로 빠른 정렬이고, 가장 많이 쓰인다.


이름

일반적으로 빠른 정렬이라서 그런가 봄.


방법

나름 설명: 어떤 기준값을 잡고, 그 값보다 크거나 같은 값을 왼쪽에서부터, 작거나 같은 값을 오른쪽에서부터 찾음. 양쪽에서 둘 다 찾았는데 서로 뒤바뀌지 않았으면 교환. 좌우가 뒤바뀌었으면 양 옆 구간을 분할해서 재귀호출. 사이즈가 1이면 종료.


특징

1. 안정성이 없다. 굉장히 빠르다. 재귀호출이 메모리를 먹는다.

2. 시간복잡도는 가장 이상적일 때 을 가진다고 하고 최악의 경우에는 까지도 간다고 한다. 하지만 최악의 경우가 랜덤한 경우에 있는 터라 역시 발생하긴 쉽지 않다. 하지만 값을 무성의하게 정했을 때는... 모르지.

3. 일반적으로 많이 쓰이는 이유는 뭘까? 복잡한데;;


최적화

책에서 비재귀화를 첫번째로 다뤘다. 하지만 내 실험결과 비재귀화하려고 push(), pop()쓰는 건 이미 뭔가 이상하기 때문에.. ㄱ-.

함수 호출을 없애려고 함수 호출을 2개로 늘리다니? 말도 안 된다. 실험해봐도 저 push, pop조합이 훨 느렸다.

그 밖에 원소가 일정개수 이하일 경우 그냥 삽입 정렬을 시도하는 방법이 있었는데, 이건 꽤 좋았다. 성능 향상이 확실하다. 그 자잘한 구간을 재귀호출하느니 삽입정렬이 차라리 낫겠지.

또 축값Pivot을 잘 지정하는 방법이 무작위로 결정하는 것과, 세 값을 추출해 그 평균을 구하는 것이 있었는데, 나는 그냥 맨 앞·뒤 두 값의 평균만 이용했다. (이정도면 정렬알고리즘 공격도 가능하겠지 ㅡㅡ;)



7. 기수 정렬

 Radix sort


컴퓨터의 자료구조가 기본적으로 Digital이라는 발상에 기초. 비트연산으로 정렬을 한다.

기수교환정렬Radix exchange sort와 직접기수정렬Straight radix sort가 있다.


이름

기수 수학용어를 네이버 사전에서 찾아보니.. 2를 기수로 하는게 디지털자료. 그 특성을 이용해서 기수정렬이라 하나보다.

숫자 자리 표시법에서 어떤 자리의 가중값(weight)으로, 이 수를 곱하면 바로 윗자리에 대한 가중값이 얻어지는 정수.10 진법(decimal notation)에서, 예를 들면 256은 2×102+5×101+6×100으로 표현할 수 있는데, 이 경우 10을 기수라고 한다.


방법

나름 설명

기수교환정렬: 기준점을 각각의 비트 하나씩으로 잡고 퀵 정렬.

직접기수졍렬: 각각의 비트를 좀 나누고 뒤에서부터 분포수세기. (앞에서부터 하려면 퀵 정렬식으로 해야돼서.. 복잡해짐)


특징

0. 공통점: 자료의 비트 수가 적어야 쓰기 편하다. 비트를 직접 비교하므로. 대신 무지 빠르다.


기수교환정렬

1. 퀵 정렬의 속성을 가진다. 상속같은 개념인가 ㅋㅋ. 일단 비트를 사용한다는게 특징일 뿐이지 방법 자체는 퀵 정렬이니까.

2. 그러므로 안정성이 없다. 다만 기준값가지고 골때리는 일은 없다. 비트가 1 or 0인지만 판단하니까.


직접기수정렬

1. 분포 수 세기의 속성을 가진다. 즉, 입력자료의 사본을 추가로 할당한다.

2. 안정성이 있다. 뭐 분포 수 세기의 속성은 전부 가지고 있다.


최적화

이 책은 최적화만 나오면 비재귀화가 감초로 나오는데... 물론 패스한다. 나머지 최적화 얘기는 없었다.

근데 직접기수정렬에서 안정성이 있기 때문에 그냥 뒤에서부터 2비트씩 정렬하는 방법을 쓰더라. (물론 시대가 다르기 때문에 나는 1바이트씩 비교하는 방법을 썼다.) 그렇게하면 확실히 구현이 간단해지고 최종적으로도 안정성이 있다.

근데 앞에서부터 비교하면서 퀵 정렬의 분할방법을 쓰는 건 어떨까? 분할 + 분포 수 세기. 안정성은 잃어버리겠지만 혹시 더 빨라질지도...? 지금은 구현하지 않았고. 나중에..



8. 힙 정렬

 Heap sort


힙이 뭔지 먼저 알아야 한다... 자료구조개념을 다시 알아봐야겠다.

힙정렬 부터 점점 이해도가 떨어지는 느낌이다 ㅡㅡ.... 나중에 실전에서 복습이라도 해야하나.


우선순위 큐Priority queue: 특정한 자료구조를 의미하는 게 아니라, 자료의 각각이 순위를 가지고 관리되는 자료구조의 추상적 개념.

예를들어 스택, 큐... 이 힙도 거기 들어가나 보다.

일반적으로 다음의 7가지 동작이 정의되다고 한다.

1. 삽입Insert: 우선순위 큐에 새로운 자료를 삽입한다.

2. 제거Remove: 순위가 가장 높은 자료를 제거한다.

3. 생성Construct: N개의 자료로 우선순위 큐를 만든다. N번 삽입과 같다.

4. 대치Replace: 순위가 가장 높은 자료와 새로운 자료를 바꾼다. 제거 + 삽입과 같다.

5. 변경Change: 자료의 순위를 변경한다. 삭제 + 삽입과 같다.

6. 삭제Delete: 임의의 자료를 삭제한다.

7. 결합Join: 두 우선순위 큐를 결합하여 큰 우선순위 큐를 만든다.


힙이란?

우선순위가 키 값의 크기에 의해 정해지는 자료구조라고 한다. 키 값은 데이터를 말하는 것 같다.

어떤 키가 다른 특정한 두 키보다 큰 값을 가져야 한다는 조건이 있는데, 그 조건만 만족하면 힙이 되는 것이다.

여기서 '두 키'라는 말이 있기 때문에 자료구조로 구현하면 이진트리로 자연스레 구현된다.

교재에서 힙의 뿌리는 전체 레코드중에서 가장 큰 레코드가 된다. 라고 했는데, 사실 오름차순이든 내림차순이든 상관 없는 것 같다. 위키에 따르면.

(잠깐, 이게 꼭 순위대로 정렬이 된 상태는 아니네? 양쪽의 순서는 따지지 않아..)

새로 삽입된 자료가 힙의 규칙에 맞게 지위가 상승하는 것을 UPHEAP, 반대로 끌어내리는 것을 DOWNHEAP이라고 한다.


층별순으로 순위를 매기면 다음의 관계를 얻을 수 있다.

1. 번호 j를 갖는 노드의 부모의 번호는 j/2

2. 번호 j를 갖는 노드의 왼족자식의 번호는 j*2, 오른쪽 자식은 j*2+1

3. 힙 자료의 개수 n의 절반(n/2)까지가 내부 노드.


일반 나무구조는 균형이 잡혀있지 않은 경우도 있기 때문에 배열로 구현할 때 공간의 낭비가 심하다. 하지만 힙은 규칙으로 거의 완전이진트리를 형성하므로 배열로 구현하기 편하다. 그 배열의 첨자로 사용하기 위해 저렇게 층별순위를 매겨두는 것이다.


근데... 구현은 편한지 몰라도 내겐 좀 어려운 걸까 ㅡ,.ㅡ


이름

Heap.. 영어사전에서 찾아보니까 '수북히 쌓아놓은 더미'라고 한다.


방법

나름 설명: 힙을 만들면 그 힙의 최상위 값은 항상 최소·최대값 중 하나를 가지게 된다. 힙을 유지하면서 그 최상위 값만 뽑아 순서대로 저장하면 끝. 그 힙을 만들 때 기존의 배열이 있는 공간을 사용할 수 있으므로 추가적인 메모리가 필요치 않다.


특징

1. 매우 빠르다. 시간 복잡도가 임이 밝혀져 있다. 즉, 최악의 경우가 뜨더라도 그렇게 많이는 느려지지 않는다. 하지만 검색해보니 실제로는 퀵 정렬보다 평균적인 소요시간에서 좀 떨어지는 듯 하다.

2. 복잡하다. 아니, 구현이야 굉장히 깔끔하지만 내가 이해하기에... ㅠㅠ 익숙해지면 나으려나.

3. 성능이 좋은데도 추가적인 메모리가 필요없다.

4. 안정성은 없다.


최적화

하향식으로 힙을 만들 수도 있고, 상향식으로도 만들 수 있나 보다. 상향식으로 만드는 게 소스 양을 반으로, 연산을 2/3으로 줄여준다.


퀵 정렬과 힙 정렬의 비교분석: http://kldp.org/node/110384

내용 중 일부를 추려본다.


winner님

힙 구조를 만드는 데 필요한 시간은 O(N)이고, 깨진 구조를 바로잡는데 걸리는 시간은 O(NlogN), 최대원소를 찾는 시간은 O(1)이다.   거기다 필요 공간도 O(1)이므로 매우 효율적인 정렬이 가능하지만, 정렬 특성상 자료에 따라 시간을 단축하는 것이 없고, 힙 재조정 연산이 들어가면 캐시 이용이 힘들어져 퀵소트에게 밀리게 되었다.

이런 이유로 힙 정렬은 우선순위큐에 많이 쓰이는데, 최대원소를 빼내면서 원소를 중간마다 추가할 수 있어야 한다는 요구사항을 반영한 자료구조이므로 Heap이 아주 적당하다는 게 이유이다.

(힙이 적당히 정렬된 상태란 말도 있었다. 힙을 구축했다고 하더라도 실제론 정렬된 상태가 아니라 최대원소를 즉각 뽑아낼 수 있는 상태인 것 뿐이다. 그러므로 Heap이 우선순위 큐에 어울리며, 실제 삽입과 삭제가 빈번한 자료에서의 정렬에 쓴다고 하면 힙을 분리 시켜야 할 테기 때문에 사본을 떠야 할 것이다.)


jick님

힙소는 그런 거 다 필요없이 시작과 끝이 있는 1차원 배열 하나 덜렁 던져주고 "이거 소트해줘" 하는 상황에서도 아주 간편하게 써먹을 수 있습니다. 

(힙 정렬하고 쉘 정렬하고 비슷하지만 쉘 정렬은 간격을 설정하는 문제가 있기 때문에 즉흥적으로 써먹긴 힘들지도.)

vuccell님

퀵 정렬이 되는 경우는 실제로 거의 없고, 평균적인 수준에서 힙 정렬은 퀵 정렬보다 20%느리고, 최악의 경우에도 거기서 20%더 느리다. 이른바 보험같은 검색방식. 역시 평균적인 상황이 중요하므로 퀵 소트를 쓰는 것이다.

9. 병합 정렬

 Merge sort


교재에서 순차접근을 하기 때문에 외부정렬에 쓰이기 편하다고 한다.



이름

배열을 나눠서 정렬한 다음 합친다. 쉘 소트하고 다른 점은 간격을 두고 분할하는 게 아니란 것.


방법

나름 설명: 처음엔 1사이즈로 배열을 분할한다. 그 중에서 순서대로 2개의 배열을 선택하고 두 배열 맨 앞을 비교해서 (1개면 이미 정렬된 것이나 마찬가지니까.) 작은 것부터 사본에 복사한다. 그런 식으로 2개의 배열을 사본 배열 1개로 정렬한다. 그걸 원본 배열 끝까지 반복. 반복 했으면 사이즈를 키워서 반복. (가다가 짝이 안 되는 건 알아서. ㄱ-)


특징

1. 빠르다. 시간 복잡도가 임이 밝혀져 있다.

2. 안정성이 있다.

3. 사본을 떠야 하기 때문에 입력자료만큼의 추가적인 메모리가 필요하다. 즉, 공간복잡도 O(N).


최적화

교재에선 배열 바꿔치기할 때 원소 하나하나 복사하지 말고 포인터만 교체하라고 하는데 그건 기본 아닐까.



교재엔 외부 정렬External sort 챕터가 하나 더 끼어있었다. 외부장치는 느리고 순차접근만 가능하니까 임시파일로 쪼개서 입력 받는데 그걸 잘 내부정렬하여라... 라는 내용이었나. 쓸 필요를 느끼지 못했다.



마지막으로, 이 모든 것이 구글링하면 더 잘 일목요연하게 나온다는 거... 그냥 자기만족적 복습이지 뭐.


기념으로 만든 실행프로그램을 올리겠다. 지금까지 실습한 정렬을 그래프로 표현하는 프로그램이다.

SortSimulation.exe는 그냥 정렬 실행

SortSimulation_delayed.exe는 정렬되는 모습을 보여줌. 하지만 일부러 슬립함수를 넣었기 때문에 벤치마크 불가.

근데 알고리즘 비교하려해도 대충만든 게 한둘이 아니기 때문에 비교거리도 안 됨;;



SortSimulation.exe


SortSimulation_delayed.exe


나중에 정렬의 특성을 표로 만들어 볼 예정.


이름 시간 복잡도 공간 복잡도 난이도 방식 범용성 안정성 활용성
거품 정렬
선택 정렬
삽입 정렬
쉘 정렬
퀵 정렬
분포 수 세기
기수 교환 정렬
직접 기수 정렬
힙 정렬
병합 정렬

저작자 표시 비영리 동일 조건 변경 허락
신고

C로 배우는 알고리즘 - 복습 겸 요약 6C로 배우는 알고리즘 - 복습 겸 요약 6

Posted at 2012.11.20 02:43 | Posted in 지식저장소/읽은 책 요약

5. 정렬 알고리즘 - 선택·삽입·거품·쉘 정렬


음... 확실히 정했다. 혼연C하고 이 책을 동시에 봐야겠다. 계속 그랬지만 본격적으로 그래야 겠다.

근데 이렇게 마음먹자마자 혼연C 알고리즘 부분이 빈약해보이는 건 무슨 일이지;;


이 부분도 역시 예전엔 조금 알았는데 고등어 생활 중 많이 잊어버렸다. 다시 복습해야.. ㅠㅠ


정렬알고리즘은 C로...책으로 보니까 굉장히 신기하다. 종류도 많을 뿐더러 특히 그래프로 정렬되는 과정을 보여주는 그림이 가장 신기했다. o_o


그래서 가능한 한 WinAPI를 사용해 그림으로 표현하는 프로그램을 짤 생각이다.


그럼 ㄱㄱ



1. 개요

 정렬을 왜 할까? 검색하려고. 즉 검색하려고 정렬을 배운다.


오름차순Ascending order은 뒤로 갈수록 값이 커지는 방향으로 배열하는 것을 의미하고

내림차순Descending order은 뒤로 갈수로 값이 작아지는 식으로 배열하는 것을 뜻한다.

한글로 익히면 헷갈리는 경우가 많으므로 영어 단어를 떠올려야 겠다.

정렬은 퀵 소트라는 것이 일반적으로 가장 빠르다고 알려져있지만, 100%그런 것은 아니다. (ex. 이미 정렬된 자료의 경우 플래그 버블보다도 느릴 수 있다.) 결국 상황에 가장 적절한 알고리즘을 고르는 안목이 필요하다.


정렬의 방법론

컴퓨터는 사람처럼 한 번 딱 보고 정렬할 수 없다. 컴퓨터는 판단(=비교) · 교환 두가지 동작을 할 수 이으며, 정렬 알고리즘은 이 두가지를 어떻게 섞는지에 대한 방법론이다.


정렬 알고리즘의 다양성

간단한 알고리즘: 선택 정렬, 삽입 정렬, 거품 정렬, 쉘 정렬

복잡한 알고리즘: 퀵 정렬, 기수 정렬, 힙 정렬, 병합 정렬


외부 정렬: 정렬의 대상이 되는 레코드들이 디스크나 테이프같은 컴퓨터 외부에 있으면.

내부 정렬: 정렬의 대상이 되는 레코드들이 메모리같은 컴퓨터 내부에 있으면.


직접 정렬: 레코드 자체를 옮김 (C로 표현하자면 구조체)

간접 정렬: 레코드의 지시자를 옳김 (C로 표현하자면 배열첨자나 포인터) - 대부분 이걸 쓰겠지. int가 아닌 이상.


정렬 기본 방법에 따른 분류

삽입: 삽입 정렬, 쉘 정렬

교환: 거품 정렬, 퀵 정렬, 기수 교환 정렬

병합: 병합 정렬

선택: 선택 정렬, 힙 정렬

세기count: 분포 수 세기, 직접 기수 정렬


안정성이란?

당나귀P2P에서 안정성있는 정렬알고리즘을 사용한 것 같다.

내가 사용한 예로는, 최고화질의 영화를 찾고 싶다면 일단 파일크기로 내림차순 정렬을 하고 파일 종류로 정렬을 하는 것이다.

그러면 영화파일끼리 묶이게 되는데, 그 영화파일의 맨 위에는 가장 파일크기가 큰 것 (즉 고화질)이 오게 된다.

이렇게 우선 순위가 같은 자료에 한해서 이전의 정렬결과가 보존되는 것을 '안정성이 있다'라고 한다.


일반화된 정렬함수

이 책에선 void*만 말하고 있는데... 지금은 C++시대다. 함수 포인터를 넘겨주는 건 객체로 바뀌겠지. anachronistic.


정렬을 시뮬레이션하기 위해선 일단 난수 배열이 필요하다.

여기선 큰 문제가 안 되지만, 난수에 대해선 불평할 게 하나 있다. 나중에 따로 포스팅 하기로 한다. (그냥 내 무지에서 나온 걸지도 모르지만)


이제부터 모두 오름차순 정렬기준으로 쓴다.


2. 선택 정렬

 Selection sort


오타 발견.. 322p 2. i가 n-2가 되면 끝낸다. n-1아닌가 싶다.

WinAPI짜는 거 GetExitcodeThread MSDN 잘못 읽어서 좀 삽질했다. 아나. 난 왜 이런식이지.


이름

최소값을 '선택'해서 교환하는 방법을 써서 선택정렬인가 보다.


방법

내 나름 설명: 일단 첫 번째 원소를 고르고 거기에 들어갈 최소값 원소를 쭉 검색한다. 끝까지 검색했으면 나온 최소원소(중 맨 마지막 원소)와 첫 번째 원소를 교환한다. 이제 두 번째 원소를 첫번째 원소로 두고 반복한다. 이걸 비교 대상원소가 1개가 될 때까지 반복한다.


특징

1. 간단하고 느리다. 안정성은 없다. 메모리 사용은 O(1)이다. 소요시간은 아마도 Θ(N²).

즉 자료의 크기가 같다면 정렬 시간은 동일하다.

2. 교환의 횟수가 가장 작은 편에 속한다. 

비교횟수가 N(N-1)/2 정도이다. 읽기는 많이 하지만 교환 횟수는 많아봐야 N번이다. 읽기는 상관 없지만 쓰기가 극단적으로 느린 매체에 대해 외부정렬을 시도하는 경우 유용할 수 있을 것 같다. 큰 레코드의 직접 정렬도 마찬가지다.

3. 순차적으로 정렬이 된다.

예를 들어, 프로그램이 로딩되면 맨 먼저 보이는 화면은 가장 처음의 항목들을 보여주기 마련이다. 선택정렬을 이용하면 자료의 가장 처음부터 순서대로 정렬되기 때문에 빠른 로딩에 도움이 될 것 같다. 이건 내가 만든 그림으로 표시해주는 프로그램을 봐도 알 수 있다.


내가 이걸 구현할 때 문득 이중 루프 중 안쪽의 루프의 순회방향을 바꿔주면 선택정렬에도 안정성이 생기지 않을까 생각해봤다.

하지만 다시 잘 생각해보니 교환하는 요소는 안정성을 유지할 수 있어도, 교환 당하는 요소(최소값이 아닌 요소)는 안정성을 보장 못하더라.


3. 삽입 정렬

 Insertion sort


근데 교재에 예제코드 있는거 a[j-1] > t && j > 0 이거 Access violation걸릴 수 있는 거 아닌가 ㅡㅡ?

쇼트 서키트를 쓴다 해도 앞뒤 순서 좀 바꿔야 할 것 같은데, 딱히 에러는 안 나는게... 뭐지.


교환이 많음에도 별로 선택정렬에 비해 성능이 뒤지지 않는 건... 최악의 경우가 아닌 한 끝까지 밀어넣을 필요가 없어서겠지.

게다가 연결 리스트를 쓰면 정말 교환이 N번이 되고.


이름

아무 값이나 적절한 위치에 '삽입'해서 삽입정렬인가 보다.


방법

내 나름 설명: 2번째 원소부터 고른다. 그러고 첫번째 원소까지 탐색해서 정렬상 맞는 위치로 옮겨준다. 그러고 이전에 골랐던 원소가  아닌 다음 원소로 가서 반복한다.


특징

1. 간단하고 느리다. 안정성이 있다. 메모리 사용은 O(1)이다. 

2. 소요시간은 아마도 O(N²), Ω(N). 선택 정렬보다 교환을 많이 한다.

대신, 이미 정렬된 자료에 대해서는 최소한의 검산만한다. 그러므로 어느정도 정렬된 배열의 경우 효과가 좋다.

반대로, 역순의 경우 최악의 경우가 된다. N(N-1)/2번 비교·교환을 하게 된다. 이러면 오히려 선택정렬이 낫다.

3. 그래서 난수 배열의 경우 선택 정렬보다는 더 좋다. (경우에 따라선 더 느릴 수도 있지만 대체로.)

삽입정렬은 입력자료에 굉장히 민감하다. 반대로 말하면 선택정렬은 둔감하다.

4. 교환을 많이 하기 때문에, 내부정렬과 간접정렬에 필요하다. 그게 아니면 그걸로 바꿀 필요가 있다.


최적화

1. 보초sentinel를 사용하기. 자료의 첫번째 항목에 -1같이 보장되는 최소값을 넣어주면 내부 루프 조건에서 j > 0을 뺄 수 있다.

2. 이진검색 도입. 어느 기준점 이전의 자료들은 이미 정렬된 상태이기 때문에 검색을 사용해 더 빨리 끼울 곳을 찾을 수 있다.



4. 거품 정렬

 Bubble sort


일반적으로 worst의 정렬이다. 


이름

교환을 하는 모습이 뽀글거리는 거품이 이동하는 것 같다고 해서 거품정렬이라는 것 같다. 바로 다음 원소와 스왑하니까.


방법

현재 원소와 다음 원소를 정렬한다. 그러고 현재 원소를 다음 원소로  잡고 계속 반복한다. 끝까지 하면 맨 마지막 원소는 최대값이다. 그거 빼고 처음부터 반복한다.


특징

1. 간단하고 일반적으로 가장 안 좋다. 안정성이 있다. 메모리 사용은 O(1)이다.

2. 소요시간은 O(N²). 하지만 교환하는 연산이 스왑 그대로라서 한 2.5상수배는 해 주는 것 같다. 최적화를 넣으면 Ω(N)이 되기는 한다.

3. 진보형태로 쉐이커정렬이 있다. 양쪽으로 오가면서 정렬을 한 댄다.

4. 단순 연결 리스트에서 적용 가능하다...


최적화

flag넣기. 대충 정렬을 하기 때문에 막판에 와서 이미 정렬이 다 되어 있을 수 있다. 그때 flag를 쓰면 더 이상의 연산을 막을 수 있다.



4. 쉘 정렬

 Shell sort

삽입정렬이 입력자료에 민감하다는 단점을 극복한 정렬이다. 기본적으로 삽입정렬을 쓴다. (꼭 안 쓰고 딴 거 써도 쉘 정렬로 치는 듯 하다.)


이름

알고리즘의 창시자 도널드 셸의 이름을 따서 정해졌다. (위키참조)

근데 쉘이라고 부르는게 습관이 됐는데 이거 어쩌나. 상관 없겠지 뭐.


방법

원소를 띄엄띄엄 간격을 두고 골라 부분집합 여러개로 나눈다. (이건 너무 요약적이므로 누군가 이걸 이해하려고 읽는 사람들은 다른 글을 참조 바람) 그걸 정렬하고, 간격을 줄여 반복한다. 결국 마지막은 간격0, 일반정렬로 끝난다.


특징

1. 메모리 사용이 O(1)면서 빠르다. 하지만 안정성이 없다.

2. 시간복잡도는 계산하기 까다롭다. 이유는 간격을 어떻게 두느냐에 따라 시간이 달라지기 때문.

일반적으로 의 값을 가진다고 한다. 최악의 경우 자체도 역순이 아니라 랜덤한 자료에 있다.


최적화

위에서 나오다시피 간격에 따라 쉘 정렬의 성능이 달라진다. 교재에서 낫다고 알려진게 수열이라는데, 왜인지 알고싶었지만.. 논문이라니.

그 논문엔 쉘 정렬이 3중루프로 일반화되어 있었다.


결국 그림그리는 표현 프로그램을 만들었다. 허접하지만 시간이 들어간... 그건 다음에 올릴 거다 ㅇㅅㅇ

저작자 표시 비영리 동일 조건 변경 허락
신고

C로 배우는 알고리즘 - 복습 겸 요약 5C로 배우는 알고리즘 - 복습 겸 요약 5

Posted at 2012.11.18 21:30 | Posted in 지식저장소/읽은 책 요약


4. 재귀 호출Recursion



1. 재귀호출 서론

 


유의점

1. 물론 종료조건이 없으면 안 된다.

2. 상호 호출해서 1의 상황을 일으켜도 안 된다.


전략

1. 문제의 크기를 조금씩 줄여가는 방법. 문제의 크기가 점진적으로 줄어드는 점에서 두번째 유형과 다르다.

2. 문제의 크기를 양분하여 가는 방법. 꼭 절반이 아니어도 되며(퀵 정렬) devide and qunquer라고도 부른다.

3. 문제 자체에 점근하여 가는 방법. 트리에서 노드를 찾아갈 때 한번에 찾을 순 없다.

... 근데 난 왜 잘 구분이 안 가지. 특히 1, 2번.


예제로는 누승factorial 구하기, 피보나치 수열 구하기, 하노이의 탑이 나왔다.


2. 재귀함수를 비재귀함수로 바꾸기

 


비재귀함수로 바꿔야 하는 걸까? 이유는 함수를 부를 때마다 오버헤드, 즉 지연이 생기기 때문이다.

어차피 함수는 스택에 의해 구현되는 것에 불과하기에 이론적으로 모두 비재귀로 바꿀 수 있을 듯 하다. 스택만 구현해주면 되므로. 더 빨라지는지에 대한 문제를 제껴두면.


이 책에서는 스택을 하나만 준비해서 비재귀 함수로 변환하는 방법을 알려주었다.

재귀호출이 하나인 경우 - factorial예제

재귀호출이 둘인 경우 작업 선행 - tree preorder traverse

재귀호출이 둘인 경우 작업 중간에 - tree inorder traverse, hanoi

재귀호출이 둘인 경우 작업 마지막 - tree postorder traverse


음.. 저 예제들은 좀 복잡했다. 혼자 만들어봐야 할 것 같지만, 그냥 읽는 것으로... (어려운 것만 귀차니즘 발동인가.)

비재귀화하는 방법은 경우마다 다르다곤 하지만 공통점이 있다면 스택으로의 변수 저장과 처리작업의 선택이 관건이다.

즉, 함수 내부에서 루프를 이용해 함수역할을 구현할 때 변수요소만 적절히 바꿔주면 끝나는 것이다.

내가 그 정신에 입각해서 성능은 깡그리 무시해 버리고 형태를 유지한 채 그냥 비재귀화만 해보았다.

test.cpp

대충 만든거 (Inorder Insert하려고 큐 클래스를 사용하려다가 실패해서 난리가 났다;;)라 소스가 난장판이다. 어차피 읽을 필요도 없을 테니...

아주 억지스럽게도 while루프와 goto문가지고 재귀호출만 피했다 ㅋㅋ

물론 성능은 무진장 딸릴 거라 예상한다;;

근데, 함수 오버헤드 가지고 그렇게 비재귀화 고민하면 예제도 이미 push함수 하나로 최적화 물 건너간 게 아닐까...?

(push함수는 매크로 함수 같은 것으로 인라인화하면 해결 되긴 한다. 나름 가치는 있다.)


책은 EIP의 처리를 조건문만으로 한 것이고, 나는 switch goto문으로 한 것이 차이이다. 책이 복잡한 만큼 더 성능이 좋겠지.


나는 일반화의 방법을 따랐을 뿐이다.


나머지 예제는 그래픽쪽이 있는데 그건 구현 생략. 선 그리기와 프랙탈 그래픽에 재귀 호출이 쓰일 수 있다는 내용이다.


파일 탐색도 이미 함수 헤더가 dir.h, dos.h... 혼연C에 훌륭한 예제가 있으므로 차라리 그걸 보는 게 낫다.


저작자 표시 비영리 동일 조건 변경 허락
신고

C로 배우는 알고리즘 - 복습 겸 요약 4C로 배우는 알고리즘 - 복습 겸 요약 4

Posted at 2012.11.17 18:13 | Posted in 지식저장소/읽은 책 요약

3. 자료구조 - 스택, 큐, 트리



1. 스택

 

알다시피 선입후출형의 자료구조이다. 이것을 구현하는 걸 배열이나 연결 리스트로 할 수 있는데....

혼연C는 배열이 좋다고 하고 이 교재는 리스트가 좋다고 한다!!!

근데 난 혼연C가 옳다고 생각. 일단 구현은 쉬우니까. push()하고 pop()만 만들면 되는..

둘 다 장단점은 다 있으니까 여기서 스톱한다.


예제는 계산기. 전위식을 후위식으로 바꿔 스택에 저장한 후 계산하는 방식이다.

지금해도 만만찮지만, 예전에 한 번 만들어 본 적이 있다. 아.. 만들기 귀찮아..

근데 자료구조 풀다가 스택은 만들어 버렸다.. 동적할당을 지원하고 배열로 구현했다. 보라고 만든 건 아니다. 그냥 기념 -.-

아, 여기에 하나 주석. 왜 혼연C하고 C로.. 교재는 둘 다 스택 특이값을 -1로 잡았을까? 0으로 잡으면 안 되었을까?

나는 0으로 구현했다. 그러면 top하고 스택의 size비교가 쉽기 때문.

3-3.my_stack.cpp


2. 큐

 

큐는 스택과 달리 선입선출형이다. 이것도 역시 배열과 연결리스트로 구현할 수 있는데,  혼연C는 둘 다로 구현했다.

근데 연결리스트로 구현한 부분 중 Insert에서 큐가 커지면 어쩌려고 그러는지...

혹시 자료구조 개념만 중요한 거고 구현은 그닥 중요한 게 아닌 걸까?

설령 그렇다고 해도 구현을 하다보면 개념에 대해 더 이해가 깊어지는 경우가 있어 구현이 필요 없는 건 아니지만.. (연결리스트만 해도.. ㅡㅡ)

근데 두 교재 모두 이중연결 리스트로 구현을 했다. C로 배우는 알고리즘은 단순연결 리스트로 하면 put동작이 부자연 스럽다고 하는데, 그럼 적어도 혼연C의 구현에서는 단순 연결 리스트를 써도 되는게 아닌가 싶다.

실제로 prev가 쓰이진 않으니까... 그리고 head, tail을 유지하면서 단순연결리스트로 큐를 만드는 것도 그렇게 어렵진 않을 듯 싶다.


둘 다 예제는 없다. 넘어간다.

(사실 혼연C에서 시뮬레이션 예제가 있지만... 굳이 그것까지야;;)

데크는 STL에서 본 적이 있다. 좀 어이 없던 것은 큐가 데크의 상속 클래스 였던 것... 같은데. 나름 이유가 있겠지.


이것도 구현해보았다. 트리 층별순회에 써먹으려고 템플릿으로 만들어보려 했으나 처참하게 실패.

못 써먹었다. C++ 다 까먹은 느낌. 고등학교 교육과정 정말 필요한 걸까 ㄱ-?

3-4.my_queue.cpp


3. 트리

 

이제부터 생소해지기 시작한다. 무슨 책 먼저 볼까... (아니, 지금 어느 교재 독후감 쓰는 건데 ㅡㅡ;)


트리의 용어정의

트리: 어떠한 조건을 만족하는 노드Node와 링크Link의 집합

노드는 버텍스Vertex라고도 하며 링크는 에지Edge라고도 함.

노드는 정보를 담고 있고, 링크는 노드간의 연결을 나타냄.

경로: 트리 내에서 링크에 의해 연결된 일련의 노드의 집합. 뭐... 디렉토리 구조도 트리니까, 쉽다.

 graph와 차이점. 한 노드에서 다른 노드에 이르기까지의 경로는 단 하나밖에 없다.

부모, 자식, 조부모, 형제노드라는 표현도 있다. 족보 생각하면 쉽다.

내부노드 = 비종료노드, 외부노드 = 종료노드 = 잎

내부·외부 경로는 무슨말인지 잘 모르겠다. 나중에.


아... 오타 발견. 233p에 마지막에서 4번째 줄은 '꽉 차있는 이진 나무'가 아니라 '완전한 이진 나무'인 것같다.

다중 트리Multiway Tree: 무조건 어떤 정수 이하개수로 자식을 가지는 트리. 이진트리도 여기 속한다.

완전 이진트리Complete binary tree: 마지막 레벨 빼고 꽉 차있는 이진트리.. 라고 C로 배우는 알고리즘엔 적혀있는데!!!

혼연C를 보니, 순서대로 번호를 매겨서 빈 번호가 없으면 그게 완전이진트리다.

포화 이진트리Full binary tree: 모든 레벨이 차있다.


트리의 성질

1. 트리구조의 임의의 두 노드는 최소공통선조Least common ancestor를 갖는다.

   그 두 노드를 잇는 경로는 그 최소공통선조를 거치는 경로 하나밖에 없다.

2. N개의 노드를 갖는 트리는 N-1개의 링크를 갖는다. 노드 하나당 부모와의 링크 하나를 가지고 있고 맨 위의 root가 없으니까 N-1이 된다.

3. 이진트리의 높이(=최대 레벨)로 포함 가능한 노드 수를 나타내는 공식에서 반대의 경우도 가능하다는 것만 알아두자. 일단 답은 log₂N + 1


트리의 순회traverse

전위 순회PreOrder, 중위 순회InOrder, 후위 순회PostOrder가 있는데, 각각은 루트를 방문하는 순서로 나눈다. 모두 재귀호출로 구현가능하다.

다만 층별 순회LevelOrder는 BFS와 유사해 큐를 이용한다.


트리는 구현이 너무 다양하다고 한다. 예제는 C로.. 책에 계산기가 나왔는데, 내·외부 노드 구분이 정말로 쓰일 줄은 몰랐다...

게다가 후위식도 자유자재로 다루는 점에선 스택보다 깔끔한 것 같기도 하다.


이 트리의 순회는 다음에 나오는 재귀호출에서 예제로 많이 나오더라.

저작자 표시 비영리 동일 조건 변경 허락
신고

C로 배우는 알고리즘 - 복습 겸 요약 3C로 배우는 알고리즘 - 복습 겸 요약 3

Posted at 2012.11.14 18:07 | Posted in 지식저장소/읽은 책 요약

제 3장. 자료구조 - 배열, 연결 리스트



1. 자료구조란..

 

앞에서 구조화 프로그래밍이란 개념을 배웠다고 한다. 생각해보니 내가 본 옛날 C코드 중에 코드와 데이터를 구분하지 않고 실행하는 것 같은 소스가 있었다. 아마 비구조적 프로그래밍이 이런 것이 아닐까 싶은데, 마침 찾을 수 있었으니 첨부한다.


옛날 C소스


요즘의 C소스와 비교해보면 딱 감이 올 것이다. 구조적이라는 개념에 대해서.


이 구조적이라는 개념을 성립시키기 위해 저 혼란스러운 코드를 2가지로 분리할 필요가 있다고 한다. 바로 알고리즘(코드)과  자료구조(데이터).


이번엔 자료구조를 먼저 살펴보기로 한다.


2. 배열

 Array

C에서의 배열의 정의는 "연속된 메모리 공간을 차지하는 같은 데이터형들의 집합"이라고 한다.

꼭 C뿐만 아니라 다른 프로그래밍 언어를 둘러보아도 "연속된 같은 데이터"들이란 것은 바뀌지 않을 듯 하다.

파이썬은 얼핏보면 다른 데이터를 집어넣는 것 같아도 Py_Object라는 단위로 본다면 같은 데이터로 칠 수 있지 않은가.

맨 처음 맞닥뜨리는 자료구조이고 그만큼 직관적이고 단순한 구조로 이루어져 있다.

배열이 C에서 가지는 특성은 앞서 나온 "연속된 메모리 공간"을 차지한다는 것과, 배열의 첨자 검사를 안 한다는 것이 있다.


나머지는 C의 세부적인 문법에 관한 사항 (배열 인자로 넘기는 방법, 문법적 특징 등등...)이업고, 배열의 사용 예를 보자.


행렬

행렬의 각 원소의 자료형은 같다. 꼭 배열로 구현할 필요는 없겠지만, 왜 배열로 구현을 했을까?

배열의 특성을 짚어볼 필요가 있다. C에서의 기본배열은 고정된 크기를 가자고, 원소의 추가·제거가 힘들다. 행렬의 크기가 변하는 경우는 없으므로 적합하다.

책에서는 행렬을 자료구조로, 행렬의 곱하기 연산을 알고리즘으로 예제를 두었다


미로, 우선법

이것도 내가 직접 작성해보는 것은 생략할 것이다. (지금보니까 옛날에 정렬까지 예제를 직접 타이핑 해 봤었다;; 다시 공부해서 효과 얻으려면 직접 짜봐야 하는 건가..)

미로도 배열을 자료구조로 채택하는 것은 좋다. 하지만 우선법의 알고리즘은 가장 최선은 아니다.

책이 오래돼서 하드웨어 자원을 아끼는 것을 미덕으로 삼아선지는 몰라도, 최단경로를 찾는 방법은 BFS가 가장 적당하다.

순서대로, 책의 예제부터 보자.

예제를 실행하면 1이 이동한다. 처음은 우선법을 따른다. 두번째 최단경로 이동부분에서 미로가 연결되지 않은 부분에서 경로 단축을 못 하는 문제가 있는 걸 알 수 있다.

기존 알고리즘에서 개선시키는 방법은, 좌선법 추가정도가 있다. 더 이상 개선하려면 복잡해질 테니 속 편하게 BFS를 쓰는게 나을 것 같다.



3. 연결 리스트

 Linked iist


배열과 달리 연결 리스트부터는 C가 기본지원하지 않기 때문에 직접 구현해야 한다. (STL은 빼자)

개념은 알고있었고, 구현을 해보기로 했다.

개념.. 장점은 메모리 소모가 동적이고, 삽입, 삭제가 빈번한 자료에 유용하다.

단점은 검색하기 힘들다. (순차검색만 되니)


단순 연결 리스트

이거 구현은 혼연C교재가 최곤 것 같다.

만든 다음 비교해 봤더니 내가 짠 코드는

1. Deleteall함수에 NULL체크를 중복했다.

2. Insert_after, Delete_after에 NULL체크를 추가로 했다.

이런 차이점이 있었다.


짜면서 쓴 주석

// 단순 연결 리스트에서 head가 가리키는 노드는 쓰지 않는 게 좋다. 일관성을 위해서라는데, 살펴보자.

// 일단 head가 가리키는 값도 쓰려면 insert_after나 Delete_after에 NULL을 처리하는 부분이 반드시 필요하다.

// 쓰지 않아도 safe-coding을 위해 NULL처리 구문은 그래도 들어가겠지만, 논리적으로는 필요가 없다.

// 그리고 head가 가리키는 값은 head를 직접 조작해야 제거할 수 있기 때문에, C++에서는 제거에 포인터를 넘겨줄 것을,

// 포인터에 대한 레퍼런스를 넘겨주는 것으로 약간 비효율적이 된다.

// 결론은, 앞의 노드를 이용하는 모든 동작에서 추가적인 코드가 필요해진다. (head는 예외니까.)

// 여기선 head노드는 쓰지 않음과 동시에 현재 노드대신 이전노드를 쓰는데, 그걸 하려면 차라리 더블 링크드 리스트를 쓰는게 낫기 때문이라고 생각해서다.


Find_node()

// 값을 찾은 노드 바로 이전 노드 주소를 리턴합니다. 검색할 때 목적은 존재 여부확인 or 삭제니까...

// 결과적으로 Find_Node를 쓸 때 Get_before가 필요 없습니다.

// p부터가 아니라 p다음부터 찾습니다. 계속 검색할 때 유용하고, 단순 연결 리스트 특성 때문이기도 합니다.

// head부터 검색할 땐 문제 없지만, 도중부터 검색하려면 추가적인 코드가 필요하겠네...


교재에 있는 C책하고 구현이 좀 다르게 되었는데, 그 이유가 위의 주석이다.


다음은 실습한 소스


my_linkedlist.cpp


이중 연결 리스트

짜면서 쓴 주석

난감한 점. 구현 방식이 2가지 있다.

하나는 직접 자료를 다루게 하는 것. head가 NULL일 때도 예외처리로 노드 하나 만들어주고 하는 방식.

다른 하나는 단순 연결 리스트처럼 head지정 노드를 접근 불가하게 하기.

전자의 방식은 직관적, 원소 0개 가능이라는 장점이 있고, 헤드의 왼쪽에도 노드 삽입이 가능하다.

후자의 방식은 head가 유지되고(=원소 수 세기가 쉽다), 구현이 간단하다.

혼연C/C++을 보니까 후자로 구현했던데... 헤드의 왼쪽에 삽입할 경우 무시해 버린다.

... 합리적이었다. 역시. 알아서 조심하면 되는건가.

그럼, 혼연을 참고로해서 다시 만들자.

혼연에는 AppendNode(), GetListCount(), GetNodeIndex(), FindNodeByIndex()도 있었다.

내가 부족했던 점은

1. Insert_before을 prev->Insert_after로 간단히 구현할 수 있는 걸 비슷한 코드 2개를 만들어버렸다.

   원인을 꼽자면, 저 2가지 방식 중 하나를 명확히 정하지 않고 생각없이 짠 것이겠지.

2. Ordered_Insert만들 때 많이 해멨다. 너무 최적하하려다가 ㄱ-.


my_doublelinkedlist.cpp


(이번에는 자료구조 정의는 많이 안 쓰고, 내 생각만 적었는데, 공개하게 되면 그 때 정의를 적든지 하자.)

그리고 예제는 단순연결리스트의 경우 명함관리가 있었는데, 순차검색만 되는 리스트로 그걸 구현할 필요를 못 느껴서 패스.

이중연결리스트의 경우 텍스트 뷰어가 있는데, 이건 한 번 시도할 만 한 것 같다.


...근데 함수의 실제적 구현부분에서 케케묵은 냄새가 풍긴다. 아예 새로 구현할 거니까 상관은 없지만,

filename[13](8.3 DOSname)이라든가 textattr... WinAPI중에 그런 함수가 있을 진 몰라도, 일단은 이건 불가다.

그리고 \r\n을 \n\r도 된다고 하다니, 커리지 리턴과 라인피드가 도스 시절엔 정말 각자 기능이 있었던건가.


텍스트뷰어를 짜 보았다. 아 코딩 속도가 넘 느리다.. ㅠㅠ

너무 최적화 생각해서 그런가. 그래 놓고도 미완성스러운데.

만들어 놓고 혼연C의 JusoList예제를 보니... 아. FirstNode, LastNode는 그럴 때 쓰라고 있는 거구나.. 하는 생각이 들었다 ㅡㅡ;

엉엉 난 또 삽질한 거였어...


더 수정하기 귀찮아서 일단 소스는 올려둔다. 특징은 아무리 큰파일이라도 부분만 읽어서 보여 줌.

하지만 한글출력과 정상동작 보장 불가. (로직...)


3-2-1_my_textviewer.cpp



저작자 표시 비영리 동일 조건 변경 허락
신고