許多產生空串的地方？

Question

我正在閱讀Graham Hutton在Haskell編程。我陷在了帕爾斯的章節中。在它有定義爲兩個相互遞歸功能：

many p = many1 p +++ return [] 
many1 p = do v <- p 
      vs <- many p 
      return (v:vs) 

凡many實際上轉化成這種形式：

many1 p = p >>= (\ v -> many p >>= (\ vs -> return (v : vs))) 

的>>=操作者被定義爲：

p >>= f = P (\inp -> case parse p inp of 
          []  -> [] 
          [(v,out)] -> parse (f v) out) 

的+++運營商定義爲：

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

個

有關這個問題的另一個功能是這些：

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

sat p = do x <- item 
      if p x then return x else failure 

digit = sat isDigit 

failure = P (\inp -> []) 
item = P (\inp -> case inp of 
          []  -> [] 
          (x:xs) -> [(x,xs)]) 
return v = P (\inp -> [(v,inp)]) 

現在，企圖用many1從字符串"a"解析數字，就像當：

parse (many digit) "a" 

結果是[("","a")]。

在嘗試從使用many1像字符串"a"解析位數：

parse (many1 digit) "a" 

結果是[]。

我想我理解爲什麼第二個結果。 (many1 digit)嘗試解析字符串"a"，因此它調用digit "a"，由於"a"不是數字，因此失敗，因此空列表返回[]。

但是，我不明白使用(many digit)時的第一個結果。如果(many1 digit)返回[]那麼顯然它失敗了，所以在+++運算符中，執行第二個case表達式。但是當我嘗試parse (return []) "a"時，我得到的結果是[([], "a")]。

我不明白爲什麼many的結果是[("", "a")]，結果many1是[]。 任何幫助表示讚賞。

P.S.我已經看過this question，但它沒有給我我正在尋找的答案。

Answer 1

如果你的困惑是，你回來[("", "a")]當你預期的[([], "a")]：

字符串是字符數的列表。所以""是一個空的Chars列表。由於[]是任何類型的空列表，這意味着""只是[]的特例。換句話說，[] :: [Char]完全等同於""。

因此，由於您的解析器預計會生成一個字符串，因此已知空列表的類型爲[Char]，因此打印爲""而不是[]。