Products all the way down

You are probably familiar with the Cartesian product. It takes two lists and creates a list of all pairs that can be made from an element of the first and an element from the second:

$$\ \left[1,2\right] \times \left[3,4\right] = \left[(1,3),(1,4),(2,3),(2,4)\right] \$$

Here the order of the result is such that the pairs whose first element is earlier in the first list come earlier in the result, and if the first elements come from the same element the pair whose second element comes first is earlier.

Now we can also have a generalized Cartesian product which takes 3 arguments, two lists and a function to combine pairs.

So for example if we wanted to find all ways to add an element of the first list to an element of the second list:

$$\ \mathrm{Cart} : \left((A,B) \rightarrow C, [A], [B]\right)\rightarrow[C]\\ \mathrm{Cart}\left(+,[1,2],[3,4]\right) = [4,5,5,6] \$$

This is the same as taking the regular Cartesian product and then adding up each pair.

Now with this generalized Cartesian product we are going to define the "product all the way down"

$$\ a\otimes b = \mathrm{Cart}\left(\otimes, a,b\right) \$$

This recursive definition is a little bit mind bending. $$\\otimes\$$ takes a ragged list containing nothing but lists all the way down and combines each pair of elements using itself.

Lets work through some examples. The simplest example is $$\[\space]\otimes[\space]\$$. Since the generalized Cartesian product of an empty list with anything is the empty list it doesn't matter that this is recursive the answer is just $$\[\space]\otimes[\space] = [\space]\$$. There are two elements to combine so there are no ways to combine two elements.

The next example is $$\[[\space]]\otimes[[\space]]\$$, here we have some elements. The regular Cartesian product of these is $$\[([\space],[\space])]\$$, we already know how to combine $$\[\space]\$$ with $$\[\space]\$$ so we can do that. Our result is $$\[[\space]]\$$.

Ok Let's do $$\[[\space],[[\space]]]\otimes[[[\space]]]\$$. First we take the Cartesian product,

$$\ [([\space],[[\space]]),([[\space]],[[\space]])] \$$

Then we combine each with $$\\otimes\$$:

$$\ \begin{array}{ll} [[\space]\otimes[[\space]],&[[\space]]\otimes[[\space]]] \\ [[\space],&[[\space]]\otimes[[\space]]] \\ [[\space],&[[\space]\otimes[\space]]] \\ [[\space],&[[\space]]] \\ \end{array} \$$

Your task is to take two finite-depth ragged lists and return their "product all the way down".

Answers will be scored in bytes with the goal being to minimize the size of the source code.

Test cases

If you are having difficulty understanding please ask rather than try to infer the rules from test cases.

[] [] -> []
[[]] [[]] -> [[]]
[[],[[]]] [[[]]] -> [[],[[]]]
[[[[]]]] [] -> []
[[],[[]],[]] [[],[[]]] -> [[],[],[],[[]],[],[]]

• wow u sure do like ragged-lists this is like the 5th one in a row! Jan 18, 2022 at 11:29
• This is more of a puzzle for Haskell's type-checker than a programming problem! Jan 18, 2022 at 11:33
• @pxeger To do it in Haskell you can use the fixed point combinator. There's a nice elegant way to do this, which in fact inspired this challenge in the first place. Jan 18, 2022 at 11:35

APL (Dyalog Unicode), 17 bytes

Anonymous infix lambda.

{0∊≢¨⍺⍵:⍬⋄,⍵∘.∇⍺}


Try it online!

{} "dfn"; left argument is ⍺ and right argument is ⍵:

0∊ Is zero a member of…
≢¨ the length of each of…
⍺⍵ the arguments?
:⍬ If so, return the empty list.

⋄ Otherwise,…
, ravel (flatten)…
⍵∘.∇⍺ the Cartesian self-product of the reversed arguments.

Wolfram Language (Mathematica), 13 bytes

#0/@Tuples@#&


Try it online!

Takes input as a list of two ragged lists.

Python, 42 bytes

f=lambda X,Y:[f(x,y)for x in X for y in Y]

Attempt This Online!

The obvious.

Pip-xp, 6 bytes

fM$CPa  Attempt This Online! Explanation Same approach as Jonathan Allan's Jelly answer: fM$CPa
a  ; The argument, a list of two lists
\$CP   ; Fold on Cartesian product
fM      ; Map the main function over the resulting list of pairs


Jelly, 4 bytes

Œpß€


A monadic link accepting a list of the two ragged lists that yields their product-all-the-way-down.

Try it online!
Or see the test-suite (The footer parses and reformats like the question for ease of comparison)

How?

Œpß€ - Link, "f": list of lists (initially the two inputs), A:
Œp   - Cartesian product of A's items
€ - for each resulting list, a:
ß  -   call this Link - i.e. f(a)


jq, 24 bytes

def f:[combinations|f];f


Try it online!

Vyxal, 4 bytes

λΠvx


Try it Online!

Port of Jonathan Allan's Jelly answer.

Explanation

λ    # Start a lambda function
Π   # Cartesian product
v  # For each inner list:
x #  Do a recursive call


05AB1E, 19 11 bytes

"â®δ.V"©.V


Input as a pair of ragged lists.

Explanation:

"..."    # Recursive string as defined below
©   # Store this string in variable ®
.V # Execute it as 05AB1E code, using the (implicit) input as argument
# (after which the result is output implicitly)

# Push both lists in the pair separated to the stack
â       # Take the cartesian product of these two lists
δ     # Map over each inner pair of lists:
® .V   # Execute ® as 05AB1E code, doing a recursive call


If only 05AB1E had a recursive function builtin..

Charcoal, 34 bytes

⊞υＡＦυ«≔⊟ιηＦ⊟ιＦＥη⟦κλ⟧«⊞ιλ⊞υλ»»⭆¹§υ⁰


Try it online! Link is to verbose version of code. Takes input as a list of two ragged lists. Explanation:

⊞υＡ


Push the list of two ragged lists to the predefined empty list.

Ｆυ«


Loop over all the lists of ragged lists.

≔⊟ιη


Remove the second ragged list from the list.

Ｆ⊟ιＦＥη⟦κλ⟧«


Remove the first ragged list from the list and loop over the Cartesian product of the lists.

⊞ιλ⊞υλ


Push each new list of two ragged lists to the ragged list being processed and also to the predefined empty list so that it will be "recursively" processed.

»»⭆¹§υ⁰


Pretty-print the resulting ragged list. (The default output for a ragged list is blank, so I don't have much choice here.)

Thunno, $$\ 15 \log_{256}(96) \approx \$$ 12.35 bytes

Y"yzSeYxAv"AxAv


Attempt This Online!

Port of Kevin Cruijssen's 05AB1E answer.

Explanation

Y"yzSeYxAv"AxAv  # Implicit input
Y                # Store it in y for later
"yzSeYxAv"Ax    # Store the recursive string in x:
yzS            #  Get the cartesian product of the elements of y
e           #  Map:
Y          #   Store the list in y
xAv       #   And execute x as Thunno code
Av  # Execute x as Thunno code
# Implicit output


Ruby, 28 bytes

f=->a,b{a.product(b).map &f}


Try it online!

Recursive by definition.

JavaScript, 33 bytes

f=A=>B=>A.flatMap(a=>B.map(f(a)))


Try it online!

Use as f(A)(B), as permitted here.