CODEWITHSUNDEEP
parsinghaskell
user2820579
user2820579

Reputation: 3451

Example of simple parsers in haskell

I have the following parsers functions 

import Data.Char
type Parser a = String -> [(a,String)]

return' :: a -> Parser a
return' v = \inp -> [(v,inp)]

failure :: Parser a
failure = \inp -> []

item :: Parser Char
item = \inp -> case inp of
         [] -> []
     (x:xs) -> [(x,xs)]

parse :: Parser a -> String -> [(a,String)]
parse p inp = p inp

parse :: Parser a -> String -> [(a,String)]
parse p inp = p inp

(+++) :: Parser a -> Parser a -> Parser a
p +++ q = \inp -> case parse p inp of
            [] -> parse q inp
     [(v,out)] -> [(v,out)]

So far so good, they can be loaded into ghci. But when I add the following function

sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then return x else failure

I obtain an error. Could you tell what's going on?

Upvotes: 1

Views: 396

Answers (2)

Lee
Lee

Reputation: 144106

Use of do blocks requires that your Parser is an instance of the Monad class. Since your Parser type is an alias for a function type String -> [(a, String)] and functions are not instances of Monad, this is why you get the error. You could write your function without using do notation:

sat :: (Char -> Bool) -> Parser Char
sat p [] = []
sat p (c:cs) = if p c then [(c, cs)] else []

Upvotes: 0

Cirdec
Cirdec

Reputation: 24156

The type of x in the do block of sat is [(Char, String)]. This is because item has the type String -> [(Char, String)] or (->) String [(Char, String)] and you are using the Monad instance for (->) String, so what is "contained" in a (->) String [(Char, String)] is a [(Char, String)].

{-# LANGUAGE ScopedTypeVariables #-}

sat :: (Char -> Bool) -> Parser Char
sat p = do (x :: [(Char, String)]) <- item
           if p x then return' x else failure

p is a function from a Char to Bool; it doesn't accept a list of possible parsing results. The only sensible thing to do with p is filter the results based on whether the Char matches p. This still results in [] when the result doesn't match p.

sat :: (Char -> Bool) -> Parser Char
sat p = do (x :: [(Char, String)]) <- item
           return $ filter (p . fst) x

If we drop ScopedTypeVariables, we need to drop the type signature I added for illustration.

sat :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           return $ filter (p . fst) x

Upvotes: 1

Related Questions