Find a way to avoid writing O(n^2) conversions

[djspiewak]

This is the current state of the ^^ syntax in parseback. It is done in this way to achieve two goals:

• The parameter to ^^ should be an arity-n function, where n is the number of chained type parameters within the target Parser of the form A ~ B ~ ... ~ N
• The parameter to ^^should be fully type inferred, allowing for the use of lambdas without explicit type parameters

The reason there is a quadratic number of cases stems from the fact that we need to provide a separate, specific syntax class for each possible reassociation of the ~ type constructor. Obviously it would be much nicer to just write a linear number of cases (one for each arity, presumably) and then build some implicit machinery which would convince implicit search to generate the quadratic portion, but my efforts in that direction have thus far been unsuccessful.

Paging @milessabin and @travisbrown for thoughts and assistance if they feel so inclined!

[milessabin]

Possibly related SO Q&A.

[djspiewak]

@milessabin Similar, but not quite the same. This would all actually be quite easy if the sequential combinator produced a Parser[A :: B :: HNil] rather than a Parser[A ~ B], but I want to avoid the dependency if I can. It would also be very easy if I didn't have to worry about associativity, which is where things get especially tricky. That particular SO question deals with pattern extraction, which has explicit associativity. Because I have to infer associativity and types at the same time, guided solely by the Parser[E] (where E has some form) and the arity of the FunctionN type given, it gets a little more annoying.

Oh, tiny bit of background: type ~[+A, +B] = (A, B)

tl;dr: I tried what you suggest, and it doesn't leave enough structure in place for scalac to infer both associativity and specific types. I still think that the answer is probably somewhere along that line, but the direct approach didn't work for me.