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, 2020 at 11:47

3 Answers 3


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.


Python3, 887 bytes:

def p(s):
 while s and(S:=s[0])!=')':
  if S.isalpha():r+=[s[0]]
 return r,s
F=lambda x:(O:=ord(str(x)[0]))<=91 and(64<O<91 or all(F(i)for i in x[-2:]))
R=lambda x:[i for i in x if i]
def f(s,l=0,r=0):
 if F(s):
  while s:
   if F(S:=s.pop(0))==0:J+=[S]
    if len(s)>1 and F(s[0])==0:J+=[[S,s.pop(0)]]
  while s:
   if F(s[0])==0:c+=[s[0]];s=s[1:];continue
   a,b=s[:2];c+=[a,f(R([l,b,r]))if F(b) else f(b)];s=s[2:]
  return f(c)
 while s:
  if F(j:=s.pop(0)) and type(j)==list:
   c+=[f(j,l=c and not F(c[-1])and c.pop(),r=f(s))]
 return c
P=lambda e,l=0:e if str==type(e)else '('*(Y:=(l>0 and len(e)>1))+''.join(P(i,l+1)for i in e)+')'*Y
M=lambda s:P(f(p(s)[0]))

Try it online!

This ended up being longer than I had originally anticipated, but this is an intriguing problem, and I thought I would add a non-APL, parsing-based solution.


Tamsin, 348 bytes


Try it online!

Ungolfed version:

expr1 = [expr2] -> L & function -> F & expr1 -> R & apply(F, [L, R])
      | expr2.

expr2 = "(" & expr1 -> E & ")" & E
      | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l"
      | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x"
      | "y" | "z".

function = "(" & (function | expr2)/nil/list -> T & ")" & T
         | !(expr2 | ")") & any.

apply([F, G, H | T], A) = apply(H, A) -> L
                        & apply(F, A) -> R
                        & apply(G, [L, R]) -> R
                        & apply([R | T], A).

apply([F | G], A) = apply(F, A) -> R & apply(G, [nil, R]).

apply(F, [L, R]) = n @ F & R
                 | expr1 @ F
                 | n @ L & '' + F + R
                 | '(' + L + ')' + F + R.

n = “nil“.

Unfortunately Tamsin does not have a easy way to match only uppercase/lowercase letters, so we need to do "a"|"b"|...|"z" for matching arrays, though we can take a shortcut for functions by just matching any char that cannot be matched as a array and is not ( and ) as a bonus this means symbols (like +, -, ×, etc.) are considered functions.


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.