# Evaluation order of an APL n-train

## Description

APL trains are a series of functions, that get applied to an argument in this way:

```
(f g) x = f g x
(f g h) x = (f x) g (h x)
(a b c d e f) x = (a (b c (d e f))) x = a (b x) c (d x) e (f x)
```

Trains evaluate from the right to the left, so in the last example, (f x) is evaluated, then (d x), then (d x) e (f x), then (b x), etc.

The final evaluation order there is FDEBCA, or using numbers instead, 6 4 5 2 3 1.

## Challenge

Given a number n, output the evaluation order of a train with n functions. Your result can be 0 indexed or 1 indexed.

## Examples

Here are the first 10 outputs starting from n=1 (1 indexed)

```
1 (0 if 0 indexed)
2 1 (1 0 if 0 indexed)
3 1 2
4 2 3 1
5 3 4 1 2
6 4 5 2 3 1
7 5 6 3 4 1 2
8 6 7 4 5 2 3 1
9 7 8 5 6 3 4 1 2
10 8 9 6 7 4 5 2 3 1
```

BQN, 8 bytesSBCS ``` ⍒↕+2| …

9d ago

[Jelly], 8 bytes ṖUs2Uṭ …

9d ago

[Jelly], 5 bytes ḶHĊUỤ …

9d ago

[Haskell], 52 48 45 42 bytes …

7d ago

posix SH + [GNU sed], 43 bytes …

9d ago

Japt, 10 bytes o ÅÔò cÔ …

2d ago

[Husk], 8 bytes ηÖ↔mo⌈½ …

7d ago

## 7 answers

# Jelly, 8 bytes

```
ṖUs2UṭµF
```

-1 byte thanks to caird coinheringaahing

(Also posted on Stack Exchange by myself)

```
ṖUs2UṭµF Main Link
Ṗ pop (remove last element; for numbers, comes with an implicit range)
U reverse
s2 slice into chunks of length 2
U reverse each chunk
ṭ tack; prepend the input
µ (new chain)
F flatten the list
```

#### 0 comments

#
BQN, 8 bytes^{SBCS}

```
⍒↕+2|⊢+↕
```

The solution itself is an 8-train, so its evaluation order is given by the sequence `7 5 6 3 4 1 2 0`

: first the rightmost `↕`

, then the `⊢`

, then the `+`

between them, and so on—it's fully expanded below. Although it's organized as a train, the computation itself doesn't take advantage of BQN's support for trains.

```
⍒↕+2|⊢+↕ # Tacit function (suppose 𝕩=3)
↕ # Range of 𝕩 0‿1‿2
⊢ # 𝕩, unchanged 3
+ # Add 3‿4‿5
2 # 2
| # Remainder mod ^ 1‿0‿1
↕ # Range again 0‿1‿2
+ # Add 1‿1‿3
⍒ # Descending grade 2‿0‿1
```

The idea is to start with ascending indices, then group them into mostly-twos by adding one to the first part of each pair. We do this by taking indices modulo 2. However, this means the first pair starts on element index 1—in english, the second element—which is correct for even lengths but wrong for odd lengths. So we flip the odd lengths by adding `𝕩`

to the range. Subtracting would also work, in either order: perhaps a more intuitive version is `⊢-↕`

, which is the distance from each position to one after the end.

After doing this we have a number for each function, and the ordering goes from high to low numbers but left to right for functions with the same number. Descending Grade does exactly this.

#### 0 comments

#
Haskell, ~~52~~ ~~48~~ ~~45~~ 42 bytes

Caught mistake thanks to rak1507

Saved 3 bytes thanks to Hakerh400

```
f n=n:g[n-1,n-2..1]
g(b:c:t)=c:b:g t
g t=t
```

`g`

takes the rest of the trains.

```
-- This is a fork, so append c (monad) and b (dyad)
-- and continue with the rest of the train
g(b:c:t)#=[c,b]++g t
-- t is either empty or a single monad, so finish it off
g t=t
```

`f`

simply starts it off with the last function `n`

and the other trains `1..n-1`

(in reverse).

```
f n=n:g[n-1,n-2..1]
```

#### 3 comments

This doesn't seem to give the right answers

`[c,b]++g t`

---> `c:b:g t`

@Hakerh400 Thanks, I don't know how I missed that.

# posix SH + GNU sed, 43 bytes

```
seq $1|tac|sed -zE 's/(\n.+)(\n.+)/\2\1/mg'
```

```
seq $1 # 1..the argument (inclusive)
|tac| # reverse
sed # replace
-z # null terminated. basically this means that \n is
# treated as a normal character, needed because
# seq and tr operate on lines
E # extended regex so we can use () instead of \(\)
' do this replacement '
s/(\n.+)(\n.+)/\2\1/mg
s/ / /mg # replace all occurences of
\n.+ # a newline followed by non-newlines
# the (GNU extension) m modifier makes
# . not match a newline
( )(....) # twice
/ # with
\2\1 # swap their places
```

# posix SH, 50 bytes

```
seq $1|tac|sed -zE 's/(\n[^\n]+)(\n[^\n]+)/\2\1/g'
```

Old 52 bytes, outputting spaces:

```
seq -s' ' $1 -1 1|sed -r 's/( [^ ]+)( [^ ]+)/\2\1/g'
```

#### 0 comments

# Jelly, 5 bytes

```
ḶHĊUỤ
```

Uses xash's method over on CGCC

## How it works

```
ḶHĊUỤ - Main link. Takes n on the left
Ḷ - Range from 0 to n-1
H - Halve
Ċ - Ceiling
U - Reverse
Ụ - Grade; Sort the indices of n by its elements
```

## 2 comments

Is it alright if we number them

`n..1`

instead of`1..n`

? — user 9 days agoI'm going to be harsh and say no sorry — rak1507 9 days ago