Unzip in one go?

Question

Standard libraries include a feature

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

The obvious way to determine this is

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

However, this means that we iterate over the list twice to build the result. I am wondering if there is a way to do this with just one workaround?

Adding to the list is expensive - O (n). But, as any newbie knows, we can skillfully use laziness and recursion to “add” to the list using a recursive call. Thus, zip can be easily implemented as

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

This trick seems to work only if you return a single list. I cannot figure out how to extend this to allow the construction of the tails of several lists at the same time, without ending up duplicating the source traversal.

I always assumed that unzip from the standard library handles this in one round (this is the type of the whole implementation of this trivial function in the library), but I really don't know how to do this.

Answer 1

Yes, it is possible :

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

With explicit recursion, it would look like this:

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

The reason the standard library has an irrefutable match with the ~(as, bs) pattern is to let it actually work 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 ..]]
one
Prelude> head. fst $ unzip '' [(n, n) | n <- [1 ..]]
*** Exception: stack overflow

Answer 2

The following ideas come from The Beautiful Folding .

When you have two folding operations on a list, you can always perform them right away, folding, saving both states. Let me put it in Haskell. First we need to fix what a bending operation is:

 {-# LANGUAGE ExistentialQuantification #-} import Control.Applicative data Foldr ab = forall r . Foldr (a -> r -> r) r (r -> b) 

The folding operation has a folding function, an initial value and a function that gives a result from the final state. Using existential quantification, we can hide the type of state that is needed to combine folds with different states.

Applying Foldr to a list is just calling Foldr with the appropriate arguments:

 fold :: Foldr ab -> [a] -> b fold (Foldr fsg) = g . foldr fs 

Naturally, Foldr is a functor, we can always add a function to the final one:

 instance Functor (Foldr a) where fmap f (Foldr ksr) = Foldr ks (f . r) 

More interestingly, it is also Applicative functor. The implementation of pure is simple, we just return the given value and do not reset anything. The most interesting part is <*> . He creates a new fold that holds the states as giving folds, and at the end, combines the results.

 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 

Note (as to the left) that we have a lazy pattern matching ~ with tuples. This ensures that <*> is lazy enough.

Now we can express map as Foldr :

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

This makes unzip easy. We just combine the two cards using fst and the other snd :

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

We can verify that it processes the input only once (and lazily): Both

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

enter the correct result.