CODEWITHSUNDEEP
haskell
Zindzi
Zindzi

Reputation: 41

Zip list of different lengths

I'm just starting with Haskell and I'm not sure how to do this but when I have an input like [1,2,3,4] [5,6,7,8,9,10,11,12] the output should be [[(1,5),(2,6),(3,7),(4,8)][(1,9),(2,10),(3,11),(4,12)]]. I tried to do something, see my code below. But this only works for a list of a specific size. I'm sure there must be a way to do this more efficiently and for a list of any size recursively, can someone help me with this? 

splitlist :: [a] -> [b] -> [[(a,b)]] 
    splitlist list1 list2 = [a,b,c] where
        n = length list1
        a = zip list1 list2
        nlist = drop n list2
        b = zip list1 nlist 
        nnlist = drop n nlist 
        c = zip list1 nnlist

Upvotes: 2

Views: 964

Answers (4)

Will Ness
Will Ness

Reputation: 71065

The first answer isn't working when first list is the longest of the two; the second answer seems excessively long for such a simple task.

It is easy to amend the first answer's code,

import Data.List.Split (chunksOf)

splitList as bs = zs : if null xs then map ( zip  as) (chunksOf n ys)
                                  else map (`zip` bs) (chunksOf n xs)
   where
   (zs, n, xs, ys) = (zip as bs, length zs, drop n as, drop n bs)

Works in both cases, also with infinite lists.

Upvotes: 2

chepner
chepner

Reputation: 531165

You have the right approach, but you just need to make it recursive rather than enumerating the number of cycles you go through: 

splitList :: [a] -> [b] -> [[(a,b)]]
splitList as [] = []
splitList as bs = zip as bs : splitList as (drop (length as) bs)

So, for example,

splitList [1,2] [1..10]
  == zip [1,2] [1..10] : splitList [1,2] [3..10]
  == zip [1,2] [1..10] : zip [1,2] [3..10] : splitList [1,2] [5..10]
  == ...
  == zip [1,2] [1..10] : zip [1,2] [3..10] : ... : zip [1,2] [9,10] : splitList [1,2] []
  == zip [1,2] [1..10] : zip [1,2] [3..10] : ... : zip [1,2] [9,10] : []
  ...
  == [[(1,1),(2,2)],[(1,3),(2,4)],...,[(1,9),(2,10)]]

Upvotes: 0

Daniel Wagner
Daniel Wagner

Reputation: 152837

The other answer shows how to reuse library functions. However, it has a small flaw: it forces its arguments into memory before beginning to return results, so it doesn't play cleanly with the rest of Haskell's lazy infrastructure. In this answer, I will show how to write a version which:

  1. Begins producing output immediately (as soon as it is clear that both lists are nonempty)
  2. Works with infinite inputs
  3. Forces at most twice the length of the shorter list worth of elements into memory at any given time

We will build up all the pieces used in the other answer, but lazified versions of them: rather than using Int for lengths, we'll implicitly use a list of type [a] as a lazy representation of its own length. The first thing we need is comparisons of two lazy numbers. It will turn out later to be convenient to have our comparison return not just which number is bigger, but the difference of the two numbers, as well.

data LazyOrdering a b
    = LazyLT [b]
    | LazyEQ
    | LazyGT [a]
    deriving (Eq, Ord, Read, Show)

lazyCompare :: [a] -> [b] -> LazyOrdering a b
lazyCompare [] [] = LazyEQ
lazyCompare [] bs = LazyLT bs
lazyCompare as [] = LazyGT as
lazyCompare (ah:at) (bh:bt) = lazyCompare at bt

Next we need chunksOf; we will implement it in terms of a lazified version of splitAt. The latter should take a "lazy" length to split its list argument at. We are careful to start producing elements as quickly as we can -- that is, as soon as we know that the index to split at is greater than 0 and the list we're splitting is nonempty.

lazySplitAt :: [a] -> [b] -> ([b], [b])
lazySplitAt [] bs = ([], bs)
lazySplitAt _ [] = ([], [])
lazySplitAt (_:as) (b:bs) = (b:bb, be) where ~(bb, be) = lazySplitAt as bs

Our lazy chunksOf variant can now use lazySplitAt as a subroutine. Again, we take a "lazy" number as our first argument; and we are careful to produce the structure of the output list as early as possible, calling (:) as the outermost function call.

lazyChunksOf :: [a] -> [b] -> [[b]]
lazyChunksOf as bs = bb : case be of
    [] -> []
    _  -> lazyChunksOf as be
    where ~(bb, be) = lazySplitAt as bs

With these pieces in place, we can use essentially the same implementation, swapping in our lazy variants for length/(<=)/chunksOf.

zipCycle :: [a] -> [b] -> [[(a,b)]]
zipCycle [] _ = []
zipCycle _ [] = []
zipCycle as bs = zip as bs : case lazyCompare as bs of
    LazyLT bt -> lazyChunksOf as (zip (cycle as) bt)
    LazyEQ    -> []
    LazyGT at -> lazyChunksOf bs (zip at (cycle bs))

We can try it out in ghci:

> zipCycle "hi" "hello"
[[('h','h'),('i','e')],[('h','l'),('i','l')],[('h','o')]]

Infinite lists work well as either argument:

> take 3 $ zipCycle "hi" [1..]
[[('h',1),('i',2)],[('h',3),('i',4)],[('h',5),('i',6)]]
> take 3 $ zipCycle [1..] "hi"
[[(1,'h'),(2,'i')],[(3,'h'),(4,'i')],[(5,'h'),(6,'i')]]

...or as both arguments:

> take 1 . map (take 3) $ zipCycle [1..] [1..]
[[(1,1),(2,2),(3,3)]]

Upvotes: 1

assembly.jc
assembly.jc

Reputation: 2066

An interesting question! cycle may help in this situation, it repeat the elements of list infinite time, such as

cycle [1,2,3,4] = [1,2,3,4,1,2,3,4,1,....]

so, when to zip with [5,6,7,8,9,10,11,12] will be the desired result [(1,5),(2,6),(3,7),(4,8),(1,9),(2,10),(3,11),(4,12)] and then use chunksOf (defined in Data.List.Split) group it into [[(a, b)]] type as:

splitList::[a]->[b]->[[(a,b)]]
splitList [] _ = []
splitList _ [] = []    
splitList list1 list2 
    | length list1 <= length list2 = doSplit (length list1) (cycle list1) list2
    | otherwise                    = doSplit (length list2) list1 (cycle list2)
    where doSplit len xs ys        = chunksOf len $ zip xs ys

P.S this solution only work for finite lists

Upvotes: 2

Related Questions