해커랭크 사이트의 문제 중 하나 The Tree of Life 를 풀다가 나온 입력 처리입니다.
위의 문제는 이진 트리가 LISP의 S-expression 형식으로 입력됩니다.
이진 트리의 각 노드 값은 . 이나 X 이고,
브랜치는 괄호로 묶어 왼쪽/자신/오른쪽 순으로 표시됩니다.
예를 들어(X . (. X .))는 아래와 같은 트리를 나타냅니다.
.
/ \
X X
/ \
. .
문제 자체의 난이도보다 이를 하스켈로 읽어들이는 것을 더 어렵게 느끼는 분들도 있을 것 같습니다. 이진 트리가 재귀 자료구조이다보니 입력도 재귀적으로 처리해야 하기 때문입니다. 단순히 공백으로 나누는 식으로 처리하기 어렵죠.
하지만 하스켈하면 Parsec이 유명하잖아요? 이번에 간단한 파싱이 정말 간단하게 되는지 살펴보겠습니다.
이진 트리를 BinTree라고 하면 String -> BinTree의 함수가 필요합니다.
read 함수는 Read 클래스를 구현하는 타입을 읽어주기 때문에 BinTree에 Read 인스턴스를 붙여줍니다.
data BinTree = Leaf Char | Branch BinTree Char BinTree
instance Read BinTree where
...Read 클래스는 readsPrec과 readPrec의 두 함수 중 하나를 구현하면 됩니다. prec은 우선순위(precedence)를 의미하고
우선순위는 필요에 따라 괄호를 하거나 할 경우 필요합니다. 다행히 이 문제의 이진 트리는 항상 괄호를 포함하고 있으니 잠깐 무시하기로..
그럼 readsPrec과 readPrec 둘 중에서 GHC가 추천하는 건 readPrec이라고 하니 readPrec을 살펴보겠습니다.
readPrec :: ReadPrec a
newtype ReadPrec a = P (Prec -> ReadP a)
type Prec = IntReadPrec은 ReadP를 우선순위 고려할 수 있게 래핑해놓은 타입입니다.lift :: ReadP a -> ReadPrec a를 이용하면
리프팅할 수 있습니다. 대부분의 Parsec 함수들은 ReadP 로 구현되어 있으니 이를 이용하여 구현할 수 있는데...
여기서 중요한건 ReadP와 ReadPrec이 Functor/Applicative/Monad/MonadPlus/Alternative의 인스턴스라는 점이에요.
여러가지 타입/함수들이 나와서 헷갈릴 수 있으니 한번 정리하고 넘어가볼게요.
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")]
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 tGHC.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