Sequencing basic parsers in Haskell and Frege using do notation

Question

I try to run snippets from chapter 8 about functional parsers in Graham Hutton's 'Programming in Haskell' both in ghci and frege-repl. I'm not able to sequence parsers using do syntax. I have following definitions in Frege (Haskell version differs only with simpler item definition that doesn't pack and unpack String and Char and is the same as in the book):

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' works both in ghci and frege-repl. However, when trying loading module I got those messages. First from 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 is even less friendly because it simply kicks me out from repl with an error stack trace:

 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$80.eval(GenJava7.java:11387)
    at frege.compiler.GenJava7$80.eval(GenJava7.java:11327)
    at frege.runtime.Fun1$1.eval(Fun1.java:63)
    at frege.runtime.Delayed.call(Delayed.java:198)
    at frege.runtime.Delayed.forced(Delayed.java:267)
    at frege.compiler.GenJava7$78.eval(GenJava7.java:11275)
    at frege.compiler.GenJava7$78.eval(GenJava7.java:11272)
    at frege.runtime.Fun1$1.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$4.eval(State.java:1900)
    at frege.control.monad.State$IMonad_State$4.eval(State.java:1897)
    at frege.runtime.Fun1$1.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$4.eval
...

My intuition is that I need something apart >>= and return or there is something I should tell compilers. Or maybe I need to put p definition into State monad?

Answer 1

The following works with Frege (and should work the same way with GHC language extension 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")

It prints:

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

The main difference to your version is a more efficient item function, but, as I said before, this is not the reason for the stack trace. And there was this small indentation problem with the do in your code.

So yes, you can use the do notation here, though some would call it "abuse".