Should have had

levels = (1, [1..b-1]) : [(l+1, concatMap (generate (l+1)) prefix) | (l, prefix) <- levels, not (null prefix)]

The orignal will be left forever joining an infinite stream of empty lists, when there are no more polydivisible numbers available.

You should add more edge cases to the tests, such as adjacent parallel edges and zero-length edges.

Random tests are producing false negatives:

Falsifiable (after 74 tests and 37 shrinks): 
[(-37,[-2,51]),(-2,[-37]),(51,[-37,-2]),(-2,[51])]
3 /= 2

Falsifiable (after 27 tests and 18 shrinks): 
[(17,[17]),(17,[17])]
1 /= 2

Falsifiable (after 28 tests and 30 shrinks): 
[(23,[-20]),(-7,[23,-20]),(23,[-7]),(-20,[-7]),(-20,[23])]
3 /= 2

Falsifiable (after 61 tests and 37 shrinks): 
[(-2,[-51,18]),(18,[-51]),(-51,[-2,18]),(18,[-2])]
3 /= 2

This seems to assume that there are no characters after any closing parenthesis. The specification only mentions the last closing parenthesis.

How is this a best practice with an exponential running time and memory consumption?