Generate all brace-strings of length n

Prolog, 69 bytes

s-->[];e,s.
e-->"*";"(",s,")";"[",s,"]".
b(N,A):-length(A,N),s(A,[]).

One of the most interesting properties of Prolog is that in many cases it's capable of running a program backwards; for example, instead of testing to see if something's true, you can generate all solutions for which it's true, and instead of checking the length of a string, you can generate all strings with a given length. (Another nice property of Prolog is that it requires whitespace after the end of each predicate definition, and a newline can be inserted as cheaply as a space; thus even golfed programs are often fairly readable.)

The above defines a predicate (the equivalent of a function) b which tests to see if a string has a given length and is a "brace string" as defined in the question. Specifically, it does this via Prolog's grammar/regex/pattern-match support that gives some nice, short sugar for defining this sort of expression (apparently this is standard/portable, but I was unaware of this while originally writing the answer, and thus assumed the answer would work on only one Prolog implementation; it seems it works on every implementation that complies with the standards, though). The program can be translated into English fairly directly; the first two lines say "an s is an empty string, or an e followed by an s; an e is an asterisk, or an s in parentheses, or an s in square brackets". The third line can be interpreted as "The b of N can be A if A is a list with length N and A is an s followed by a null string."

I took some care to write s (and thus b) so that they match each "brace string" in exactly one way (which is the reason that both s and e have to exist, rather than grouping them into one predicate). This makes them both entirely reversible; thus b can be used to generate all "brace strings" of a given length, in addition to testing if a string is a brace string of a given length (it can also be used a third way round, to figure out the length of a brace string, but that is almost certainly its least useful mode of operation). The implementation is recursive, e.g. to generate an s, the code will generate all possible es that are no longer than the required length of the output, and append all possible ss that fit in the remaining space to them; because I specified the length of the argument in advance (within b), the Prolog engine knows that it can't generate output that's longer than the given length, which allows the recursion to terminate.

Here's an example of the program in operation:

| ?- b(4,A),format("~s ",[A]),fail.
**** **() **[] *()* *(*) *[]* *[*] ()** ()() ()[] (*)* (**) (()) ([]) []** []() [][] [*]* [**] [()] [[]]

Haskell, 101 94 bytes

7 bytes saved by Zgarb!

b 0=[""]
b n=[x++y|k<-[1..n],x<-u k,y<-b$n-k]
u 1=["*"]
u n=[a:s++b|s<-b$n-2,a:b<-["()","[]"]]

Almost straightforward, following the definition, but with the "" case moved.

Use:

*Main> map b [0..3]
[[""],["*"],["**","()","[]"],["***","*()","*[]","()*","[]*","(*)","[*]"]]
*Main> length $ b 10
21595

(The second computation takes less than a second on a slow machine.)

I'd also like to share the result of another approach I came up with while thinking about generating functions. It defines a list b of lists of strings such that b!!n contains all brace-strings of length n. Similarly, u!!n contains all atoms of size n-1. One nice thing is that the code is not using any numbers. It is not completely golfed: u and i could be inlined, and it certainly misses a few other golfing opportunities. Unfortunately, it doesn't look like it can be made shorter than the first version, but it computes length $ b !! 10 even faster.

b=[""]:b%u
u=["*"]:map i b
i=concatMap(\s->['(':s++")",'[':s++"]"])
(b:c)%f=zipWith(++)[[x++y|x<-b,y<-e]|e<-f]([]:c%f)

Mathematica, 116 bytes

#<>""&/@Select[Characters@"*([)]"~Tuples~#,(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&]&

Explanation

Characters@"*([)]"

Find the characters of the string "*([)]", giving the List {"*", "(", "[", ")", "]"}.

... ~Tuples~#

Find the tuples of the above list with length n.

(#/."*"->Nothing//.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b})=={}&

Unnamed Boolean function to find whether the tuple is balanced:

#/."*"->Nothing

Delete all "*" in the input.

... //.{a___,"(",")",b___}|{a___,"[","]",b___}:>{a,b}

Repeatedly delete all consecutive occurrences of "(" and ")" or "[" and "]" until the input does not change.

... =={}

Check whether the result is an empty List.

Select[ ... , ... ]

Find the tuples that give True when the Boolean function is applied.

#<>""&/@

Convert each List of characters into Strings.