문제

해커랭크 사이트의 문제 중 하나 The Tree of Life 를 풀다가 나온 입력 처리입니다.

위의 문제는 이진 트리가 LISP의 S-expression 형식으로 입력됩니다. 이진 트리의 각 노드 값은 . 이나 X 이고, 브랜치는 괄호로 묶어 왼쪽/자신/오른쪽 순으로 표시됩니다. 예를 들어(X . (. X .))는 아래와 같은 트리를 나타냅니다.

   .
  / \
 X   X
    / \
   .   .

문제 자체의 난이도보다 이를 하스켈로 읽어들이는 것을 더 어렵게 느끼는 분들도 있을 것 같습니다. 이진 트리가 재귀 자료구조이다보니 입력도 재귀적으로 처리해야 하기 때문입니다. 단순히 공백으로 나누는 식으로 처리하기 어렵죠.

하지만 하스켈하면 Parsec이 유명하잖아요? 이번에 간단한 파싱이 정말 간단하게 되는지 살펴보겠습니다.

BinTree 자료형

이진 트리를 BinTree라고 하면 String -> BinTree의 함수가 필요합니다. read 함수는 Read 클래스를 구현하는 타입을 읽어주기 때문에 BinTree에 Read 인스턴스를 붙여줍니다.

data BinTree = Leaf Char | Branch BinTree Char BinTree

instance Read BinTree where
  ...

Read 클래스

Read 클래스는 readsPrec과 readPrec의 두 함수 중 하나를 구현하면 됩니다. prec은 우선순위(precedence)를 의미하고 우선순위는 필요에 따라 괄호를 하거나 할 경우 필요합니다. 다행히 이 문제의 이진 트리는 항상 괄호를 포함하고 있으니 잠깐 무시하기로.. 그럼 readsPrec과 readPrec 둘 중에서 GHC가 추천하는 건 readPrec이라고 하니 readPrec을 살펴보겠습니다.

readPrec :: ReadPrec a
newtype ReadPrec a = P (Prec -> ReadP a)
type Prec = Int

ReadPrec은 ReadP를 우선순위 고려할 수 있게 래핑해놓은 타입입니다.lift :: ReadP a -> ReadPrec a를 이용하면 리프팅할 수 있습니다. 대부분의 Parsec 함수들은 ReadP 로 구현되어 있으니 이를 이용하여 구현할 수 있는데...

여기서 중요한건 ReadP와 ReadPrec이 Functor/Applicative/Monad/MonadPlus/Alternative의 인스턴스라는 점이에요.

Read / ReadS / ReadP / ReadPrec

여러가지 타입/함수들이 나와서 헷갈릴 수 있으니 한번 정리하고 넘어가볼게요.

class Read a
  readPrec :: ReadPrec a

read :: (Read a) => String -> a

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

readP_to_S :: ReadP a -> ReadS a

data ReadP a
data ReadPrec a

lift :: ReadP a -> ReadPrec a

우리가 부르고 싶은 함수는 read 입니다. read를 사용하려면 Read 클래스의 인스턴스가 있어야 하죠. 이 인스턴스를 구현할 때 readPrec 함수를 구현해야 하고, 그 함수는 ReadPrec 타입입니다. ReadPrec 타입은 ReadP 타입을 lift하여 얻을 수 있어요. ReadP가 바로 Parser Combinator입니다. ReadP 파서를 실행시키려면 ReadS (함수타입)로 변환해줘야 합니다.

예를 들어 가장 단순한 get :: ReadP Char 파서는 글자 하나만 읽는 파서입니다. 실행시키려면..

> readP_to_S get "abc"
[('a',"bc")]

BinTree의 Read 인스턴스

Leaf이거나 Branch일수 있습니다. (<|>)로 합칠 수 있죠. ReadP의 단위 파서 함수들 중에서 char만 이용해도 이 문제는 풀수 있겠네요.

import Text.Read (readPrec, lift)
import Text.ParserCombinators.ReadP (ReadP, char)
import Control.Applicative

data BinTree = Leaf Char | Branch BinTree Char BinTree deriving Show

instance Read BinTree where
  readPrec = lift tree

tree :: ReadP BinTree
tree = Leaf <$> node
   <|> Branch <$ char '(' <*> tree <* char ' ' <*> node <* char ' ' <*> tree <* char ')'

node :: ReadP Char
node = char 'X' <|> char '.'

t :: BinTree
t = read "(X . (X . X))"

main :: IO ()
main = print t

이진 트리를 Generic하게 만든다면 아래와 같이 바꿀 수 있습니다.

import Text.Read (readPrec)
import Text.ParserCombinators.ReadPrec (ReadPrec, lift)
import qualified Text.ParserCombinators.ReadP as P (char)
import Control.Applicative ((<|>))

data BinTree a = Leaf a | Branch (BinTree a) a (BinTree a) deriving Show

instance (Read a) => Read (BinTree a) where
  readPrec = Leaf <$> readPrec
         <|> Branch <$ char '(' <*> readPrec <* char ' ' <*> readPrec <* char ' ' <*> readPrec <* char ')'

char :: Char -> ReadPrec Char
char ch = lift (P.char ch)

t :: BinTree Int
t = read "(1 2 (3 4 5))"

main :: IO ()
main = print t

공백을 좀더 robust하게 처리하고 싶다면 Lex 모듈을 이용할 수 있습니다.

import Text.Read (readPrec)
import qualified Text.Read.Lex as L (expect, Lexeme(..))
import Text.ParserCombinators.ReadPrec (ReadPrec, lift)
import Control.Applicative ((<|>))

data BinTree a = Leaf a | Branch (BinTree a) a (BinTree a) deriving Show

instance (Read a) => Read (BinTree a) where
  readPrec = Leaf <$> readPrec
         <|> Branch <$ expect (L.Punc "(") <*> readPrec <*> readPrec <*> readPrec <* expect (L.Punc ")")

expect :: L.Lexeme -> ReadPrec ()
expect l = lift $ L.expect l

t :: BinTree Int
t = read "(1 2    (  3 4 5))"

main :: IO ()
main = print t

GHC.Read의 paren을 이용하면 더 간단합니다.

import Text.Read (readPrec)
import Control.Applicative ((<|>))
import GHC.Read (paren)

data BinTree a = Leaf a | Branch (BinTree a) a (BinTree a) deriving Show

instance (Read a) => Read (BinTree a) where
  readPrec = Leaf <$> readPrec
         <|> paren (Branch <$> readPrec <*> readPrec <*> readPrec)

t :: BinTree Int
t = read "(1 2    (  3 4 5))"

main :: IO ()
main = print t

마지막

문제가 요구하는 입력을 처리하는 코드는 아래와 같습니다. 이정도면 매우 간단하지 않나요?

import Text.Read (readPrec, lift)
import Text.ParserCombinators.ReadP (char, skipSpaces)
import Control.Applicative ((<|>))
import GHC.Read (paren)

data BinTree a = Leaf a | Branch (BinTree a) a (BinTree a) deriving Show

instance (Read a) => Read (BinTree a) where
  readPrec = Leaf <$> readPrec
         <|> paren (Branch <$> readPrec <*> readPrec <*> readPrec)

data Cell = On | Off deriving Show

instance Read Cell where
  readPrec = lift $ skipSpaces >> (On <$ char '.' <|> Off <$ char 'X')

t :: BinTree Cell
t = read "(. X    ( X . .))"

main :: IO ()
main = print t