Unzip in one pass?
haskell, list
Solution
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
Problem
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.