一次解压缩？ [英] Unzip in one pass?

问题描述

标准库包含一个函数

  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 能够在一次遍历中做到这一点（这是实现这个不重要的功能的完整点）一个库），但我实际上并不知道它是如何工作的。 /hackage.haskell.org/packages/archive/base/latest/doc/html/src/GHC-List.html#unziprel =nofollow noreferrer>有可能：

$ p $ unzip = foldr（\（a，b）〜（as，bs） - >（a：as，b：bs））（[


$ b

使用显式递归，这看起来如此：

  unzip [] =（[]，[]）
 unzip（（a，b）：xs）=（a：as，b： bs）
其中（as，bs）= unzip xs 
  

标准库具有无可辩驳的模式匹配〜（as，bs）可以让它实际上延迟工作：

> let unzip'= foldr（\（a，b）〜（as，bs） - >（a：as，b：bs））（[]，[]）
 
 Prelude> let unzip''= foldr（\（a，b）（as，bs） - >（a：as，b：bs））（[]，[]）
 
前奏>头部。 fst $ unzip'[（n，n）| n<  -  [1 ..]] 
 
 1 
 
前奏>头。 fst $ unzip''[（n，n）| n < -  [1 ..]] 
 
 ***例外：堆栈溢出
 
 

The standard libraries include a function

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

The obvious way to define this is

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

However, this means traversing the list twice to construct the result. What I'm wondering is, is there some way to do this with only one traversal?

Appending to a list is expensive - O(n) in fact. But, as any newbie knows, we can make clever use of laziness and recursion to "append" to a list with a recursive call. Thus, zip may easily be implemented as

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

This trick appear to only work if you're returning one list, however. I can't see how to extend this to allow constructing the tails of multiple lists simultaneously without ending up duplicating the source traversal.

I always presumed that the unzip from the standard library manages to do this in a single traversal (that's kind of the whole point of implementing this otherwise trivial function in a library), but I don't actually know how it works.

解决方案

Yes, it is possible:

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

With explicit recursion, this would look thus:

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

The reason that the standard library has the irrefutable pattern match ~(as, bs) is to allow it to work actually lazily:

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

这篇关于一次解压缩？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！