实施解析器函子

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