Haskell 中列表的 Monad

Question

我试图在 Haskell:

中使它成为 Monad 的一个实例

data Parser a = Done ([a], String) | Fail String

现在我尝试使用这段代码使其成为 Monad 的实例：

instance Functor Parser where
  fmap = liftM

instance Applicative Parser where
  pure = return
  (<*>) = ap

instance Monad Parser where
  return xs = Done ([], xs)
  Done (xs, s) >>= f = Done (concat (map f xs)), s)

但这显然不行，因为bind-function中的函数f是a -> M b类型的。所以 (map f xs) 函数产生一个 M b 的列表。它实际上应该列出 b 的列表。我如何在 Haskell 中执行此操作？

注意：GHC 7.10.3给出的实际错误是：

SuperInterpreter.hs:71:27:
Couldn't match expected type `String' with actual type `a'
  `a' is a rigid type variable bound by
      the type signature for return :: a -> Parser a
      at SuperInterpreter.hs:71:5
Relevant bindings include
  xs :: a (bound at SuperInterpreter.hs:71:12)
  return :: a -> Parser a (bound at SuperInterpreter.hs:71:5)
In the expression: xs
In the first argument of `Done', namely `([], xs)'

SuperInterpreter.hs:72:45:
Couldn't match type `Parser b' with `[b]'
Expected type: a -> [b]
  Actual type: a -> Parser b
Relevant bindings include
  f :: a -> Parser b (bound at SuperInterpreter.hs:72:22)
  (>>=) :: Parser a -> (a -> Parser b) -> Parser b
    (bound at SuperInterpreter.hs:72:5)
In the first argument of `map', namely `f'
In the first argument of `concat', namely `(map f xs)'
Failed, modules loaded: none.

Answer 1

虽然定义 fmap = liftM 等并不少见，但在我看来这有点倒退。如果您首先定义更基本的实例，并将更复杂的实例基于它们，事情通常会变得更清晰。我会离开<*> = ap，但改变其他一切：

instance Functor Parser where  -- Note that you can `derive` this automatically
  fmap f (Done vs rest) = Done (map f vs) rest
  fmap f (Fail err) = Fail err

instance Applicative Parser where
  pure xs = Done ([], xs)
  (<*>) = ap

现在 fmap 已经存在，我可以用“更数学”的方式定义 Monad：定义 join 而不是 >>=。

instance Monad Parser where
  return = pure
  q >>= f = joinParser $ fmap f q

这意味着您将使用直观可处理的具体值，而不必担心通过解析器对函数进行线程处理。因此，您可以非常清楚地看到发生了什么，只需写出递归即可：

joinParser :: Parser (Parser a) -> Parser a
  joinParser (Fail err) = Fail err
  joinParser (Done [] rest) = Done [] rest
  joinParser (Done (Fail err : _) _) = Fail err
  joinParser (Done (Done v0 rest0 : pss) rest) = ??

此时您可以清楚地看到 Carsten 已经说过的话：您的 Parser 类型作为解析器并没有真正的意义。内部和外部 Done 包装器都以某种方式具有 rest 数据；结合它意味着你结合未完成的工作......这不是解析器所做的。

在网上搜索一下，关于如何在 Haskell 中实现解析器的内容很多 material。有疑问，看看一些已建立的库是如何做到的，e.g. parsec。

Answer 2

leftaroundabout 已经向您展示了一些问题。

通常我希望解析器是某种接受输入的函数-String，可能会使用该字符串的一部分，然后将结果与未使用的输入一起返回。

基于这个想法，您可以扩展您的代码来做到这一点：

data ParserResult a
  = Done (a, String)
  | Fail String
  deriving Show

data Parser a = Parser { run :: String -> ParserResult a }

instance Functor Parser where
  fmap = liftM

instance Applicative Parser where
  pure = return
  (<*>) = ap

instance Monad Parser where
  return a = Parser $ \ xs -> Done (a, xs)
  p >>= f = Parser $ \ xs ->
    case run p xs of
      Done (a, xs') -> run (f a) xs'
      Fail msg      -> Fail msg

一个简单的例子

这是一个可以接受任何字符的简单解析器：

parseAnyChar :: Parser Char
parseAnyChar = Parser f
  where f (c:xs) = Done (c, xs)
        f ""     = Fail "nothing to parse"

这就是您的使用方式：

λ> run parseAnyChar "Hello"
Done ('H',"ello")
λ> run parseAnyChar ""
Fail "nothing to parse"

Haskell 中列表的 Monad

Monad of list in Haskell

monads

haskell

list

一个简单的例子