一次解压缩？

Question

标准库包括一个函数

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标准库的管理要做到这一点在一个遍历(这是一种实现在图书馆这个本来平凡函数的整点),但我真的不知道它是如何工作.

Answer 1

是的,有可能:

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)是允许它实际上懒惰地工作:

Prelude> let unzip'= foldr(\(a,b)〜(as,bs) - >(a:as,b:bs))([],[])
Prelude> let unzip''= foldr(\( a,b)(as,bs) - >(a:as,b:bs))([],[])
Prelude> head.fst $ unzip'[(n,n)| n < - [1 ..]]
1
Prelude> head.fst $ unzip''[(n,n)| n < - [1 ..]]
***例外:堆栈溢出

Answer 2

以下想法源于The Beautiful Folding.

当您在列表上进行两次折叠操作时,您始终可以通过折叠并同时保持其状态来一次执行它们.让我们在Haskell中表达这一点.首先,我们需要捕获什么是折叠操作:

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

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

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

将a Foldr应用于列表只需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

请注意(在左侧的答案中)我们~在元组上有惰性模式匹配.这确保了<*>足够的懒惰.

现在我们可以表达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'))

产生正确的结果.