Parsing
Algorithms
Logic
Strings
Monads
Data Structures
Functional Programming
http://www.willamette.edu/~fruehr/haskell/seuss.html
A parser for a thing
Is a function from a string
To a list of pairs
Of things and strings!
This monadic parser is missing many basic functions and several important typeclass instances.
{-# LANGUAGE DeriveFunctor, TupleSections #-}
module MonadicParsing where
newtype Parser a = Parser { runParser :: String -> [(a, String)] }
deriving Functor
instance Monad Parser where
return a = Parser $ return . (a,)
Parser p >>= f = Parser $ \s -> concatMap (uncurry (runParser.f)) $ p s
import Data.Char
import Data.List
import Test.Hspec
import MonadicParsing (Parser (..))
main :: IO ()
main = hspec spec
takeParser :: Int -> Parser String
takeParser l = Parser $ \s -> [(take l s, drop l s)]
digitParser :: Parser Int
digitParser = Parser $ \s -> [ (digitToInt a, drop 1 s) | a <- take 1 s, isDigit a ]
repeatParser :: Show a => a -> Parser a
repeatParser a = Parser $ \s -> [(a, drop l s) | t `isPrefixOf` s]
where
t = show a
l = length t
spec :: Spec
spec = do
describe "monad instance" $ do
it "left identity" $ runParser (return 3 >>= takeParser) "hello"
`shouldBe` runParser (takeParser 3) "hello"
it "right identity" $ runParser (takeParser 9 >>= return) "world"
`shouldBe` runParser (takeParser 9) "world"
it "associativity" $ runParser ((digitParser >>= repeatParser) >>= takeParser) "99 luftballons"
`shouldBe` runParser (digitParser >>= (\x -> repeatParser x >>= takeParser)) "99 luftballons"