Zip with default value instead of dropping values?

Question 1

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'

Question 2

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  "]

Question 3

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.}

Question 4

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.

Question 5

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!

Question 6

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

zipLongest :: a -> b -> [a] -> [b] -> [(a,b)]
zipLongest x y xs ys = map head . transpose $   -- longest length;
                [                                 --   view from above:
                  zip  xs 
                      (ys ++ repeat y)            -- with length of xs
                , zip (xs ++ repeat x) 
                       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 an arbitrary number of 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 x xss = transpose $ 
   zipWith const
      (transpose [xs ++ repeat x | xs <- xss])         -- pad all, and cut
      (takeWhile id . map or . transpose $             --   to the longest list
         [ (True <$ xs) ++ repeat False | xs <- xss])

> mapM_ print $ padAll '-' ["ommmmmmm", "ommmmmm", "ommmmm", "ommmm", "ommm",
   "omm", "om", "o"]
"ommmmmmm"
"ommmmmm-"
"ommmmm--"
"ommmm---"
"ommm----"
"omm-----"
"om------"
"o-------"

Question 7

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-}

Question 8

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!

Question 9

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 (,)