How can I implement generalized "zipn" and "unzipn" in Haskell?

Question

I find this documentation in the basic Haskell libraries:

zip :: [a] -> [b] -> [(a, b)]
    zip takes two lists and returns a list of corresponding pairs. If one input list is short, excess elements of the longer list are discarded.

zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
    zip3 takes three lists and returns a list of triples, analogous to zip.

zip4 :: [a] -> [b] -> [c] -> [d] -> [(a, b, c, d)]
    The zip4 function takes four lists and returns a list of quadruples, analogous to zip.

[...snip...]

unzip :: [(a, b)] -> ([a], [b])
    unzip transforms a list of pairs into a list of first components and a list of second components.

unzip3 :: [(a, b, c)] -> ([a], [b], [c])
    The unzip3 function takes a list of triples and returns three lists, analogous to unzip.

unzip4 :: [(a, b, c, d)] -> ([a], [b], [c], [d])
    The unzip4 function takes a list of quadruples and returns four lists, analogous to unzip.

... and so on, up to zip7 and unzip7.

Is this a fundamental limitation of Haskell's type system? Or is there a way to implement zip and unzip once, to work on different configurations of input?

Answer 1

This is one very useful aspect of applicatives. Check out ZipList which is just a newtype wrapper around a simple list. The reason for the wrapper is that ZipList has an applicative instance for, you guessed it, zipping lists together. Then, if you want zip7 as bs cs ds es fs gs hs, you can just do something like

(,,,,,,) <$> as <*> bs <*> cs <*> ds <*> es <*> fs <*> gs <*> hs

As you can tell, this mechanism is meant to be also for extending zipWith, which is a general case of zip. To be honest, I think we should rip out all of the zipN functions and teach people the above instead. zip itself is fine, but beyond that...

Template Haskell solution

As the comments and other answers indicate, this is not a particularly satisfying answer. The one thing I was expecting someone else to implement was a TemplateHaskell version of zip and unzip. As no one has done so yet, here it is.

All it does is mechanically produce AST for zip or unzip functions. The idea behind zip is to use ZipList and behind unzip is to use foldr:

zip as ... zs === \as ... zs -> getZipList $ (, ... ,) <$> ZipList as <*> ... <*> ZipList zs
unzip         === foldr (\ (a, ... ,z) ~(as, ... ,zs) -> (a:as, ... ,z:zs) ) ([], ... ,[])

The implementation looks like this.

{-# LANGUAGE TemplateHaskell #-}
module Zip (zip, unzip) where

import Prelude hiding (zip, unzip)
import Language.Haskell.TH
import Control.Monad
import Control.Applicative (ZipList(..))

-- | Given number, produces the `zip` function of corresponding arity
zip :: Int -> Q Exp
zip n = do
  lists <- replicateM n (newName "xs")

  lamE (varP <$> lists)
       [| getZipList $
            $(foldl (\a b -> [| $a <*> ZipList $(varE b) |])
                    [| pure $(conE (tupleDataName n)) |]
                    lists) |]

-- | Given number, produces the `unzip` function of corresponding arity
unzip :: Int -> Q Exp
unzip n = do
  heads <- replicateM n (newName "x")
  tails <- replicateM n (newName "xs")

  [| foldr (\ $(tupP (varP <$> heads)) ~ $(tupP (varP <$> tails)) -> 
                $(tupE (zipWith (\x xs -> [| $x : $xs |])
                                (varE <$> heads)
                                (varE <$> tails))))
           $(tupE (replicate n [| [] |])) |]

You can try this at GHCi:

ghci> :set -XTemplateHaskell
ghci> $(zip 3) [1..10] "abcd" [4,6..]
[(1,'a',4),(2,'b',6),(3,'c',8),(4,'d',10)]
ghci> $(unzip 3) [(1,'a',4),(2,'b',6),(3,'c',8),(4,'d',10)]
([1,2,3,4],"abcd",[4,6,8,10])

Answer 2

This is a zipN function that depends on the machinery of the generics-sop package:

{-# language TypeFamilies #-}
{-# language DataKinds #-}
{-# language TypeApplications #-}

import Control.Applicative
import Generics.SOP

-- "a" is some single-constructor product type, like some form of n-ary tuple
-- "xs" is a type-level list of the types of the elements of "a"
zipN :: (Generic a, Code a ~ '[ xs ]) => NP [] xs -> [a]
zipN np = to . SOP . Z <$> getZipList (hsequence (hliftA ZipList np))

main :: IO ()
main = do
   let zipped = zipN @(_,_,_) ([1,2,3,4,5,6] :* ['a','b','c'] :* [True,False] :* Nil)
   print $ zipped

The result:

[(1,'a',True),(2,'b',False)]

This solution has two disadvantages:

• You have to wrap the argument lists in the special NP type from generics-sop that is constructed with :* and Nil.
• You need to specify somehow that the result value is a list of tuples, and not a list of some other Generic-compatible type. Here, it is done with the @(_,_,_) type application.