Zip ragged lists

Question

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!

Task

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 code-golf so the goal is to minimize the size of your source code as measured in bytes.

Answer 1

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.

Answer 2

Haskell, 100 92 bytes

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!

Answer 3

K (ngn/k), 58 bytes

{$[&/i:`i=@:'(x;y);x,'y;|/i;x o'y;o'/#/:/|1(&/#:')\(x;y)]}

Try it online!

Answer 4

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;

Answer 5

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.

Answer 6

Rust, 294 284 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]})}

Playground Link

Answer 7

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.

Answer 8

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

Answer 9

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
            head :: rest ->
              { 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 []