Haskell Tutorial Code Error

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Haskell Tutorial Code Error

Pete Ryland
Hi,

Sorry to post to a list, but there are no other contact addresses on
the haskell.org site or in the tutorial itself.  Any replies, please
also CC me as I do not subscribe to any haskell.org lists.

I noticed an error in the Haskell Tutorial in section 8.3.  The code
for the Tree parser will not work.  Specifically, the following is
broken:

readsTree               :: (Read a) => ReadS (Tree a)
readsTree s             =  [(Branch l r, x) | ("<", t) <- lex s,
                                             (l,   u) <- readsTree t,
                                             ("|", v) <- lex u,
                                             (r,   w) <- readsTree v,
                                             (">", x) <- lex w         ]
                          ++
                          [(Leaf x, t)     | (x,   t) <- reads s       ]

It will not read a string like "<<1|2>|3>" because of the "<<" which
the lexer will see as one token.  Here is another implementation:

 showsTree               :: (Show a) => Tree a -> ShowS
 showsTree (Leaf x)      =  ("Leaf " ++) . shows x
 showsTree (Branch l r)  =  ("Branch (" ++) . showsTree l . (") (" ++)
                                           . showsTree r . (')':)

 readsTree               :: (Read a) => ReadS (Tree a)
 readsTree s             =  [(Branch l r, v) | ("Branch", t) <- lex s,
                                              (l, u) <- readsTree t,
                                              (r, v) <- readsTree u   ]
                           ++
                           [(Leaf x, u)     | ("Leaf", t) <- lex s,
                                              (x, u) <- reads t       ]
                           ++
                           [(x, v)          | ("(", t) <- lex s,
                                              (x, u) <- readsTree t,
                                              (")", v) <- lex u     ]

 instance Show a => Show (Tree a) where
    showsPrec _ x = showsTree x

 instance Read a => Read (Tree a) where
    readsPrec _ s = readsTree s

This is almost equivalent to the derived one, but will accept strings
like "Branch Leaf 3 Branch Branch Leaf 1 Leaf 2 Branch Leaf 5 Leaf 4"
(that is, without the parentheses).

Regards,
Pete