Parse BinaryTree with (Read a, Show a)

Question

I am having a little trouble on how to start this problem. I am supposed to parse a string representation of a binary tree and check whether the contents of a leaf have valid letters and if they do then create the tree else return "" for failed parsing all without deriving (Show,Read)

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


data letters = A | B | C | D | E | F | G deriving (Show, Eq, Enum, Bounded, Read)

lett = [(A)..(G)]
str = "Branch (Leaf A) (Branch (Branch (Leaf A) (Leaf C)) (Leaf D))"

parse:: (Read a, Show a) => [a] -> String ->  BinaryTree  a

Using a typical parser library I could use something along the lines of

parseTree = do{item; symb "Leaf"; x <- string; return Leaf (read x)} +++ {item; symb "Branch"; item;x <- parseTree; item; item; y <- parseTree; item; return (Branch x y)}

The type constraint of (Read a, Show a) confuses me as I am unsure how I would handle the case of going through a leaf or branch.

You can use deriving (Show, Read) in your data BinaryTree, and thne it will make a parser itself. — Willem Van Onsem
There is something not entirely correct with the function code, it should be return (Branch x y) for example. — Willem Van Onsem

Simon Shine Simon Shine · Accepted Answer · 2019-10-31T16:08:54

As Willem says, you can derive Read to get this function for free:

data Letter = A | B | C | D | E | F | G
  deriving (Show, Eq, Enum, Bounded, Read)

data BinaryTree a = Leaf a | Branch (BinaryTree a) (BinaryTree a)
  deriving (Eq, Show, Read)

t :: BinaryTree Letter
t = Branch (Leaf A) (Branch (Branch (Leaf A) (Leaf C)) (Leaf D))

Trying this:

λ> t == read (show t)
True

create the tree else return "" for failed parsing all without deriving (Show, Read).
parseTree = do{ item; symb "Leaf"; ... +++ ... }

I'm not sure what "" means in the context of reading a binary tree from a string: According to your definition of binary tree, trees cannot be empty, since even Leaf contains at least one letter. So maybe you're looking for a function String -> Maybe (BinaryTree Letter).

Since your reluctance to use derived Show and Read instances, this must be an exercise in writing a parser. You could structure a recursive-descent parser in the following way:

parseLetter :: String -> Maybe (Letter, String)
parseLetter s = ...

parseTree :: String -> Maybe (BinaryTree Letter, String)
parseTree s
  | "Leaf " `isPrefixOf` s = ...
  | "Branch " `isPrefixOf` s = ...
  | otherwise = Nothing

Here the (..., String) is the left-over of the string being parsed that isn't consumed by a sub-parser. E.g. in parsing Branch (Leaf A) (Leaf B), when parseLetter has parsed A, it may return (A, ") (Leaf B)") for its caller.

Note, however, that getting something of comparable quality to deriving Read requires being pretty flexible with regards to whitespace and parentheses:

λ> read "Branch ( Leaf A)(  Branch (  Leaf B )   ((Leaf C) )   ) " :: BinaryTree Letter
Branch (Leaf A) (Branch (Leaf B) (Leaf C))

I am unsure how I would handle the case of going through a leaf or branch

Going through a leaf means parsing a single letter.

Going through a branch means calling upon the parser recursively.

You may want to use a more efficient and ergonomic parsing library, like what Text.Read exposes (it even contains an example of reading a tree type), or you might want to use a parser combinator framework like Megaparsec or ReadP.

Parse BinaryTree with (Read a, Show a)

1 Answers