在實例聲明中推導類

由於教學原因，我正在實現與Parsec類似的功能。動機是定義Functor，Applicative和Alternative實例而不使用Monad魔法。 Functor和Applicative的實例很好。然而，在Alternative中定義<|>正在磨損我的頭髮。在實例聲明中推導類

newtype Parser t = Parser (String -> [(t, String)]) 

parse (Parser p) s = p s 

instance Functor .... 
instance Applicative .... 

empty1 = Parser $ \s -> [] 

orp :: Parser t -> Parser t -> Parser t 
-- orp :: (Eq t) => Parser t -> Parser t -> Parser t -- this works too 
p1 `orp` p2 = Parser $ \s -> let p1out = parse p1 s 
           e  = parse empty1 s 
          in 
           if p1out == e 
           then parse p2 s 
           else p1out  

{- 
instance Alternative Parser where 
    empty = Parser $ \s -> [] 

    (<|>) = orp -- fails to compile 
-}

GHC抱怨說，它無法從上下文推斷Eq，即使我添加到Eq的orp`簽名。很明顯，我不能將一個簽名添加到實例聲明中以使其表現良好。單態限制沒有幫助;也許我不明白這一切。

我錯過了什麼？我應該探索存在類型嗎？或者我犯了一個根本的錯誤？或者這是不可能的？

來源

2012-07-27 kusimari

而不是使用(==)比較空單的，你應該模式匹配

orp :: Parser t -> Parser t -> Parser t 
orp p1 p2 = Parser $ \s -> 
    case parse p1 s of 
     [] -> parse p2 s 
     xs -> xs

達到無類型的類約束相同的行爲，因此在實例聲明可用。

來源

2012-07-27 10:36:09

丹尼爾菲捨爾提出了一個具體的修復;我想建議一個抽象的修復。一路上，我們會公開一個您在此做出的設計決定，您甚至可能沒有意識到自己已經做出了決定（並且我會做出錯誤決定的情況）。

是應用函子組成的well known;它雖然不是我自己發明的，但其他種類的函子配對組合起來卻不是那麼有名。特別是，一個替代函子與任一側的函子組成一個新的替代函數。下面，我將使用Haskell語法來解釋我的意思。我會寫無效 Haskell - 因爲我將在任何地方使用type而不是newtype以避免混亂 - 但我們會在以後使用無效的Haskell派生有效的Haskell。

type (f :. g) a = f (g a) -- like in TypeCompose 

-- (1) 
instance (Applicative f, Alternative g) => Alternative (f :. g) where 
    empty = pure empty 
    x <|> y = liftA2 (<|>) x y 

-- (2) 
instance Alternative f => Alternative (f :. g) where 
    empty = empty 
    x <|> y = x <|> y

（這些情況下，重疊的真的，真的很多。）

語義上說，我們現在可以查看您的類型爲類型組成的鏈：

-- (3) 
type Parser = (String ->) :. [] :. (String,)

...其中我們在這裏觀察(String ->)是Applicative（4）的一個實例，並且[]是Alternative（5）的實例。這意味着我們應該能夠通過將Parser的語義定義與上面的實例耦合，從此「讀取」Alternative的實例。

empty :: Parser t 
= -- (3) 
empty :: (String ->) :. [] :. (String,) 
= -- (1) 
pure (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,)) 
= -- (4) 
const (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,)) 
= -- (2) to use []'s empty rather than [] :. (String,)'s empty 
const (empty :: [] :. (String,)) :: (String ->) :. ([] :. (String,)) 
= -- (5) 
const [] :: (String ->) :. ([] :. (String,)) 

p <|> q :: Parser t -> Parser t -> Parser t 
= -- (3) 
p <|> q :: ... -> ... -> ((String ->) :. [] :. (String,)) 
= -- (1) 
liftA2 (<|>) p q 
= -- (4) 
\s -> p s <|> q s 
= -- (2) to use []'s <|> rather than [] :. (String,)'s <|> 
\s -> p s <|> q s 
= -- (5) 
\s -> p s ++ q s

所以，語義，我們知道我們要怎麼empty和<|>現在表現爲Parser s，而剩下的唯一的訣竅就是在所有適當的NEWTYPE建設者和deconstructors增加。

instance Alternative Parser where 
    empty = Parser (const []) 
    Parser p <|> Parser q = Parser (\s -> p s ++ q s)

或者，如果我們覺得興奮，我們可以寫同樣的事情更重載語法：

instance Alternative Parser where 
    empty = Parser (pure empty) 
    Parser p <|> Parser q = Parser (liftA2 (<|>) p q)

注意，這個實現的(<|>)實際上總是返回從q所有的結果！在你的定義中，當p失敗時，q只返回其解析;這尤其意味着成功的解析列表將會左偏。上面的語義驅動實現沒有這樣的偏見：即使(<|>)的左側解析，也可以允許右側講述它的勝利。我認爲這很自然：這意味着使用此接口構建的解析器將返回所有成功的解析。

實際上有什麼區別？那麼上面的語義定義是更穩健，並且您提出的定義是效率更高。讓我們先看看「更健壯」的含義。

考慮一個解析器總是消耗只有一個字符（它返回什麼將是不重要的討論）：

oneChar = Parser (\s -> case s of 
    c:cs -> [((),cs)] 
    _ -> [])

...並總是成功不消耗任何字符的解析器：

epsilon = Parser (\s -> [((),s)]) -- you might recognize this as "pure()"

現在，如果我們編寫這樣的一個或兩個字符的解析器會發生什麼？

oneOrTwo = (oneChar <|> epsilon) <* oneChar

考慮使用oneOrTwo解析"a"。在你的定義爲(<|>)時，第一部分oneChar <|> epsilon嘗試使用oneChar解析一個成功的位，因此永遠不會運行epsilon，我們將得到一個解析列表，如[((),"")]。但是現在第二部分失敗了：沒有一個字符需要解析。根據我對(<|>)的定義，第一部分將嘗試同時運行oneChar和epsilon的兩個解析，並獲得如[((),""),((),"a")]的解析列表。現在，第二部分在列表的第一個元素上失敗，但在第二個元素上成功，並且解析總體成功。另一方面，由於兩個原因，你的定義可以更有效：首先，它可以儘早丟棄輸入的早期部分（導致與垃圾收集更好的交互），其次，它可以修剪大部分的回溯搜索空間（導致搜索週期更少）。

這種權衡是相當知名的;例如，Parsec通過try組合子提供了你的交替類型（它向第一個參數提交，如果它消耗任何輸入的話）和我的類型（它會回溯）。

來源

2012-07-27 19:02:02

在實例聲明中推導類

回答

相關問題