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
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.
zip 3 4
?(3,4)
or[(3, 4)]
or both of them? \$\endgroup\$zip 3 4
since3
and4
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. \$\endgroup\$zip
. I will modify these to make them more test-case like. \$\endgroup\$[1]
and[2, 3]
? \$\endgroup\$[(1,2)]
\$\endgroup\$