Is it an ordinal?

Question

Background (feel free to skip)

Ordinals are the abstract representation of well-orders. A well-order of a set is a total order, which basically means that every element in the set can be compared against any other element in the set, and one of them is either smaller or larger. Also there are no cycles.

The crucial difference between total orders and well-orders is that a well order is always well-founded. This means that every nonempty subset of a well-ordered set has a least element, which implies that an infinite descending chain is impossible; An infinite sequence \$a_1\gt a_2\gt a_3\gt a_4 \gt ...\$ doesn't exist.

This is useful for many things, one of them being proving that recursion terminates. For example, here is the definition of the Ackermann function:

\$ A(0,n)=n+1\\ A(m+1,0)=A(m,1)\\ A(m+1,n+1)=A(m,A(m+1,n)) \$

Can you see why it always terminates? We call the Ackermann function with a 2-tuple of natural numbers, and when we recurse, the tuple is smaller under the standard tuple ordering (lexicographic ordering: first compare the first elements, then the second ones). Because the standard tuple ordering is a well-ordering (\$\omega^2\$ in fact), the recursion must eventually terminate.

With the knowlege that \$\omega^2\$ is well-founded we were able to prove that the Ackermann function is total. There are of course larger ordinals, one of them being \$\varepsilon_0\$. All ordinals below \$\varepsilon_0\$ can be represented with a simple ordinal notation using ragged lists.

We can use the standard lexicographic ordering of ragged lists. However there is a problem. The ordering, while a total order, is not a well order. For example, [ [[]] ] > [ [], [[]] ] > [ [], [], [[]] ] > [ [], [], [], [[]] ] > ...

There is a solution though. We can just make sure that in every list, the elements are in decreasing order. This means that [ [], [[]] ] is not an ordinal, since [[]] is larger than []

Here is a table of some valid ordinal notations

Notation	Value
[]	\$0\$
[[]]	\$\omega^0=1\$
[[],[]]	\$\omega^0+\omega^0=2\$
[[[]]]	\$\omega^{\omega^0}=\omega\$
[[[[]],[]],[],[]]	\$\omega^{\omega^{\omega^0}+\omega^0}+\omega^0+\omega^0=\omega^{\omega+1}+2\$

Task

You are given a ragged list containing only lists. Your task is to determine if that list is an ordinal. A list is an ordinal iff each of its elements are ordinals, and the list is decreasing.

Comparison between ordinals can be done with simple lexicographic comparison. That is, given two lists, compare the first elements. If they are equal, compare the second ones and so on. If one of the lists runs out of elements, that list is smaller.

For example, say you got the ragged list [a,b,c,d]. You must first make sure that a, b, c and d are ordinals. Then, make sure that \$a\ge b\ge c\ge d\$, using lexicographic ordering. If both conditions are true, then it's an ordinal. When there is just one element in the list, the second condition is always true. And when the list is empty, both conditions are vacuously true.

Standard decision-problem rules apply.

Test cases

[] -> True
[[]] -> True
[[[]]] -> True
[[], []] -> True
[[[[]]]] -> True
[[[], []]] -> True
[[[]], []] -> True
[[], [[]]] -> False
[[], [], []] -> True
[[[[[]]]]] -> True
[[[[], []]]] -> True
[[[[]], []]] -> True
[[[], [[]]]] -> False
[[[], [], []]] -> True
[[[[]]], []] -> True
[[[], []], []] -> True
[[[]], [[]]] -> True
[[[]], [], []] -> True
[[], [[[]]]] -> False
[[], [[], []]] -> False
[[], [[]], []] -> False
[[], [], [[]]] -> False
[[], [], [], []] -> True
[[[[[[]]]]]] -> True
[[[[[], []]]]] -> True
[[[[[]], []]]] -> True
[[[[], [[]]]]] -> False
[[[[], [], []]]] -> True
[[[[[]]], []]] -> True
[[[[], []], []]] -> True
[[[[]], [[]]]] -> True
[[[[]], [], []]] -> True
[[[], [[[]]]]] -> False
[[[], [[], []]]] -> False
[[[], [[]], []]] -> False
[[[], [], [[]]]] -> False
[[[], [], [], []]] -> True
[[[[[]]]], []] -> True
[[[[], []]], []] -> True
[[[[]], []], []] -> True
[[[], [[]]], []] -> False
[[[], [], []], []] -> True
[[[[]]], [[]]] -> True
[[[], []], [[]]] -> True
[[[[]]], [], []] -> True
[[[], []], [], []] -> True
[[[]], [[[]]]] -> False
[[[]], [[], []]] -> False
[[[]], [[]], []] -> True
[[[]], [], [[]]] -> False
[[[]], [], [], []] -> True
[[], [[[[]]]]] -> False
[[], [[[], []]]] -> False
[[], [[[]], []]] -> False
[[], [[], [[]]]] -> False
[[], [[], [], []]] -> False
[[], [[[]]], []] -> False
[[], [[], []], []] -> False
[[], [[]], [[]]] -> False
[[], [[]], [], []] -> False
[[], [], [[[]]]] -> False
[[], [], [[], []]] -> False
[[], [], [[]], []] -> False
[[], [], [], [[]]] -> False
[[], [], [], [], []] -> True
[[[[[[[]]]]]]] -> True
[[[[[[], []]]]]] -> True
[[[[[[]], []]]]] -> True
[[[[[], [[]]]]]] -> False
[[[[[], [], []]]]] -> True
[[[[[[]]], []]]] -> True
[[[[[], []], []]]] -> True
[[[[[]], [[]]]]] -> True
[[[[[]], [], []]]] -> True
[[[[], [[[]]]]]] -> False
[[[[], [[], []]]]] -> False
[[[[], [[]], []]]] -> False
[[[[], [], [[]]]]] -> False
[[[[], [], [], []]]] -> True
[[[[[[]]]], []]] -> True
[[[[[], []]], []]] -> True
[[[[[]], []], []]] -> True
[[[[], [[]]], []]] -> False
[[[[], [], []], []]] -> True
[[[[[]]], [[]]]] -> True
[[[[], []], [[]]]] -> True
[[[[[]]], [], []]] -> True
[[[[], []], [], []]] -> True
[[[[]], [[[]]]]] -> False
[[[[]], [[], []]]] -> False
[[[[]], [[]], []]] -> True
[[[[]], [], [[]]]] -> False
[[[[]], [], [], []]] -> True
[[[], [[[[]]]]]] -> False
[[[], [[[], []]]]] -> False
[[[], [[[]], []]]] -> False
[[[], [[], [[]]]]] -> False
[[[], [[], [], []]]] -> False
[[[], [[[]]], []]] -> False
[[[], [[], []], []]] -> False
[[[], [[]], [[]]]] -> False
[[[], [[]], [], []]] -> False
[[[], [], [[[]]]]] -> False
[[[], [], [[], []]]] -> False
[[[], [], [[]], []]] -> False
[[[], [], [], [[]]]] -> False
[[[], [], [], [], []]] -> True
[[[[[[]]]]], []] -> True
[[[[[], []]]], []] -> True
[[[[[]], []]], []] -> True
[[[[], [[]]]], []] -> False
[[[[], [], []]], []] -> True
[[[[[]]], []], []] -> True
[[[[], []], []], []] -> True
[[[[]], [[]]], []] -> True
[[[[]], [], []], []] -> True
[[[], [[[]]]], []] -> False
[[[], [[], []]], []] -> False
[[[], [[]], []], []] -> False
[[[], [], [[]]], []] -> False
[[[], [], [], []], []] -> True
[[[[[]]]], [[]]] -> True
[[[[], []]], [[]]] -> True
[[[[]], []], [[]]] -> True
[[[], [[]]], [[]]] -> False
[[[], [], []], [[]]] -> True
[[[[[]]]], [], []] -> True
[[[[], []]], [], []] -> True
[[[[]], []], [], []] -> True
[[[], [[]]], [], []] -> False
[[[], [], []], [], []] -> True
[[[[]]], [[[]]]] -> True
[[[], []], [[[]]]] -> False
[[[[]]], [[], []]] -> True
[[[], []], [[], []]] -> True
[[[[]]], [[]], []] -> True
[[[], []], [[]], []] -> True
[[[[]]], [], [[]]] -> False
[[[], []], [], [[]]] -> False
[[[[]]], [], [], []] -> True
[[[], []], [], [], []] -> True
[[[]], [[[[]]]]] -> False
[[[]], [[[], []]]] -> False
[[[]], [[[]], []]] -> False
[[[]], [[], [[]]]] -> False
[[[]], [[], [], []]] -> False
[[[]], [[[]]], []] -> False
[[[]], [[], []], []] -> False
[[[]], [[]], [[]]] -> True
[[[]], [[]], [], []] -> True
[[[]], [], [[[]]]] -> False
[[[]], [], [[], []]] -> False
[[[]], [], [[]], []] -> False
[[[]], [], [], [[]]] -> False
[[[]], [], [], [], []] -> True
[[], [[[[[]]]]]] -> False
[[], [[[[], []]]]] -> False
[[], [[[[]], []]]] -> False
[[], [[[], [[]]]]] -> False
[[], [[[], [], []]]] -> False
[[], [[[[]]], []]] -> False
[[], [[[], []], []]] -> False
[[], [[[]], [[]]]] -> False
[[], [[[]], [], []]] -> False
[[], [[], [[[]]]]] -> False
[[], [[], [[], []]]] -> False
[[], [[], [[]], []]] -> False
[[], [[], [], [[]]]] -> False
[[], [[], [], [], []]] -> False
[[], [[[[]]]], []] -> False
[[], [[[], []]], []] -> False
[[], [[[]], []], []] -> False
[[], [[], [[]]], []] -> False
[[], [[], [], []], []] -> False
[[], [[[]]], [[]]] -> False
[[], [[], []], [[]]] -> False
[[], [[[]]], [], []] -> False
[[], [[], []], [], []] -> False
[[], [[]], [[[]]]] -> False
[[], [[]], [[], []]] -> False
[[], [[]], [[]], []] -> False
[[], [[]], [], [[]]] -> False
[[], [[]], [], [], []] -> False
[[], [], [[[[]]]]] -> False
[[], [], [[[], []]]] -> False
[[], [], [[[]], []]] -> False
[[], [], [[], [[]]]] -> False
[[], [], [[], [], []]] -> False
[[], [], [[[]]], []] -> False
[[], [], [[], []], []] -> False
[[], [], [[]], [[]]] -> False
[[], [], [[]], [], []] -> False
[[], [], [], [[[]]]] -> False
[[], [], [], [[], []]] -> False
[[], [], [], [[]], []] -> False
[[], [], [], [], [[]]] -> False
[[], [], [], [], [], []] -> True

Answer 1

Haskell + free, 34 bytes

To represent ragged lists we use the free package and represent them as free monads generated by the list.

f(Free x)=all f x&&scanl1 min x==x

ATO seems to be broken and TIO doesn't have free so no link for now. :(

Since there are now elements in the list a better representation of this type would be Fix []. However I don't know of any Haskell libraries (other than hgl) which export a fully featured version of this.

Answer 2

Python, 43 bytes

f=lambda a:1in map(f,a)or a<sorted(a)[::-1]

Attempt This Online!

Outputs inverted: False for valid ordinals, and True for invalid ordinals.

This is a DeMorgan's Law conversion of the below, which would be a completely direct translation of the problem statement:

46 bytes

f=lambda a:all(map(f,a))and a==sorted(a)[::-1]

Attempt This Online!

But by inverting it, all becomes any, which can then be changed to 1in (using this tip of mine), which saves a byte on parentheses.

Also, and becomes or, for another -1.

Finally, by the magic of the properties of lexicographic comparison, we can use < instead of != in the inverted form, for a total of 3 bytes saved.

---

Python, 44 bytes

f=lambda a:{*map(f,a)}<={a==sorted(a)[::-1]}

Attempt This Online!

Bonus answer, outputting non-inverted.

Answer 3

Rust Nightly + #![feature(is_sorted)], 101 bytes

#[derive(PartialOrd,PartialEq)]
struct T(Vec<T>);fn f(t:&T)->bool{t.0.is_sorted()&&t.0.iter().all(f)}

Playground Link

Answer 4

Python 2, 35 bytes

f=lambda a:[`a`][a<sorted(a,key=f)]

Attempt This Online!

Heavily based on (same logic as) @pxeger's python answer.

My additions:

1. Use the fact that string representation of lists has the correct ordering.
2. Use sort key to save map construction.
3. Use exit code for signalling freeing up return value for use with 1,2.

Answer 5

Factor, 40 bytes

[ [ [ after=? ] monotonic? ] deep-all? ]

Try it online!

Using a depth-first search, is every element non-increasing?

Answer 6

Jelly, 7 bytes

ṢṚ⁼ȧ߀Ạ

Try it online!

Test all cases given

Explanation

ṢṚ⁼ȧ߀Ạ    given a candidate list:
   ȧ        check that the following two conditions are satisfied:
  ⁼          1. the list is equal to
 Ṛ              the reverse of
Ṣ               the sorted version of the list
     ߀Ạ     2. and the same is true for every element in the list

Answer 7

Charcoal, 22 bytes

¹⊞υＡＦυＷι«⊞υ§ι±¹¿‹⌊ι⊟ι⎚

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a valid ordinal, nothing if invalid. Explanation:

¹

Assume the input is an ordinal.

⊞υＡ

Start by checking the input.

Ｆυ

Loop through the ragged lists to check.

Ｗι«

Loop though the elements of the current ragged list.

⊞υ§ι±¹

Add the last element of the current ragged list to the list of lists to check.

¿‹⌊ι⊟ι⎚

Check that the last element is also the minimum element, and also remove it from the current ragged list, so that the rest of the current ragged list can be checked.

Note that Charcoal's input format is a list of inputs, so if you accidentally enter [[], [[]]] you're actually providing two inputs, and the program will happily tell you that the first input is a valid ordinal.