4
\$\begingroup\$

Objective

Mimic Haskell's reads :: ReadS ().

Or in other words, parse nested parentheses. Since the target type is () (the type with one possible value), "parsing" means discarding a leading nested parentheses.

Valid Input

"Nested parentheses" means (), (()), ((())), and so on. That is, leading nonzero (s and trailing )s of the same number.

But there's a twist. The parser must munch also leading or intercalated whitespaces. So for example, the following strings are valid to be munched:

  • ( )
  • ()
  • ( () )

Note that trailing whitespaces are not to be munched.

Whitespaces

The following ASCII characters are always considered a whitespace:

  • \t U+0009; Horizontal Tab
  • \n U+000A; Line Feed
  • \v U+000B; Vertical Tab
  • \f U+000C; Form Feed
  • \r U+000D; Carriage Return
  • U+0020; Space

For each of the following Unicode characters, it is implementation-defined to consider it a whitespace:

  • U+0085; Next Line
  • U+00A0; No-Break Space
  • U+1680; Ogham Space Mark
  • U+2000; En Quad
  • U+2001; Em Quad
  • U+2002; En Space
  • U+2003; Em Space
  • U+2004; Three-Per-Em Space
  • U+2005; Four-Per-Em Space
  • U+2006; Six-Per-Em Space
  • U+2007; Figure Space
  • U+2008; Punctuation Space
  • U+2009; Thin Space
  • U+200A; Hair Space
  • U+2028; Line Separator
  • U+2029; Paragraph Separator
  • U+202F; Narrow No-Break Space
  • U+205F; Medium Mathematical Space
  • U+3000; Ideographic Space

All other characters are never considered a whitespace.

Error

If the string doesn't start with a nested parentheses, the parser shall fall in an erroneous state. Ways that indicates an error include:

  • Monadic failing
  • Returning an erroneous value
  • Raising/Throwing an error

Output

When the parser successfully munched a nested parentheses, the parser shall output the unmunched part of string.

Examples

Valid example

  • When given (), the output is an empty string.
  • When given ( ) Hello, the output is Hello. Note the leading whitespace of the output.
  • when given ((())))), the output is )).

Erroneous example

  • Empty string
  • ((()
  • (()())
  • (H)
  • Hello, world!

Ungolfed solution

C

Returns a null pointer for an error.

#include <stdbool.h>
#include <stdlib.h>

char *readMaybeUnit(char *str) {
    bool p = false;
    unsigned c = 0;
    while (*str != '\0') {
        switch (*str) {
        case '(':
            p = true;
            ++c;
            // FALLTHRU
        case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
            break;
        default:
            goto parseRightParentheses;
        }
        ++str;
    }
    parseRightParentheses: while (*str != '\0') {
        switch (*str) {
        case ')':
            if (1 >= c) {
                if (1 == c)
                    ++str;
                c = 0;
                goto returnReadMaybeUnit;
            }
            --c;
            // FALLTHRU
        case '\t': case '\n': case '\v': case '\f': case '\r': case ' ':
            break;
        default:
            goto returnReadMaybeUnit;
        }
        ++str;
    }
    returnReadMaybeUnit: return p && 0 == c ? str : NULL;
}
\$\endgroup\$
5
  • 7
    \$\begingroup\$ Can you say outright what the task is? It looks like we remove a prefix of open parens followed by an equal number of close parens, with possible whitespace in between. If so, I'm not clear why Hello, world! doesn't just give itself (do we need nonzero parens?) or what's going on with (()()). \$\endgroup\$
    – xnor
    Commented Oct 1, 2020 at 22:39
  • 11
    \$\begingroup\$ It's also probably confusing to people who haven't seen Haskell's parsing or similar that "parse" here actually means "remove". \$\endgroup\$
    – xnor
    Commented Oct 1, 2020 at 22:40
  • 3
    \$\begingroup\$ Also, requiring programs to validate their input is discouraged. \$\endgroup\$ Commented Oct 1, 2020 at 22:47
  • 5
    \$\begingroup\$ @RedwolfPrograms What do you mean by "validate"? This challenge asks for a parser, and a parser is to validate its input anyway. \$\endgroup\$ Commented Oct 1, 2020 at 22:49
  • 2
    \$\begingroup\$ Your ungolfed solution crashes on the third testcase. \$\endgroup\$
    – Noodle9
    Commented Oct 2, 2020 at 23:16

5 Answers 5

6
\$\begingroup\$

Haskell, 83 76 bytes

c?(a:b)|elem a" \t\n\r\v\r"=c?b|a==c=[b]
_?_=[]
f x='('?x>>=(:)<*>f>>=(')'?)

Try it online!

Since this question to imitate Haskell's parsing I thought it would be nice to give this a try using Monadic parsing in Haskell. The result is actually really short. I use [] as my monad because it is just way shorter than Maybe or Either.


What is monadic parsing?

Put simply monadic parsing is a type of parsing in which a parser is a function from a string to some optional type of a the remaining string and some data

type Parser a = String -> Option (a, String)

Here our Option type is a list, and we are just validating rather than producing any data, so our parser looks like:

type Parser a = String -> [ String ]

Where our parser takes some string and returns all possible suffixes of valid parses. The empty string represents a failure to parse because no suffixes means that no valid parse was found.

This way of structuring things makes it super easy to combine parsers. For example if we have a parser p which parses the regex \s*( and a parser q which parses the regex \s*) then we can make a parser that parses the expression \s*(\s*) using the Kleisli arrow

(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)

Meaning the result is p >=> q. We can also do other combinators.


So here's how I use it in my answer.

The first thing we do is implement ?, which takes a character c returns a parser the regex \s*c (where c is the character). Essentially this consumes a prefix made of any amount of whitespace followed by a single character. This is only ever called on ( and ).

With this we implement f which is the parser that the challenge asks for. We don't actually have the Kleisli arrow in Prelude but I will write it as if we did for clarity and then show how we remove Kleisli arrows.

f = ('('?) >=> (:)<*>f >=> (')'?)

So we have three parsers first, it must start with some whitespace followed by a ( then some gobbledygook parser and then it must end with some whitespace followed by a ).

The gobbledygook (:)<*>f can be expressed more clearly as

\ x -> x : f x

Which is to say it is it matches everything the f parser does but also matches the empty string.

So our f parser matches:

Parentheses enclosing, either the empty string or another f.

Now to remove our Kleisli arrows we use >>= which has the similar type signature:

(>>=) :: m a -> (a -> m b) -> m b

So we take an argument from f, pass it to the first parser and change all of our (>=>)s to (>>=)s.

\$\endgroup\$
6
\$\begingroup\$

Python 3.8 (pre-release), 112 bytes

f=lambda s,c=0,p='(':[f(s[1:],c+"()".find(a)%-3+1,max(a,p))if(a:=s[:1])in{p,*"	\n0b0c\r )"}else 0,s][c<1and')'==p]

Try it online!

An attempt without using regular expressions. Returns 0 on error.

  • Thanks to @movatica for saving 4 bytes!
Python 3, 116 bytes
f=lambda s,c=0,p='(':[f(s[1:],c+"()".find(s[:1])%-3+1,max(s[:1],p))if s[:1]in{p,*"	\n0b0c\r )"}else 0,s][c<1and')'==p]

Try it online!

Python 2, 119 bytes
f=lambda s,c=0,p='(':[f(s[1:],c+"()".find(s[:1])%-3+1,max(s[:1],p))if s[:1]in{p}|set("	\n0b0c\r )")else 0,s][`c`+p=="0)"]

Try it online!


Python 2 (non-recursive), 153 bytes
def p(s):c=i=a=0;t="""
while i<len(s):
 if~-s[i].isspace():
	if%r!=s[i]:break
	c+=%s
 i+=1""";exec t%('(','1')+t%(')',"-1\n\tif c==0:a=s[i+1:]");return a

Try it online!

  • Thanks to @ovs for saving 4 bytes!

We could probably save a few more bytes if we returned the original string on error, but then inputs '()' and '' would give the same output ''.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 166 bytes by using %r for string formatting and ~-a[m].isspace() instead of a[m].isspace()-1. If you copy the Code Golf submission from the Share menu, the tabs will be displayed correctly here. \$\endgroup\$
    – ovs
    Commented Oct 4, 2020 at 9:33
  • 1
    \$\begingroup\$ 121 bytes for Python 3 \$\endgroup\$
    – movatica
    Commented Mar 19 at 6:35
4
\$\begingroup\$

Retina 0.8.2, 32 31 bytes

^(\s*\()+(?<-1>\s*\))+(?(1)$.)

Try it online! Link includes test cases. Returns the original string on error. Considers the given control characters as white space, plus any Unicode characters (such as space) in the Separator group, plus U+0085. If only the minimal white space is desired, this can be achieved by prefixing e`. Explanation:

^(\s*\()+

Match some open parentheses at the start of the string.

(?<-1>\s*\))+

Match some close parentheses.

(?(1)$.)

Check that the same number of open and close parentheses were matched.


Delete the matched parentheses.

Alternative solution, also 31 bytes:

r`^(?<-1>\s*\()+(\s*\))+(.*)
$2

Try it online! Link includes test cases. If only the minimal white space is desired, this can be achieved by prefixing e. Explanation:

r`

Start matching at the end of the string and work backwards (like a lookbehind would).

(.*)

Match as much result as possible.

(\s*\))+

Match some close parentheses.

^(?<-1>\s*\()+

Match the open parentheses at the start of the string. The number of close parentheses must be at least as many as the number of open parentheses for the balancing group to succeed, but it can't be more because the (.*) ensures that as few close parentheses are matched as possible.

$2

Keep everything except the matched parentheses.

Previous 32-byte solution that returns the empty string on error:

1!`(?<=^(?<-1>\s*\()+(\s*\))+).*

Try it online! Link includes test cases. If only the minimal white space is desired, this can be achieved by prefixing e. Explanation:

1!`

Output the matched part of the first match.

(?<=^(?<-1>\s*\()+(\s*\))+)

Ensure that the match starts after balanced parentheses. Note that this is a lookbehind, so the match is processed right-to-left - the )s are matched first, then a ( can be matched for each ). There can't be too many )s because the lookbehind would have matched earlier, meaning that this is no longer the first match.

.*

Match the rest of the string. This actually counts as part of the match, and therefore becomes the resulting output.

\$\endgroup\$
2
  • \$\begingroup\$ "would be golfier to output the original string on error but I don't know whether that's valid" I'd say that's actually a valid way for an error. \$\endgroup\$ Commented Oct 2, 2020 at 0:45
  • \$\begingroup\$ @DannyuNDos Thanks, in that case I have two alternative 31-byte solutions! \$\endgroup\$
    – Neil
    Commented Oct 2, 2020 at 11:03
3
\$\begingroup\$

Perl 5, (-p) 22 bytes

s/^(\s*\((?1)?\s*\))//

Try it online!

Using recursive regex. The shorter \s*\((?0)?\s*\) didn't work because of start anchor missing.

The error case is given by the result of substitution operation :

  • 1 - success
  • "" - failed
\$\endgroup\$
3
\$\begingroup\$

Haskell + hgl + TypeApplications, 16 bytes

st<gj<uP(ν @())

Attempt This Online!

Explanation

ν is the general purpose read parser, so when given the () type it basically does exactly the desired task. However, there are two issues

  1. The question wants the remainder, and parsers are generally set up to get the value not the remainder.
  2. The question actually wants what is considered the lowest priority parse, i.e. the parse that trims the least whitespace. Parsers generally like to get higher priority parses

To solve this we just dump the most verbose parser output using uP. gj gets the lowest priority pair and st grabs the result from the pair.

16 bytes

gk$Sw$ivP$ν @()

Attempt This Online!

This version has no post processing after the parse, i.e. the top level function performs a parse.

Explanation

This solves the two issues in a different way. It uses ivP to invert the parse priorities on ν. We use Sw to "swap" the result with the remainder.

At the top level we use gk to get the highest priority parse.

Haskell + hgl, 17 bytes

st<gj<uP(mp()<ν)

Attempt This Online!

Explanation

This is basically the same as the last one, except without type application we can't tell it what type to parse directly. Instead we want to map a function across the parser with the type () -> a where a is any type. This will force a type of () onto the output. Taking () as an input is pretty uncommon. The shortest I could find is mp(), which uses the semigroup action to combine two ()s.

17 bytes

gk$Sw$mp()<ivP ν

Attempt This Online!

This version has no post processing after the parse, i.e. the top level function performs a parse.

Haskell + hgl (no ν), 28 bytes

g=p__<*enP(g?<>p__)
gk$g*>h'

Attempt This Online!

Reflection

I think these do decently, but I have a lot of notes on how to improve.

  • There should be a version of gk to get the lowest priority parse.
  • There should be some parse runners that return the remainder rather than the result.
  • While I did have fun trying to find the shortest way to coerce the type of ν, extremely polymorphic ν should come with built-in ways to do this. The way to do this would be to make a version of ν which a witness value as input, and always returns something of the same type. If this were 3 bytes it would actually save bytes over using a type application in this case.
  • You might notice uP<ν is really just an expensive way to do reads. I don't actually export any version of reads. This sort of makes sense, I haven't really invested the time into making Read related functions, but if ν exists, reads should probably exist.
  • (p__*>) and (<*p__) to trim leading and trailing whitespace respectively are both way too expensive, there should be built in shortcuts.
  • There should be a flip of mpY.
  • lSo and lMy should return a specific type, probably Nat.
  • I noticed there's no version of py which counts the number of results. It wouldn't be helpful in any way here, but I feel like that should exist.
  • The recursive regex in the perl answer is sort of interesting. The option for this right now seems like:
    gk$Sw$rX"/w*/(/r?/w*/)"
    
    which are shorter than the answer without ν but longer than the other ones.
  • Looking at the regex, there should be a version of gk for regexes.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.