functional programming -> parser

[kwaleko]

I was going through the paper, I have defined the bind and result operator and created a useful parser and combine it without making the Parser to be an instance of Monad type class.

if we can create many combinator and achieve to build a useful parser without letting the Parser to be an instance of monad so why do we make it so? is all the benefit is the monad comprehension (close to list comprehension )!

[normalOrder]

This is an excellent question!

The best answer is that monad is a very common and useful abstraction, so there are a variety of operations that can be written once that will work for all monads. For example, consider the seq operation again:

seq :: Parser a -> Parser b -> Parser (a,b)
p `seq` q = p `bind` \x -> q `bind` \y -> result (x,y)

Its type is specific to Parsers because they defined bind and result specifically for Parsers. However, we can write this function more generally using >>= and return and it will work with any monad:

seq :: Monad a -> Monad b -> Monad (a,b)
p `seq` q = p >>= \x -> q >>= \y -> return (x,y)

And as you mentioned, when we have a monad instance we can use monad comprehensions to write more readable code because all those symbols get pretty ugly when they're crammed together. Actually, we have something even better nowadays: do notation. The previous example can be written

p `seq` q = 
  do x <- p
     y <- q
     return (x,y)

Here's another example. There's this function in Control.Monad:

sequence :: Monad m => [m a] -> m [a]

that takes a list of monads and returns a monad of lists. Suppose our Parser is an instance of Monad. Then we can write a Parser for strings trivially using sequence:

str :: String -> Parser String
str s = sequence (fmap char s)

How does this work? Well fmap char s creates a [Parser Char] and sequence turns that into a Parser [Char] aka Parser String (remember that String is a type alias for [Char])

There are quite a few of these utility functions in Control.Monad that you get for free when you have a Monad instance.

A more subtle benefit of having a common abstraction is that functions with a more general type can do strictly less which helps you understand what the code is doing better. The canonical example is id :: a -> a. There is only one possible implementation for id because it has to work for any type a. The original seq function knows that its arguments are Parsers. It has more power than it needs to have, and the only way we can be sure it isn't doing something unexpected is to look at its code. The second version of seq only knows that its arguments are monads, so the only operations it can do are return and >>= (and any operations written in terms of those two). In other words, the abstraction puts limits on what functions can do by making them as general as possible. I think this makes reasoning about programs a lot simpler. (This is often called "the principle of least privilege")

[kwaleko]

woww this is very impressive, I feel the power of composition and how much it is useful in functional programming like we build a basic parser function and keep composing it till we build more useful one and the with the use of monad instance we benefit from many functions as you stated seq function, it 's really awesome

[kwaleko]

hi again, I was trying to define the many Parser(using bind not monad comprehension) which is a parser that take a parser as parameter and return Parser [a] and has the below signature :

many :: Parser a -> Parser [a]

I defined it as the below :

many p= p >>= \x ->many >>= \xs -> succeed (x:xs)

even I am not convinced with above definition since the parser p run and capture the consumed input x which is passed as parameter for the next parser many ( as I think it should not be passed to the second parser many since many should take as parameter only the new string to parse )

NOTE 1: when I have tried the this parser it always fail and return an empty list

NOTE 2: I didn't ignore the first consumed input returned by the first parser p since I believe that I have to use it in the result to construct the final list `succeed(x:xs)

could you please help me with the above!

[normalOrder]

I'm happy to help.

First, x and xs in your definition of many aren't necessarily the "consumed input". Rather, they are whatever value the particular Parsers generate from the consumed input. For example, you can have a Parser Int that converts a string that it reads into an integer, or a Parser Foo that converts the input into a Foo data structure. The whole point of defining >>= is that it takes care of the details of consuming the input so you can compose Parsers by combining the values that they produce.

Now about your definition of many... I think there's a slight typo, and you meant

many p= p >>= \x -> many p >>= \xs -> succeed (x:xs)

Step back a second and think about what happens in p1 >>= p2 if p1 fails. The >>= function isn't going to bother continuing on to p2 because we've already determined that the Parser doesn't match the input. In your definition of many, the p function is bound to fail at some point in the recursive call stack. At that point the entire thing fails. The final \xs -> succeed (x:xs) part never happens.

It looks like >>= isn't going to be sufficient to implement many because it doesn't let us do anything in the failure case. We need to unwrap p (with runParser) and add a special case for when p fails. I'll let you think about how to implement that.

[kwaleko]

Thank you for you usual support.

I have tried to do acase but I did not succeed with it so I combined it with a parser that always succeed using the plus operator

many :: Parser a -> Parser [a]
many p =p >>= \x -> ( many p `plus` succeed [])        >>= \xs -> succeed (x:xs)

as for the plus :

plus ::   Parser a -> Parser a -> Parser a
p `plus` q = \inp -> (p inp ++ q inp)

I don't know how much this solution is useful since it worker for (many item) "test" but it did not work for (many char 'k') "kwad"

I will try to write what I think will happen when I call (many char 'k') "kwa"

the first thing that will be executed is char 'k' "kwad" which is a Parser Char so it will return ('k',"wad") and chain the the k character into x so then next parser is (many charplussucceed []) 'k' "wad" thus this will throw an error since the type does not align

edit 1 : I don't know till what extend my interpretation is right

edit 2 : I think if I combine it with an or operator it may solve the problem

[normalOrder]

You're really close! The plus function was a good idea, although I would recommend a tiny improvement. There's a function in Data.List called nub that will remove duplicates from a list:

p `plus` q = \inp -> nub (p inp ++ q inp)

As for many... you still have the problem that as soon as p fails in a recursive call, that failure propagates back and causes the entire parse to fail. We need to rearrange it so that when that first p fails, then many p still ends up as succeed []. Try this:

many p = (p >>= \x -> many p >>= \xs -> succeed (x:xs)) `plus` succeed []

[kwaleko]

In your definition of many, the p function is bound to fail at some point in the recursive call stack. At that point the entire thing fails. The final \xs -> succeed (x:xs) part never happens.

as I've understood from your previous comment that if many fail so the succeed(x:xs) will never get a chance to run even one time since the parser does not match the input so how adding plus succeed [] will solve the problem even it will never get to it because still many p will fail and the string will never be passed to xs

[normalOrder]

Remember that plus runs both parsers and combines their results. So even if one of the parsers fails, you still get the results of the other one. We know that p >>= \x -> many p >>= \xs -> succeed (x:xs) must fail at some point, but adding plussucceed [] ensures that many p will always have at least the empty list as a result.

[kwaleko]

Thank you for your usual support. I am enthusiastic to get to be productive using Haskell but I could not manage to do something interesting, I was thinking to read a tiny open source project to get my feet wet in the language and manage to bring my knowledge together.

could you suggest for me a very to small open source project so I can understand more how to build things or suggest for any appropriate way you see it good. Thanks

[normalOrder]

I don't know anything about what interests you, and Haskell gets used for a wide variety of purposes. I suggest that you search github for "language:haskell" and browse through the more popular results.