在 Haskell 和 Frege 中使用 do 表示法对基本解析器进行排序

Question

我尝试在 ghci 和 frege-repl 中运行 Graham Hutton 'Programming in Haskell' 的第 8 章中关于函数式解析器的片段。我无法使用 do 语法对解析器进行排序。我在 Frege 中有以下定义（Haskell 版本仅与不打包和解包 String 和 Char 的更简单的 item 定义不同，与书中相同） :

module Parser where
type Parser a = String -> [(a, String)]   

return :: a -> Parser a
return v = \inp -> [(v, inp)]

-- this is Frege version
item :: Parser Char
item = \inp ->
  let inp' = unpacked inp
  in
    case inp' of
        [] -> []
        (x:xs) -> [(x,packed xs)]


parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp

-- sequencing
(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = \inp -> case (parse p inp) of
  [] -> []
  [(v,out)] -> parse (f v) out

p :: Parser (Char, Char)
p = do x <- Parser.item
       Parser.item
       y <- Parser.item
       Parser.return (x,y)

-- this works
p' :: Parser (Char, Char)
p' = item Parser.>>= \x ->
     item Parser.>>= \_ ->
     item Parser.>>= \y ->
     Parser.return (x,y)

p' 适用于 ghci 和 frege-repl。但是，在尝试加载模块时，我收到了这些消息。首先来自 ghci:

src/Parser.hs:38:8:
    Couldn't match type ‘[(Char, String)]’ with ‘Char’
    Expected type: String -> [((Char, Char), String)]
      Actual type: Parser ([(Char, String)], [(Char, String)])
    In a stmt of a 'do' block: Parser.return (x, y)
    In the expression:
      do { x <- item;
           item;
           y <- item;
           Parser.return (x, y) }
Failed, modules loaded: none.

frege-repl 更不友好，因为它只是将我从 repl 中踢出并显示错误堆栈跟踪：

 Exception in thread "main" frege.runtime.Undefined: returnTypeN: too many arguments
    at frege.prelude.PreludeBase.error(PreludeBase.java:18011)
    at frege.compiler.Utilities.returnTypeN(Utilities.java:1937)
    at frege.compiler.Utilities.returnTypeN(Utilities.java:1928)
    at frege.compiler.GenJava7.eval(GenJava7.java:11387)
    at frege.compiler.GenJava7.eval(GenJava7.java:11327)
    at frege.runtime.Fun1.eval(Fun1.java:63)
    at frege.runtime.Delayed.call(Delayed.java:198)
    at frege.runtime.Delayed.forced(Delayed.java:267)
    at frege.compiler.GenJava7.eval(GenJava7.java:11275)
    at frege.compiler.GenJava7.eval(GenJava7.java:11272)
    at frege.runtime.Fun1.eval(Fun1.java:63)
    at frege.runtime.Delayed.call(Delayed.java:200)
    at frege.runtime.Delayed.forced(Delayed.java:267)
    at frege.control.monad.State$IMonad_State.eval(State.java:1900)
    at frege.control.monad.State$IMonad_State.eval(State.java:1897)
    at frege.runtime.Fun1.eval(Fun1.java:63)
    at frege.runtime.Delayed.call(Delayed.java:198)
    at frege.runtime.Delayed.forced(Delayed.java:267)
    at frege.control.monad.State$IMonad_State.eval
...

我的直觉是我需要 >>= 和 return 之外的东西，或者我应该告诉编译器一些东西。或者也许我需要将 p 定义放入 State monad？

Answer 1

这是因为 String -> a 是在您的 do 符号中使用的 monad，因为 Prelude 中 Monad 的实例之一是函数箭头。

因此，例如x <- Parser.item中的x是[(Char, String)]类型的参数。

您可以通过将 Parser 设为 newtype 并为其定义您自己的自定义 Monad 实例来解决此问题。

Answer 2

以下适用于弗雷格（并且应该以与 GHC 语言扩展相同的方式工作 RebindableSyntax）：

module P
    where


type Parser a = String -> [(a, String)]   

return :: a -> Parser a
return v = \inp -> [(v, inp)]

-- this is Frege version
item :: Parser Char
item  = maybeToList . uncons


parse :: Parser a -> String -> [(a, String)]
parse p inp = p inp

-- sequencing
(>>=) :: Parser a -> (a -> Parser b) -> Parser b
p >>= f = \inp -> case (parse p inp) of
  [] -> []
  [(v,out)] -> parse (f v) out

p :: Parser (Char, Char)
p = do 
    x <- item
    item
    y <- item
    return (x,y)

main = println (p "Frege is cool")

它打印：

[(('F', 'r'), "ege is cool")]

与您的版本的主要区别在于更高效的 item 函数，但是，正如我之前所说，这不是堆栈跟踪的原因。您的代码中的 do 存在这个小缩进问题。

所以是的，你可以在这里使用 do 表示法，尽管有些人会称之为 "abuse"。

在 Haskell 和 Frege 中使用 do 表示法对基本解析器进行排序

Sequencing basic parsers in Haskell and Frege using do notation

haskell

frege

do-notation