do notation:
> openTagParser :: Parser String
> openTagParser = do list space
> is '<'
> tag_name <- xmlTagNameParser
> is '>'
> return (head (words tag_name))
Similarly for a closing tag:
> closeTagParser :: Parser String
> closeTagParser = do list space
> is '<'
> is '/'
> tag_name <- xmlTagNameParser
> is '>'
> return tag_name
>
The text inside a basic XML structure can be any ASCII character
except for an opening bracket.
> xmlTextFieldParser :: Parser String
> xmlTextFieldParser = list (satisfy (\c -> isAscii c && (c /= '<')))
The simplest XML structure that we will parse is a balanced pair of tags
with some text inbetween, such as: <foo>hey there</foo>.
> xmlTextElementParser :: Parser [(String, String)]
> xmlTextElementParser = do open_tag_name <- openTagParser
> text_body <- xmlTextFieldParser
> close_tag_name <- closeTagParser
> if open_tag_name /= close_tag_name then failed else return [(close_tag_name, text_body)]
The other kind of structure that we can parse is a pair of
balanced tags with some list of text bits inside, such as:
<foo><bar>bar value</bar><meh>meh value</meh></foo>
The top level definition of the parse is thus:
> xmlToTagValueList :: Parser [(String, String)]
> xmlToTagValueList =
> do open_tag_name <- openTagParser
> body <- many1 (xmlTextElementParser ||| xmlToTagValueList)
> close_tag_name <- closeTagParser
> if open_tag_name /= close_tag_name then failed else return ((close_tag_name, "->"):(concat body))
For testing purposes we will try to parse the input file and then report the number of
parsed XML-like elements.
> main = do args <- getArgs
> x <- readFile (head args) :: IO String
> let x' = parse (list xmlToTagValueList) x
> print (length (head (snd (fromJust x'))))
For testing I will use a file with one line repeated inside a
<blah> block. The file input10.txt has 10 lines in the
inner block:
<blah>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
<hello> do de dah</hello> <foo> <bar>bar</bar> </foo>
</blah>
Here are some run times on a lightly loaded 2Ghz Xeon running Ubuntu 10.10
with GHC 6.12.1, and the binary compiled with "ghc -O --make". This parse is clearly impractical if
parsing 30 lines of text will take over 1.5 hours:
| Nr lines | time (seconds) |
|---|---|
| 1 | 0.116 |
| 10 | 0.015 |
| 15 | 0.468 |
| 20 | 16.166 |
| 25 | 466.365 |
| 30 | > 5000 |
The paper by Swierstra and Duponcheel pretty much sums things up:Although the idea of programming with combinators is quite old, the design of combinator libraries has been profoundly infuenced in recent years by Wadler's introduction of the concept of a monad into functional programming[Wad90, Wad92, Wad95]. We shall discuss monads much more fully in the next section, but for now, suffice it to say that a monad is a kind of standardised interface to an abstract data type of `program fragments'. The monad interface has been found to be suitable for many combinator libraries, and is now extensively used. Numerous benefits flow from using a common interface: to take just one example, Haskell has been extended with special constructions to make the use of monads particularly convenient.
It is therefore a matter for some concern when libraries emerge which cannot, for fundamental reasons, use the monad interface. In particular, Swierstra and Duponcheel have developed a very interesting library for parsing LL-1 grammars[SD96], that avoids a well-known inefficiency in monadic parsing libraries by combining the construction of a parser with a `static analysis' of the program so constructed. Yet Swierstra and Duponcheel's optimisation is incompatible with the monad interface. We believe that their library is not just an isolated example, but demonstrates a generally useful paradigm for combinator design that falls outside the world of monads. We shall look more closely at their idea in section 3. Inspired by Swierstra and Duponcheel's library, I sought a generalisation of the monad concept that could also offer a standardised interface to libraries ofthis new type. My proposal, which I call arrows, is the subject of this paper. Pleasingly, the arrow interface turned out to be applicable to other kinds of non-monadic library also, for example the fudgets library for graphical user interfaces [CH93], and a new library for programming active web pages. These applications will be described in sections 6 and 9.
While arrows are a little less convenient to use than monads, they have significantly wider applicability. They can therefore be used to bring the benefits of monad-like programming to a much wider class of applications.
To learn about arrows in Haskell, go here: http://www.haskell.org/arrows/.As soon as one starts to use normal combinator based parsers, disappointments arise. The parsers constructed may be unexpectedly slow, and since combinators are usually used to describe non-deterministic parsers, they do not perform any form of error-reporting, let alone error-recovery. Even the smallest mistake in the input may lead to a lengthy parsing process which finally produces an empty list of successful parses, with no clue as to where where the mistake is located.