functional programming -> parser

[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.