list - 一口气解压？

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

是的，it is possible :

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..]]
*** Exception: stack overflow