# Zip with default value instead of dropping values?

I'm looking for a function in haskell to zip two lists that may vary in length. All zip functions I could find just drop all values of a lists that is longer than the other.

For example: In my exercise I have two example lists. If the first one is shorter than the second one I have to fill up using 0's. Otherwise I have to use 1's. I'm not allowed to use any recursion. I just have to use higher order functions.

Is there any function I can use? I really could not find any solution so far.

## Answers

You can append an inifinte list of 0 or 1 to each list and then take the number you need from the result zipped list:

zipWithDefault :: a -> b -> [a] -> [b] -> [(a,b)] zipWithDefault da db la lb = let len = max (length la) (length lb) la' = la ++ (repeat da) lb' = lb ++ (repeat db) in take len $ zip la' lb'

There is some structure to this problem, and here it comes. I'll be using this stuff:

import Control.Applicative import Data.Traversable import Data.List

First up, lists-with-padding are a useful concept, so let's have a type for them.

data Padme m = (:-) {padded :: [m], padder :: m} deriving (Show, Eq)

Next, I remember that the truncating-zip operation gives rise to an Applicative instance, in the library as newtype ZipList (a popular example of a non-Monad). The Applicative ZipList amounts to a decoration of the monoid given by infinity and minimum. Padme has a similar structure, except that its underlying monoid is positive numbers (with infinity), using one and maximum.

instance Applicative Padme where pure = ([] :-) (fs :- f) <*> (ss :- s) = zapp fs ss :- f s where zapp [] ss = map f ss zapp fs [] = map ($ s) fs zapp (f : fs) (s : ss) = f s : zapp fs ss

I am obliged to utter the usual incantation to generate a default Functor instance.

instance Functor Padme where fmap = (<*>) . pure

Thus equipped, we can pad away! For example, the function which takes a ragged list of strings and pads them with spaces becomes a one liner.

deggar :: [String] -> [String] deggar = transpose . padded . traverse (:- ' ')

See?

*Padme> deggar ["om", "mane", "padme", "hum"] ["om ","mane ","padme","hum "]

This can be expressed using These ("represents values with two non-exclusive possibilities") and Align ("functors supporting a zip operation that takes the union of non-uniform shapes") from the *these* library:

import Data.Align import Data.These zipWithDefault :: Align f => a -> b -> f a -> f b -> f (a, b) zipWithDefault da db = alignWith (fromThese da db)

salign and the other specialised aligns in Data.Align are also worth having a look at.

Thanks to u/WarDaft, u/gallais and u/sjakobi over at r/haskell for pointing out this answer should exist here.

This should do the trick:

import Data.Maybe (fromMaybe) myZip dx dy xl yl = map (\(x,y) -> (fromMaybe dx x, fromMaybe dy y)) $ takeWhile (/= (Nothing, Nothing)) $ zip ((map Just xl) ++ (repeat Nothing)) ((map Just yl) ++ (repeat Nothing)) main = print $ myZip 0 1 [1..10] [42,43,44]

Basically, append an infinite list of Nothing to the end of both lists, then zip them, and drop the results when both are Nothing. Then replace the Nothings with the appropriate default value, dropping the no longer needed Justs while you're at it.

You don't have to compare list lengths. Try to think about your zip function as a function taking only one argument xs and returning a *function* which will take ys and perform the required zip. Then, try to write a *recursive* function which recurses on xs only, as follows.

type Result = [Int] -> [(Int,Int)] myZip :: [Int] -> Result myZip [] = map (\y -> (0,y)) -- :: Result myZip (x:xs) = f x (myZip xs) -- :: Result where f x k = ??? -- :: Result

Once you have found f, notice that you can turn the recursion above into a fold!

As you said yourself, the standard zip :: [a] -> [b] -> [(a, b)] drops elements from the longer list. To amend for this fact you can modify your input *before* giving it to zip. First you will have to find out which list is the shorter one (most likely, using length). E.g.,

zip' x xs y ys | length xs <= length ys = ... | otherwise = ...

where x is the default value for shorter xs and y the default value for shorter ys.

Then you extend the shorter list with the desired default elements (enough to account for the additional elements of the other list). A neat trick for doing so without having to know the length of the longer list is to use the function repeat :: a -> [a] that repeats its argument infinitely often.

zip' x xs y ys | length xs <= length ys = zip {-do something with xs-} ys | otherwise = zip xs {-do something with ys-}

Here is another solution, that does work on infinite lists and is a straightforward upgrade of Prelude's zip functions:

zipDefault :: a -> b -> [a] -> [b] -> [(a,b)] zipDefault _da _db [] [] = [] zipDefault da db (a:as) [] = (a,db) : zipDefault da db as [] zipDefault da db [] (b:bs) = (da,b) : zipDefault da db [] bs zipDefault da db (a:as) (b:bs) = (a,b) : zipDefault da db as bs

and

zipDefaultWith :: a -> b -> (a->b->c) -> [a] -> [b] -> [c] zipDefaultWith _da _db _f [] [] = [] zipDefaultWith da db f (a:as) [] = f a db : zipDefaultWith da db f as [] zipDefaultWith da db f [] (b:bs) = f da b : zipDefaultWith da db f [] bs zipDefaultWith da db f (a:as) (b:bs) = f a b : zipDefaultWith da db f as bs

@pigworker, thank you for your enlightening solution!

Yet another implementation:

zipWithDefault :: a -> b -> (a -> b -> c) -> [a] -> [b] -> [c] zipWithDefault dx _ f [] ys = zipWith f (repeat dx) ys zipWithDefault _ dy f xs [] = zipWith f xs (repeat dy) zipWithDefault dx dy f (x:xs) (y:ys) = f x y : zipWithDefault dx dy f xs ys

And also:

zipDefault :: a -> b -> [a] -> [b] -> [c] zipDefault dx dy = zipWithDefault dx dy (,)

No length, no counting, no hand-crafted recursions, no cooperating folds. transpose does the trick:

zipLongest :: a -> b -> [a] -> [b] -> [(a,b)] zipLongest dx dy xs ys = map head . transpose $ -- longest length; [ -- view from above zip xs (ys ++ repeat dy) -- with length of xs , zip (xs ++ repeat dx) ys -- with length of ys ]

The result of transpose is as long a list as the longest one in its input list of lists. map head takes the first element in each "column", which is the pair we need, whichever the longest list was.

*(update:)* For lists, efficient padding to the maximal length -- aiming to avoid the potentially quadratic behaviour of other *sequentially*-combining approaches -- can follow the same idea:

padAll :: [[a]] -> a -> [[a]] padAll xs c = transpose $ zipWith const (transpose [x ++ repeat c | x <- xs]) -- pad all, and cut (takeWhile id . map or . transpose $ -- to the longest list [ (True <$ x) ++ repeat False | x <- xs]) > mapM_ print $ padAll ["ommmmmmm", "ommmmmm", "ommmmm", "ommmm", "ommm", "omm", "om", "o"] '-' "ommmmmmm" "ommmmmm-" "ommmmm--" "ommmm---" "ommm----" "omm-----" "om------" "o-------"