實施解析器函子

Question

布倫特Yorgey的2013賓夕法尼亞大學class作業工作，以下newtype存在：

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

我試圖實現Parser作爲Functor。

鑑於以下first功能，以幫助解決這個問題：

first :: (a -> b) -> (a, c) -> (b, c) 
first f (a, c) = (f a, c) 

我試過如下：

instance Functor (Parser) where 
    fmap g (Parser f) = Parser $ fmap (first g) (f . g) 

然而，這是行不通的。

據我所知，f的型號是String -> Maybe (a, String)。所以，我不知道如何apply一個String到f爲了得到Maybe (a, String)。

一旦我得到一個Maybe (a, String)，我相信我可以簡單地運行fmap (first g) ...其中...代表Maybe。

請給我一個提示，以瞭解如何獲得Maybe (a, String)。

由於f欠一個String給一個類型的Maybe (a, String)，我不知道在哪裏可以找到String說法。

Answer 1

你做得很好。

如果我只是做一個類型的同義詞它可能是更清晰

type M a = Maybe (a,String) 

你說得對，你可以用

fmap (first g) :: Maybe (a, String) -> Maybe (b,String) 
--    :: M a -> M b 

與

f :: String -> Maybe (a,String) 
-- String -> M a 

你剛纔結合起來需要編寫String -> M a與M a -> M b得到String -> M b：

instance Functor (Parser) where 
    fmap g (Parser f) = Parser $ fmap (first g) . f 

---

你問，如果你可以從什麼地方得到的字符串。 Lambda會爲你做到這一點：\xs ->可以閱讀「給我一個字符串xs ...」，你可以將f應用於該字符串以獲得Maybe (a,String)類型的東西。所以你也可以這樣寫：

instance Functor (Parser) where 
    fmap g (Parser f) = Parser $ \xs -> fmap (first g) (f xs) 

Answer 2

將g應用於解析器f，即複合g和f。然而，由於g是一般函數，並且f返回Maybe（a，String），所以我們需要將g轉換爲

Maybe(a,String)->d 

。鑑於first::(a->b)->(a,c)->(b,c) ，然後

first.Maybe :: Maybe(a->b,a->b)->Maybe(a,String)->Maybe(b,String) 
first.Maybe :: (a->b)->Maybe(a,String)->Maybe(b,String) 
first.Maybe g :: Maybe(a,String)->Maybe(b,String) 

所以

instance Functor Parser where 
    fmap g f = Parser $ fmap (first.Maybe g) . f