4

标准库包含一个函数

unzip :: [(a, b)] -> ([a], [b])

定义这一点的明显方法是

unzip xs = (map fst xs, map snd xs)

然而，这意味着遍历列表两次来构造结果。我想知道的是，有没有办法只用一次遍历来做到这一点？

附加到列表是昂贵的 - 实际上是 O(n)。但是，正如任何新手都知道的那样，我们可以巧妙地利用惰性和递归通过递归调用“附加”到列表中。因此，zip可以很容易地实现为

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

但是，此技巧似乎仅在您返回一个列表时才有效。我看不出如何扩展它以允许同时构造多个列表的尾部，而不会最终重复源遍历。

我一直认为来自标准库的 设法在一次遍历中做到这一点（这就是unzip在库中实现这个原本微不足道的函数的全部意义），但我实际上并不知道它是如何工作的。

4

2 回答 2

16

是的，有可能：

unzip    =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])

使用显式递归，这看起来是这样的：

unzip [] = ([], [])
unzip ((a,b):xs) = (a:as, b:bs)
             where (  as,   bs) = unzip xs

标准库具有无可辩驳的模式匹配的原因~(as, bs)是允许它实际上懒惰地工作：

前奏> 让解压' = foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
前奏> 让解压'' = foldr (\( a,b) (as,bs) -> (a:as,b:bs)) ([],[])
前奏> 头。fst $ 解压缩' [(n,n) | n<-[1..]]
1
前奏> 头。fst $ unzip'' [(n,n) | n<-[1..]]
*** 例外：堆栈溢出

于 2013-08-17T10:44:18.310 回答
7

以下想法源于美丽的折叠。

当你对一个列表有两个折叠操作时，你总是可以通过折叠同时保持它们的状态来一次执行它们。让我们用 Haskell 来表达这一点。首先我们需要了解什么是折叠操作：

{-# LANGUAGE ExistentialQuantification #-}
import Control.Applicative

data Foldr a b = forall r . Foldr (a -> r -> r) r (r -> b)

折叠操作具有折叠函数、起始值和从最终状态产生结果的函数。通过使用存在量化，我们可以隐藏状态的类型，这是将折叠与不同状态结合起来所必需的。

将 aFoldr应用于列表只需foldr使用适当的参数进行调用：

fold :: Foldr a b -> [a] -> b
fold (Foldr f s g) = g . foldr f s

自然地，Foldr是一个函子，我们总是可以将一个函数附加到终结函数：

instance Functor (Foldr a) where
    fmap f (Foldr k s r) = Foldr k s (f . r)

更有趣的是，它也是一个Applicative函子。实现pure很容易，我们只返回一个给定的值而不折叠任何东西。最有趣的部分是<*>。它创建了一个新的折叠，保留了给折叠的状态，最后结合了结果。

instance Applicative (Foldr a) where
    pure x  = Foldr (\_ _ -> ()) () (\_ -> x)
    (Foldr f1 s1 r1) <*> (Foldr f2 s2 r2)
            = Foldr foldPair (s1, s2) finishPair
      where
        foldPair a ~(x1, x2) = (f1 a x1, f2 a x2)
        finishPair ~(x1, x2) = r1 x1 (r2 x2)
    f *> g  = g
    f <* g  = f

请注意（如 leftaroundabout 的回答），我们~在元组上有惰性模式匹配。这确保了<*>足够懒惰。

现在我们可以表示map为Foldr：

fromMap :: (a -> b) -> Foldr a [b]
fromMap f = Foldr (\x xs -> f x : xs) [] id

这样，定义unzip就变得容易了。我们只是结合了两张地图，一张使用fst，另一张使用snd：

unzip' :: Foldr (a, b) ([a], [b])
unzip' = (,) <$> fromMap fst <*> fromMap snd

unzip :: [(a, b)] -> ([a], [b])
unzip = fold unzip'

我们可以验证它是否只处理一次输入（并且是懒惰的）：两者

head . snd $ unzip (repeat (3,'a'))
head . fst $ unzip (repeat (3,'a'))

产生正确的结果。

于 2013-08-17T12:54:49.533 回答