haskell - 如何在 Haskell 中实现通用的 "zipn"和 "unzipn"？

Question

我在基本的 Haskell 库中找到了这个文档:

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.

...等等，直到zip7和unzip7。

这是 Haskell 类型系统的基本限制吗？或者有没有办法实现一次压缩和解压缩，以处理不同的输入配置？

Answer 1

这是应用程序的一个非常有用的方面。退房 ZipList 这只是一个 newtype包装一个简单的列表。包装器的原因是ZipList有一个应用实例，你猜对了，将列表压缩在一起。那么，如果你想要 zip7 as bs cs ds es fs gs hs ，你可以做类似的事情

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

如您所知，此机制也用于扩展 zipWith ，这是 zip 的一般情况.老实说，我认为我们应该撕掉所有 zipN功能并教人们上述内容。 zip本身很好，但除此之外......

模板 Haskell 解决方案

正如评论和其他答案所表明的那样，这不是一个特别令人满意的答案。我期待其他人实现的一件事是 TemplateHaskell zip 的版本和 unzip .由于还没有人这样做，所以就在这里。

它所做的只是机械地为 zip 生成 AST或 unzip职能。背后的理念 zip是使用 ZipList和后面 unzip是使用 foldr :

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

实现看起来像这样。

{-# 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 [| [] |])) |]

你可以在 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])