Parser(Haskell)更好的应用实例

Question

我正在完成Brent Yorgey Haskell课程,而我在为Applicative定义一个好的实例时遇到了麻烦.解析器定义如下:

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

该函数接受一个字符串,解析一定量的输入,并返回一个Maybe元组,其中第一个值是解析器的类型,其余的是未解析的字符串剩余部分.例如,这是正整数的解析器:

posInt :: Parser Integer
posInt = Parser f
  where
    f xs
      | null ns   = Nothing
      | otherwise = Just (read ns, rest)
      where (ns, rest) = span isDigit xs

赋值是为Parser创建Applicative实例.我们从一个Functor实例开始(我认为这是相对简单的):

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

instance Functor Parser where
  fmap f p = Parser f' 
    where f' s = fmap (first f) $ (runParser p) s

然后我尝试使用Applicative:

collapse (Just (Just a)) = Just a
collapse _ = Nothing

extract (Just a, Just b) = Just (a,b)
extract _ = Nothing

appliedFunc :: Parser (a->b) -> Parser a -> String -> Maybe (b, String)
appliedFunc p1 p2 str = extract (f <*> fmap fst result2, fmap snd result2)
  where result1   = (runParser p1) str
        f         = fmap fst result1
        result2   = collapse $ fmap (runParser p2) $ fmap snd result1

instance Applicative Parser where
  pure a = Parser (\s -> Just (a, s))
  p1 <*> p2 = Parser (appliedFunc p1 p2)

......呸.所以我的问题是,如何让我的Applicative实例更清洁,更难以阅读？我觉得这个问题有一个简单的答案,但我还没能绕过这些类型.

Answer 1

这可能不是你想要的,但我想顺便提一下,有一个非常简洁的方法来实现这个:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import Control.Applicative
import Control.Monad.Trans.State

newtype Parser a = Parser { unParser :: StateT String Maybe a }
    deriving (Functor, Applicative, Monad, Alternative)

runParser :: Parser a -> String -> Maybe (a, String)
runParser = runStateT . unParser

parser :: (String -> Maybe (a, String)) -> Parser a
parser = Parser . StateT

这样做的原因是引擎盖下的StateT实现方式如下:

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

如果您专注s于String并专注m于Maybe,您将得到:

StateT String Maybe a  ~  String -> Maybe (a, String)

...与您的类型相同.

StateT 自动为您提供以下实例:

instance Monad m => Functor     (StateT s m)
instance Monad m => Applicative (StateT s m)
instance Monad m => Monad       (StateT s m)

instance Alternative m => Alternative (StateT s m)

...我们可以专注m于那些实例,Maybe因为Maybe实现了两者Alternative和Monad:

instance Monad Maybe

instance Alternative Maybe

......这样就意味着StateT s Maybe自动为Functor,Applicative,Monad并Alternative没有对我们进行任何额外的工作.

这个技巧的最后一部分是GeneralizedNewtypeDeriving,它允许我们通过newtype包装器提升类型类实例.因为我们的基本StateT类型是Functor,Applicative,Monad,和Alternative,我们可以通过添加自动升降,通过我们的NEWTYPE所有四个类型的类实例:

... deriving (Functor, Applicative, Monad, Alternative)

...并且编译器将为我们的newtype重新实现它们,注意为我们做所有newtype包装和解包.

因此,如果您想弄清楚如何Applicative为您的解析器实现,您可能想要研究如何Applicative实现StateT,然后从中推断如何为您的解析器类型实现它.

Answer 2

我假设你还没有Monad参加课程.您正在使用的方式collapse并fmap告诉我您基本上正在重新发明Monad以解决此问题,特别是Monad Maybe实例.事实上,你collapse和join这个monad 是一样的.确实使用它是解决这个问题的一种非常优雅的方式,但在这一点上可能有点"作弊".以下是我在使用您的功能时可以获得的最佳形状:

appliedFunc p1 p2 str = collapse $ fmap step1 (runParser p1 str)
  where
    step1 (f, str2) = collapse $ fmap step2 (runParser p2 str2)
      where
        step2 (x, str3) = Just (f x, str3)

一旦你做到了Monad正确,你应该能够用更简洁的(>>=)运算符和/或do表示法重写它.

另一种几乎同样简单,但不需要重新发明monad的替代方案是使用Maybes的显式模式匹配.然后你可以得到类似的东西:

appliedFunc p1 p2 str = case runParser p1 str of
    Nothing        -> Nothing
    Just (f, str2) -> case runParser p2 str2 of
        Nothing        -> Nothing
        Just (x, str3) -> Just (f x, str3)