Haskell Тип ошибки

Question

Рассмотрим следующий фрагмент Haskell кода:

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" 

При попытке запустить выше код в объятиями (Version сентября 2006), я получаю следующее сообщение об ошибке:

Type error in explicitly typed binding 
*** Term   : pseq 
*** Type   : [Char] -> [(([(Char,[Char])],[(Char,[Char])]),[Char])] 
*** Does not match : Parser (Char,Char) 

И, когда я удаляю объявление своего типа для «pseq», появляется следующее сообщение об ошибке:

Unresolved top-level overloading 
*** Binding    : pseq 
*** Outstanding context : Monad ((->) [Char]) 

Answer 1

Сделать Parser Monad легко, и я думаю, что прибегать к ListT или StateT, вероятно, будет излишним.

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 

Наконец, вы используете тип возвращаемого [(a, String)], так что вы можете указать вещи, которые не может разобрать. Но в списке всегда есть только ноль или один элемент. Вы должны изучить типы Maybe и Either, которые, вероятно, будут более четкими в этом случае.

Answer 2

Проблема в том, re пытается использовать do -notation для Parser, но это не совсем Monad. Это похоже на то, что существует Monad экземпляр для r ->, но это делает тип в правой части -> «элементом» типа Monad, и здесь вы хотите, чтобы тип элемента был a в [(a,String)]. Вам нужно сделать определение Parser a newtype и написать для него экземпляр Monad (или составить его из выходящих монад/трансформаторов, таких как ListT и StateT).