哈斯克爾類型錯誤

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" 

當試圖運行擁抱（版本2006年9月）上面的代碼中，我得到了以下錯誤消息：

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

問題是，重新嘗試使用do -notation爲Parser，但它不完全是Monad。這是有點，因爲r ->有Monad實例，但是它使得->的的「元素」類型的右側的類型成爲中的a的元素類型。您需要定義Parser a newtype，併爲其編寫一個自定義的Monad實例（或將其編寫爲出現的單子/變形器，如ListT和StateT）。