Haskell: How to implement >>= for a parser

Question

I have the following Parser

newtype Parser a = P (String -> [(a,String)])

and I need to implement the bind on its implementation as a Monad. I have that the return is defined as

instance Monad Parser where
    return v = P (\inp -> [(v,inp)])

To implement p >>= f I know this much: p is a Parser object and f has type declaration

f :: a -> Parser b

So I'm thinking the value of p >>= f needs to be a Parser object which wraps a function. That function's argument is a String. So I'm guessing the function should "open up p", get its function, apply that to the input string, get an object of type [(a, String)], then ... I guess maybe apply f to every first coordinate in each tuple, then use the resulting Parser's function and apply it to the second coordinate ... and make a list of all of those tuples?

At this point I get pretty foggy on whether I got this right and if so, how to do it. Maybe I should write a helper function with type

trans :: [(a,String)] -> (a -> Parser b) -> [(b,String)]

But before getting into that, I wanted to check if my confused description of what I should be doing rings true.

@WillemVanOnsem fmap. Is the hint that trans should make use of fmap? Or should is it suggesting that I not create this trans function at all and fmap does everything for me? — Addem
– Addem, Commented Dec 9, 2018 at 0:38
Your informal description looks right to me. Try to turn that into code. — chi
– chi, Commented Dec 9, 2018 at 0:39
@Addem: no, the bind of a list is concatMap, and it is quite similar here. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Dec 9, 2018 at 0:40

Dannyu NDos · Accepted Answer · 2018-12-09 01:15:01Z

1

instance Monad Parser where
    return v = P (\inp -> [(v,inp)])
    P p >>= f = P (\inp -> do
        (x,u) <- p inp
        let P q = f x
        q u
        )

answered Dec 9, 2018 at 1:15

Dannyu NDos

2,51817 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Addem Over a year ago

p inp has type [(a,String)], right? Is the do-notation just grabbing the first element of the list if it exists? Does this mean everything else gets thrown away, if it exists?

Dannyu NDos Over a year ago

@Addem do-notation is a syntactic sugar for any monadic action. Here, it is for a list monad. As a consequence, (x,u) represents every element of p inp.

Addem Over a year ago

Oh, this is due to the fact that bind for list is concatMap which iterates over the elements of the list?

Dannyu NDos Over a year ago

@Addem Yes, exactly.

chi Over a year ago

@Addem In the list monad, do is essentially another syntax for list comprehensions: ... = P (\inp -> [r | (x,u) <- p inp , let P q = f x , r <- q u]) is equivalent.

Collectives™ on Stack Overflow

Haskell: How to implement >>= for a parser

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related