# Zip ragged lists

In Haskell (and probably some other languages or something) zip is a function which takes two lists, and produces a list of tuples by pairing elements at the same index:

zip [1,2,3] [6,5,4] = [(1,6),(2,5),(3,4)]


If there are extra elements on one of the input lists those are trimmed off and don't appear in the result:

zip [1,2,3] [6,5,4,3,2,1] = [(1,6),(2,5),(3,4)]


A ragged list is like a list, but instead of just containing one type of thing it can contain two types of things, one being itself. For example:

[1,[2,3,[2]]]


This is a ragged list of integers. It contains integers and ragged lists of integers.

You can easily imagine zipping ragged lists which have a similar enough structure. For example:

zip [1,[2,3,9],3] [2,[3,4,5,6]] = [(1,2),[(2,3),(3,4),(9,5)]]


But things get a little tricky when you have to combine an element (e.g. an integer) with a structure (e.g. a ragged list of integers). To do this we are going to distribute the element across the structure. Some examples:

zip [1] [[2,3,[5,4]]] = [[(1,2),(1,3),[(1,5),(1,4)]]]
zip [1,2] [3,[4,5]] = [(1,3),[(2,4),(2,5)]]
zip [[2,3],4] [1,[6,7]] = [[(2,1),(3,1)],[(4,6),(4,7)]]


This whole behavior can be captured by this Haskell program:

data Ragged a
= Ragged (Either a [Ragged a])

zip' :: Ragged a -> Ragged b -> Ragged (a, b)
zip' (Ragged x) (Ragged y) = Ragged $go x y where go :: Either a [Ragged a] -> Either b [Ragged b] -> Either (a,b) [Ragged (a,b)] go (Left x) (Left y) = Left (x, y) go (Left x) (Right ys) = Right$ (zip' $Ragged$ Left x) <$> ys go (Right xs) (Left y) = Right$ (flip zip' $Ragged$ Left y) <$> xs go (Right xs) (Right ys) = Right$ zipWith zip' xs ys


Attempt This Online!

Take as input two ragged lists of positive integers and output their zip as defined above. The output should be a ragged list of integer tuples. You may represent ragged lists and tuples in any reasonable way. The definition of ragged lists given here implies there is always a list at the top level, (e.g. 1 is not a ragged list of integers) so you may assume that this is the case for your inputs, but you may also support integers at the top level if its more convenient.

This is so the goal is to minimize the size of your source code as measured in bytes.

• What is the correct output for zip 3 4? (3,4) or [(3, 4)] or both of them? Feb 22 at 15:31
• @EzioMercer There's no requirement to support zip 3 4 since 3 and 4 aren't considered ragged lists by the challenge. But the most sensible answer is (3,4) IMO, and that's the one given by the Haskell sample implementation. Feb 22 at 15:39
• @EzioMercer That's not really a test case it's part of the explanation of zip. I will modify these to make them more test-case like. Feb 22 at 15:43
• What's the result of inputs [1] and [2, 3]?
– Neil
Feb 23 at 1:02
• @Neil That's just a regular zip. [(1,2)] Feb 23 at 3:50

# Whython, 53 bytes

z=lambda a,b:map(z,[+a]*len(b)?a,[+b]*len(a)?b)?(a,b)


Takes two lists; returns map iterators instead of lists. Attempt This Online!

### Explanation

Partly inspired by 97.100.97.109's Python answer.

z=lambda a,b:


Define z as a function of two arguments a and b.

map(z,...,...)


Map z over corresponding items from the following two iterables:

[+a]*len(b)?a


If a is an integer and b is a list, convert a to a list by putting it into a single-element list and then repeating it a number of times equal to the length of b. Otherwise, the first expression errors, either because +a is an error when a is a list, or because len(b) is an error when b is an int. In this case, catch the error with ? and use just a instead.

[+b]*len(a)?b


The second iterable is the same thing but for b instead of a.

If either or both of a and b are lists, the map will get two lists as arguments and will succeed. However, if they are both ints, the map will get two ints as arguments and will error. Thus:

?(a,b)


If the map errors, return a tuple containing a and b instead.

• The ? operator is the only feature of Whython used here? Feb 23 at 3:57
• @innisfree - Could it be that the ? operator is the only feature of Whython... Feb 23 at 11:22
• @innisfree Dominic van Essen is basically right. Whython does also have function composition via a[b] syntax, but that wasn't useful for this challenge (and, in fact, is rarely useful in golf). Feb 23 at 16:58

data R a=I a|L[R a]
I a%I b=I(a,b)
L x%L y=L$zipWith(%)x y a%L y=L$map(a%)y
L x%b=L$map(%b)x  Try it online! # K (ngn/k), 58 bytes {$[&/i:i=@:'(x;y);x,'y;|/i;x o'y;o'/#/:/|1(&/#:')\(x;y)]}


Try it online!

# JavaScript, 76 bytes

z=(a,b,f=c=>c.shift?.()??c)=>a<z|b<z?[]:a+b>z?[z(f(a),f(b)),...z(a,b)]:[a,b]


z=(a,b,f=c=>c.shift?.()??c)=>a<z|b<z?[]:a+b>z?[z(f(a),f(b)),...z(a,b)]:[a,b]

console.log(JSON.stringify(z([1,2,3], [6,5,4]))); // [(1,6),(2,5),(3,4)]
console.log(JSON.stringify(z([1,2,3], [6,5,4,3,2,1]))); // [(1,6),(2,5),(3,4)]
console.log(JSON.stringify(z([1,[2,3,9],3], [2,[3,4,5,6]]))); // [(1,2),[(2,3),(3,4),(9,5)]]
console.log(JSON.stringify(z([1], [[2,3,[5,4]]]))); // [[(1,2),(1,3),[(1,5),(1,4)]]]
console.log(JSON.stringify(z([1,2], [3,[4,5]]))); // [(1,3),[(2,4),(2,5)]]
console.log(JSON.stringify(z([[2,3],4], [1,[6,7]]))); // [[(2,1),(3,1)],[(4,6),(4,7)]]

Code with comment:

zip = (a, b) => {
if (isEmptyArray(a) || isEmptyArray(b)) return [];
if (isNonEmptyArray(a) || isNonEmptyArray(b)) {
return [zip(pop(a), pop(b)), ...zip(a, b)];
}
return [a, b];
};
isEmptyArray = a => a < zip;
isNonEmptyArray = a => a > zip;
pop = a => Array.isArray(a) ? a.shift() : a;

• can't you remove z= from the byte count? The lambda function is supposed to be enough Feb 24 at 10:02
• @Kaddath no, z is used in the function. Without z= it would be confuse what it supposed to be.
– tsh
Feb 24 at 10:48

# Python, 101 91 bytes

-10 bytes thanks to @DLosc

g=lambda a,b:(a,b)*(a*0==0==b*0)or map(g,a*0!=0and a or[a]*len(b),b*0!=0and b or[b]*len(a))


Attempt This Online!

Takes in input as a tuple.

# Python, 97 87 bytes

g=lambda a,b:(a,b)*(a*0==0==b*0)or map(g,a*(a*0!=0)or[a]*len(b),b*(b*0!=0)or[b]*len(a))


Attempt This Online!

Same as above, except it also assumes that the integers are never zero.

# Rust, 294284 271 bytes

#[derive(Clone)]
enum A{b(i32),c(Vec<A>)}fn f(x:(A,A))->A{A::c(match x{(A::c(i),A::c(j))=>i.into_iter().zip(j).map(f).collect(),(y,A::c(j))=>j.into_iter().map(|k|f((y.clone(),k))).collect(),(A::c(i),z)=>i.into_iter().map(|k|f((k,z.clone()))).collect(),w=>vec![w.0,w.1]})}


• Oops I accidentally subtracted 100 from my score Feb 23 at 7:58

# Charcoal, 63 bytes

⊞υθＦυＦ⊙ι⁼κ⁺κ⟦⟧«≔⮌Ｅ²⊟ιηＵＭη⎇⁼λ⁺λ⟦⟧λＥ§η¬μλＦＥ⌊ＥηＬλＥη§νλ«⊞ιλ⊞υλ»»⭆¹θ


Try it online! Link is to verbose version of code. Takes input as a pair list of ragged lists, and outputs using pair lists as tuples. Explanation:

⊞υθＦυ


Start a breadth-first search with the pair of input lists.

Ｆ⊙ι⁼κ⁺κ⟦⟧«


If at least one corresponding entry from the pair is a list, then:

≔⮌Ｅ²⊟ιη


Extract the pair into a new list so that they can be replaced by their zipped entries.

ＵＭη⎇⁼λ⁺λ⟦⟧λＥ§η¬μλ


If one of the entries is an integer then repeat it for the length of the other list.

ＦＥ⌊ＥηＬλＥη§νλ«


Loop over the transpose of the entries.

⊞ιλ⊞υλ


Push the new pairs back to the list that held the pair being processed but also to the list of lists to be processed so that they will themselves be zipped.

»»⭆¹θ


Pretty-print the final list because the default output format doesn't work well for ragged lists.

# JavaScript, 90 bytes

Expects input like z(list1, list2). Supports integer inputs

z=(a,b)=>a>z?a.flatMap((x,i)=>b[i]?[z(x,b[i])]:b>z?[]:[z(x,b)]):b>z?b.map(x=>z(a,x)):[a,b]


Ungolfed version:

z=(a,b)=>{
if (a>z) return a.flatMap((x,i)=>b[i]?[z(x,b[i])]:b>z?[]:[z(x,b)])
if (b>z) return b.map(x=>z(a,x))

return [a,b]
}


Try it:

z=(a,b)=>a>z?a.flatMap((x,i)=>b[i]?[z(x,b[i])]:b>z?[]:[z(x,b)]):b>z?b.map(x=>z(a,x)):[a,b]

;[
[
[1, 2], '[1,2]'
],
[
[1, [2,3]], '[[1,2],[1,3]]'
],
[
[1, [2,[3]]], '[[1,2],[[1,3]]]'
],
[
[[2,3], 1], '[[2,1],[3,1]]'
],
[
[[1,2,3], [4,5,6]], '[[1,4],[2,5],[3,6]]'
],
[
[[1,2], [4,5,6]], '[[1,4],[2,5]]'
],
[
[[1,2,3], [4,5]], '[[1,4],[2,5]]'
],
[
[[1], [[2,3,[4,5]]]], '[[[1,2],[1,3],[[1,4],[1,5]]]]'
],
[
[[1,2], [3,[4,5]]], '[[1,3],[[2,4],[2,5]]]'
],
[
[[[1,2],3], [4,[5,6]]], '[[[1,4],[2,4]],[[3,5],[3,6]]]'
],
].forEach(([[a,b],c])=>console.log(JSON.stringify(z(a,b)), JSON.stringify(z(a,b)) === c))

## UPD 126 -> 98

Thanks to tsh for the tip to reduce bytes count

• You should include z= in front of your program. And you can replace a.length? by a>z?, replace i<b[l] by b[i], use flatMap instead of map. z=(a,b)=>a>z?b>z?a.flatMap((x,i)=>b[i]?[z(x,b[i])]:[]):a.map(x=>z(x,b)):b>z?b.map(x=>z(a,x)):[a,b]
– tsh
Feb 23 at 5:29
• @tsh I finally understand everything that you advised :) Thank you very much! It was very informative Feb 23 at 14:04

# Elm, 159 155 bytes

4 bytes saved thanks to Wheat Wizard!

type R a=I a|L(List(R a))
z v u=case(v,u)of
(I x,I y)->I(x,y)
(L x,L y)->L(List.map2 z x y)
(_,L y)->L(List.map(z v)y)
(L x,_)->L(List.map(\n->z n u)x)


Elm's pattern matching is not very golfy, and given the nature of the language, it is hard to squeeze out bytes in the case branches themselves. We define a recursive type R to encapsulate the ragged structures used in the challenge, since Elm does not natively support ragged lists. The function itself z is called on two such structures (of Ints), and returns a structure (of pairs of ints (Int, Int)). We must also fully qualify such structures to pass it to the program, as is the nature of Elm:

z
(L[I 1, L[I 2, I 3, I 9], I 3])
(L[I 2, L[I 3, I 4, I 5, I 6]])


corresponds to zipRagged [1,[2,3,9],3] [2,[3,4,5,6]]. In the testing harness below, I've defined a parseCase function which allows the function to be called as z (parseCase "[1,[2,3,9],3]") (parseCase "[2,[3,4,5,6]]").

## Testing

You can try it here with the following test program:

import Html exposing (..)

-- begin code golf
type R a=I a|L(List(R a))
z v u=case(v,u)of
(I x,I y)->I(x,y)
(L x,L y)->L(List.map2 z x y)
(_,L y)->L(List.map(z v)y)
(L x,_)->L(List.map(\n->z n u)x)
-- end code golf
-- z : R Int -> R Int -> R (Int, Int)

-- display
showResult : R (Int, Int) -> String
showResult res =
case res of
I (x, y) -> "(" ++ (String.fromInt x) ++ "," ++ (String.fromInt y) ++ ")"
L list -> "[" ++ (List.map showResult list |> String.join ", ") ++ "]"

-- zip [1,[2,3,9],3] [2,[3,4,5,6]] = [(1,2),[(2,3),(3,4),(9,5)]]

parseCase : String -> R Int
parseCase str = str |> String.split "" |> parseCaseHelper

type alias ParseState =
{ depth : Int
, build : R Int
, number : String
, stack : List (R Int)
}
pushNumber : ParseState -> ParseState
pushNumber state =
if state.number == "" then state
else
let
parsedNumber = state.number
|> String.toInt
|> Maybe.withDefault -1
pushed = case state.build of
I x -> I parsedNumber
L v -> L (v ++ [I parsedNumber])
in
{ state
| number = ""
, build = pushed }

parseCaseHelper : List (String) -> R Int
parseCaseHelper =
List.foldl
(\el state ->
if el == "[" then
{ state
| stack = state.build :: state.stack
, build = L []
}
else if el == "," then
pushNumber state
else if el == "]" then
let nextState = pushNumber state
in
case nextState.stack of
{ nextState
| stack = rest
, build = case (nextState.build, head) of
(L b, L h) -> L (h ++ [nextState.build])
_ -> L [I -2] -- never occurs. "error"
}
_ -> state -- unbalanced. "error"
else if "0" <= el && el <= "9" then
{ state | number = state.number ++ el }
else state
)
{ depth = 0, build = L [], number = "", stack = [] }
>> .build
>> (\x -> case x of
L ((L inner) :: rest) -> L inner
_ -> x
)

cases =
[
( "[1,[2,3,9],3]"
, "[2,[3,4,5,6]]"
)
,
( "[1]"
, "[[2,3,[5,4]]]"
)
,
( "[1,2]"
, "[3,[4,5]]"
)
,
( "[[2,3],4]"
, "[1,[6,7]]"
)
]

overTuple : (a -> b -> c) -> (a, b) -> c
overTuple fn (left, right) = fn left right

main = cases
|> List.map
(Tuple.mapBoth parseCase parseCase >> overTuple z >> showResult)
|> List.map (\str -> Html.p [] [ text str ] )
|> Html.div []
`