Geek Answers Handbook

What is a unzip generalization?

Most of the methods that I know from lists are actually special cases of some well-known class types. Some example methods and an associated type class:

  • map :: (a -> b) -> [a] -> [b] and Functor
  • foldr :: (a -> b -> b) -> b -> [a] -> b and Foldable
  • forM :: Monad m => [a] -> (a -> mb) -> m [b] and Traversable
  • concat :: [[a]] -> [a] and Monad

Perhaps the list will be continued (pardon pun).

I'm curious about the “deeper meaning” for unzip :: [(a, b)] -> ([a], [b]) . Can it be implemented using some well-known instances [] and, for example, an instance functor (,a) ? Or some other cases? Ideally, I would like to have a more abstract function with this type: SomeClass m => unzip :: m (a, b) -> (ma, mb) . Is there a class that will do the job?

+7
list haskell typeclass
source share
2 answers

You can just take the first and second projections:

 gunzip :: Functor f => f (a, b) -> (fa, fb) gunzip ps = (fmap fst ps, fmap snd ps)

But note that gunzip crosses ps twice as much as regular zip for lists, so this is unpleasant because ps not garbage collected after the first pass and remains in memory, which causes a memory leak on large lists.

+7
source share

Intuitively, the unzip' function must tear down the structure holding (a,b) and then create it in two copies of the structure, the first of which contains a , and the second of them contains b .

One possible generalization already mentioned in another answer,

 unzip' :: (Functor t) => t (a, b) -> (ta, tb) unzip' xs = (fmap fst xs, fmap snd xs)

This is consistent with the count, but one of the drawbacks is that it must go over the original structure twice - once for each fmap call.

The Foldable class describes structures that can be repeated, building the result as you move. We can use this property to ensure that we only go through the initial structure once (one call to foldr ), but we still need to know how to create copies of the structures again.

A class like MonadPlus provides ways to get an empty structure and merge two structures (a bit more Monoid ) -

 class Monad m => MonadPlus m where mzero :: ma mplus :: ma -> ma -> ma

With this we can write

 import Control.Monad import Data.Foldable (foldr) unzip' :: (Foldable t, MonadPlus m) => t (a, b) -> (ma, mb) unzip' = foldr f (mzero, mzero) where f (a,b) (as, bs) = (mplus (return a) as, mplus (return b) bs)

Then we can do things like

 >> unzip' [(1,2), (3,4)] :: ([Int], [Int]) ([1,3],[2,4])

but also

 >> unzip' (Right (1,2)) :: ([Int], Maybe Int) ([1],Just 2)

The last thought is a bit ugly that we need to call mplus (return a) as . It might be better to have a class like

 class Listish m where null :: ma cons :: a -> ma -> ma

but I have not studied this bit of design space.

+6
source share

More articles:


All Articles