Related: Clearly parenthesize APL trains


In the most basic form, APL has two kinds of tokens: arrays and functions. For this challenge, we will use a lowercase letter a-z for an array, and an uppercase letter A-Z for a function. Furthermore, we will assume each character is a token of its own; Fx is equivalent to F x.

APL has two ways to call a function: monadic (taking one argument) and dyadic (taking two arguments). Monadic application is written in prefix F x, and dyadic one is written in infix x F y. There's nothing like "operator precedence"; an APL expression is always evaluated from right to left, which can be overridden with parentheses ().

x F G y -> x F (G y)
F x G y -> F (x G y)
x F y G z -> x F (y G z)
(F x) G H y -> (F x) G (H y)

A train is a way to compose functions to derive a more complex function. In essence, a train is formed when the rightmost token is a function. Here are the rules for 2- and 3-token trains:

(F G H) x -> (F x) G (H x)
(u G H) x -> u G (H x)
(G H) x -> G (H x)

x (F G H) y -> (x F y) G (x H y)
x (u G H) y -> u G (x H y)
x (G H) y -> G (x H y)

For 4-token and longer trains, the rightmost 3 tokens are recursively grouped to form a derived function until 2 or 3 tokens remain. As a whole, it can be thought of as follows:

Odd-length trains
(V D V D ... V D V) x -> (V x) D (V x) D ... (V x) D (V x)
x (V D V D ... V D V) y -> (x V y) D (x V y) D ... (x V y) D (x V y)

Even-length trains
(M V D V D ... V D V) x -> M (V x) D (V x) D ... (V x) D (V x)
x (M V D V D ... V D V) y -> M (x V y) D (x V y) D ... (x V y) D (x V y)

If an array u appears at the V position (other than the last), replace the cooresponding (V x) or (x V y) simply with u. An array appearing at M or D position is a syntax error.

Note that trains may also have sub-expressions that evaluate to an array or a function:

x ((D a) F G (u H J) K) y
   Expand 5(odd)-token train, leftmost V position being an array (D a)
-> (D a) F (x G y) (u H J) (x K y)
   Expand 3(odd)-token train (u H J)
-> (D a) F (u H (x G y) J (x K y))


Given a line of APL expression that evaluates to an array (which may or may not include one or more trains), convert it into an equivalent expression without a train.

You can assume that the input is valid under the rules stated above, and it doesn't contain any spaces. You don't need to worry too much about parentheses or spaces in the output; lacking or redundant parentheses/spaces are fine as long as they represent the equivalent expression.

Standard rules apply. The shortest code in bytes wins.

Test cases

x(XY)y -> X(xYy)
uKKKv -> uKKKv
U(xVW)yZa -> UxVWyZa
x(XXxYYYdDD)y -> (xXy)XxY(xYy)YdDxDy
a((DEF)GHJ)Kb -> (D(aGKb)HaJKb)EF(aGKb)HaJKb
c((k(PQRSTU)m)(VW)(XY)(ZA)BCD)n -> V(P(kQm)R(kSm)T(kUm))WZ(XcYn)A(cBn)C(cDn)
  • \$\begingroup\$ explicitize \$\endgroup\$ – ngn Jun 5 '20 at 11:47

APL (Dyalog Classic), 63 59 58 54 52 51 bytes

∊⍎'.[A-Z].'⎕r'{0::&⍵⋄''() '',⍪⍺&⍵}'⊢'\w'⎕r'''&'''⊢⍞

Try it online!

put all letters in quotes, replace uppercase letters with dfns that return either "(left) self right" or "self right" depending on the presence of a left arg, and execute.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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