Haskell Type Error
Consider the following piece of Haskell code:
type Parser a = String -> [(a, String)]
item :: Parser Char
item = \ inp -> case inp of
[] -> []
(x:xs) -> [(x, xs)]
ret :: a -> Parser a
ret v = \ inp -> [(v, inp)]
parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp
pseq :: Parser 开发者_高级运维(Char, Char)
pseq = do x <- item
item
y <- item
ret (x, y)
ac = parse pseq "abcdef"
When trying to run the above code in hugs (Version September 2006), I get the following error message:
Type error in explicitly typed binding
*** Term : pseq
*** Type : [Char] -> [(([(Char,[Char])],[(Char,[Char])]),[Char])]
*** Does not match : Parser (Char,Char)
And, when I remove my type declaration for "pseq", I get the following error message:
Unresolved top-level overloading
*** Binding : pseq
*** Outstanding context : Monad ((->) [Char])
The problem is that you're trying to use do
-notation for Parser
, but it's not exactly a Monad
. It is sort of, because there's a Monad
instance for r ->
, but that makes the type on the right-hand side of the ->
the "element" type of the Monad
, and here you want the element type to be the a
in [(a,String)]
. You need to make the definition of Parser
a newtype
, and write a custom Monad
instance for it (or compose it out of exising monads/transformers like ListT
and StateT
).
Making Parser a Monad is easy, and I think resorting to ListT or StateT is probably overkill here.
newtype Parser a = Parser (String -> [(a, String)])
-- make this a distinct type
-- now the function is "wrapped", though at no run-time cost
instance Monad Parser where
return = ret -- you already had it defined
(>>=) = bind -- added below
-- this instance makes Parser a Moand, and lets it work with do notation
item :: Parser Char
item = Parser $ \ inp -> case inp of
[] -> []
(x:xs) -> [(x, xs)]
-- need to "wrap" up the function as a Parser value
ret :: a -> Parser a
ret v = Parser $ \ inp -> [(v, inp)]
-- need to "wrap" up the function as a Parser value
bind :: Parser a -> (a -> Parser b) -> Parser b
bind p f = Parser $ \ s -> case parse p s of
[] -> []
[(a, s')] -> parse (f a) s'
-- the only function you were missing
-- it is worth making sure you understand how it works
parse :: Parser a -> String -> [(a, String)]
parse (Parser p) inp = p inp
-- needs to "unwrap" the newtype here
pseq :: Parser (Char, Char)
pseq = do x <- item
item
y <- item
ret (x, y)
ac = parse pseq "abcdef"
-- you probably meant pseq here, not seq
Lastly, you use the return type of [(a, String)]
, so that you can indicate things which can't parse. But the list only ever has zero or one items in it. You should look into the types Maybe
and Either
which would likely be clearer in this case.
精彩评论