3 ms·

> What ensures that the “rest of the string” is, in fact, a suffix of the input? This is not something you want to guarantee. takeWhile, dropWhile and many ar

by mrkeen 3y ago

> What ensures that the “rest of the string” is, in fact, a suffix of the input? This is not something you want to guarantee. takeWhile, dropWhile and many are three parsers which might consume 0 bytes. Backtracking via some kind of try parser would probably be unhappy as well. > I assume the purpose of this design is for compatibility with lazy input sequences Probably not. > I would want to know the position and length of the parsed output I don't understand exactly what you mean by these, but these would like be two 'parser' functions (which don't advance through the string), having types: positionOfParsedOutput :: Parser Int lengthOfParsedOutput :: Parser Int I don't think these two are implementable directly from the given definition of Parser. I'm quite far through a language implementation project, and I'm very happy about having rolled my own parser combinators. The core I used was: newtype Parser s a = Parser { runParser :: s -> Either ByteString (s, a) } * Either is better than Maybe because it gives you room for an error message. * s is polymorphic instead of String, and here's why: Your job becomes insanely easier if you split parsing into a lexing and parsing phases. But a lexer is just another parser, which different inputs and outputs. Look! lexer :: Parser String [Token] parseExpression :: Parser [Token] Expression But back to positionOfParsedOutput and lengthOfParsedOutput which I said weren't implementable from the above. Simply replace the String type from your definition with a tuple or a struct, in order to carry the extra information. data ParseState = ParseState { remaining :: String , pos :: Int , len :: Int } newtype Parser a = P (ParseState -> Maybe (ParseState, a))

amluto 3y ago
>> What ensures that the “rest of the string” is, in fact, a suffix of the input? >This is not something you want to guarantee. >takeWhile, dropWhile and many are three parsers which might consume 0 bytes. Backtracking via some kind of try parser would probably be unhappy as well. I'm not quibbling about a proper suffix vs a suffix. I'm quibbling about the unparsed tail being a suffix at all. I don't write Haskell code, so my syntax here is probably all wrong, but imagine: brokenparse s = Just (42, "rest of string") or, slightly more realistically: brokenparse s = (42, toUpper s) where toUpper represents something that the actual implementation might have wanted to calculate as an intermediate and then accidentally returned as the "rest" of the input. A totally type-unsafe Python equivalent would look like: def parse(input): ... do something return (result, input[2:]) and has exactly the same issue. But one could alternatively write it (in Python or most imperative languages) as: def parse(input): input.consume(some number of symbols) return output or quite a variants thereof, and the result seems safer to me, although considerable care would be needed with backtracking. (And even Rust can't actually make this safe as far as I know due to std::mem::swap.) It's certainly nice for something like a parser to be written in a pure language or style such that backtracking is essentially free. I would imagine that Haskell could express the constraint that the "rest" output of a parser needs to be a genuine suffix of the input using a universal type / threading trick in the style of runST. Maybe the result would be too much hassle to be used in real life.
- saurik 3y ago
  What you are looking for is called "dependent types" and is the same mechanism that you have to have to prevent the function you seem to insist is so obviously to you the right way to do it from also being wrong by returning an offset past the end of the string. Being able to express such things as "this function returns an integer which is between 0 and the length of the string passed as the second argument" and "this function returns a sequence which is related in some way to the sequence passed as an argument" is a reasonable thing to want, but almost no programming languages provide the mechanism to do it; that said, the languages which do--such as Idris or Coq--look a LOT closer to Haskell than Python.
  - mrkeen 3y ago
    > returning an offset past the end of the string I feel if you're dealing with offsets into strings, it's probably easier to stop doing that rather than try to get the type checker to prove it 'correct'. I tried a linear types implementation: newtype Parser a = P (String ⊸ (String, Maybe a)) parseChar :: Char -> Parser Char parseChar c = P $ \s -> case s of [] -> ([], Nothing) (x:xs) -> if x == c then (xs, Just c) else (xs, Nothing) This guarantees that the 's' is used exactly once instead of dropped on the floor. It's not great because I wanted to drop it on the floor. Here's it not compiling when I use the wrong string: ... then ("some string", Just c) ... • Couldn't match type ‘'Many’ with ‘'One’ arising from multiplicity of ‘s’ • In the second argument of ‘($)’, namely ‘\ s -> case s of
- mrkeen 3y ago
  I had no idea there was such thing as an improper suffix. Here's a quibble-free parser which returns a tail which is neither a "proper suffix nor a suffix". earlyTerminate c = Parser $ \s -> case s of [] -> Right (s, ()) (x:xs) | x == c -> Right ("", ()) | otherwise -> Left "Not a terminator" > although considerable care would be needed with backtracking No shit. Show your example.

by mrkeen 3y ago

amluto 3y ago

>> What ensures that the “rest of the string” is, in fact, a suffix of the input? >This is not something you want to guarantee. >takeWhile, dropWhile and many are three parsers which might consume 0 bytes. Backtracking via some kind of try parser would probably be unhappy as well. I'm not quibbling about a proper suffix vs a suffix. I'm quibbling about the unparsed tail being a suffix at all. I don't write Haskell code, so my syntax here is probably all wrong, but imagine: brokenparse s = Just (42, "rest of string") or, slightly more realistically: brokenparse s = (42, toUpper s) where toUpper represents something that the actual implementation might have wanted to calculate as an intermediate and then accidentally returned as the "rest" of the input. A totally type-unsafe Python equivalent would look like: def parse(input): ... do something return (result, input[2:]) and has exactly the same issue. But one could alternatively write it (in Python or most imperative languages) as: def parse(input): input.consume(some number of symbols) return output or quite a variants thereof, and the result seems safer to me, although considerable care would be needed with backtracking. (And even Rust can't actually make this safe as far as I know due to std::mem::swap.) It's certainly nice for something like a parser to be written in a pure language or style such that backtracking is essentially free. I would imagine that Haskell could express the constraint that the "rest" output of a parser needs to be a genuine suffix of the input using a universal type / threading trick in the style of runST. Maybe the result would be too much hassle to be used in real life.

saurik 3y ago
What you are looking for is called "dependent types" and is the same mechanism that you have to have to prevent the function you seem to insist is so obviously to you the right way to do it from also being wrong by returning an offset past the end of the string. Being able to express such things as "this function returns an integer which is between 0 and the length of the string passed as the second argument" and "this function returns a sequence which is related in some way to the sequence passed as an argument" is a reasonable thing to want, but almost no programming languages provide the mechanism to do it; that said, the languages which do--such as Idris or Coq--look a LOT closer to Haskell than Python.
- mrkeen 3y ago
  > returning an offset past the end of the string I feel if you're dealing with offsets into strings, it's probably easier to stop doing that rather than try to get the type checker to prove it 'correct'. I tried a linear types implementation: newtype Parser a = P (String ⊸ (String, Maybe a)) parseChar :: Char -> Parser Char parseChar c = P $ \s -> case s of [] -> ([], Nothing) (x:xs) -> if x == c then (xs, Just c) else (xs, Nothing) This guarantees that the 's' is used exactly once instead of dropped on the floor. It's not great because I wanted to drop it on the floor. Here's it not compiling when I use the wrong string: ... then ("some string", Just c) ... • Couldn't match type ‘'Many’ with ‘'One’ arising from multiplicity of ‘s’ • In the second argument of ‘($)’, namely ‘\ s -> case s of
mrkeen 3y ago
I had no idea there was such thing as an improper suffix. Here's a quibble-free parser which returns a tail which is neither a "proper suffix nor a suffix". earlyTerminate c = Parser $ \s -> case s of [] -> Right (s, ()) (x:xs) | x == c -> Right ("", ()) | otherwise -> Left "Not a terminator" > although considerable care would be needed with backtracking No shit. Show your example.