Tag Archives: parsing

Competitive programming in Haskell: parsing with an NFA

Posted on May 24, 2023 by Brent

In my previous post, I challenged you to solve Chemist’s Vows. In this problem, we have to decide which words can be made by concatenating atomic element symbols. So this is another parsing problem; but unlike the previous problem, element … Continue reading →

Posted in competitive programming, haskell | Tagged , , , , | 12 Comments

Competitive programming in Haskell: building unordered trees

Posted on May 22, 2020 by Brent

In my previous post I challenged you to solve Subway Tree System, which encodes trees by recording sequences of steps taken away from and towards the root while exploring the whole tree, and asks whether two such recordings denote the … Continue reading →

Posted in competitive programming, haskell | Tagged , , , , , , , , , | 26 Comments

Competitive Programming in Haskell: reading large inputs with ByteString

Posted on October 12, 2019 by Brent

In my last post in this series, we looked at building a small Scanner combinator library for lightweight input parsing. It uses String everywhere, and usually this is fine, but occasionally it’s not. A good example is the Kattis problem … Continue reading →

Posted in haskell | Tagged , , , , , | 3 Comments

Competitive Programming in Haskell: Scanner

Posted on May 22, 2019 by Brent

In my previous post I explored solving a simple competitive programming problem in Haskell. The input of the problem just consisted of a bunch of lines containing specific data, so that we could parse it using lines and words. There … Continue reading →

Posted in haskell | Tagged , , , , | 13 Comments

Parsing context-sensitive languages with Applicative

Posted on January 5, 2012 by Brent

Many parser combinator libraries in Haskell (such as parsec) have both a Monad interface as well as an Applicative interface. (Actually, to be really useful, you also need MonadPlus along with Monad, or Alternative along with Applicative, in order to … Continue reading →

Posted in haskell | Tagged , , , , , , | 11 Comments