implementation of unzip function in haskell

Question

I am trying to implement the unzip function, I did the following code but I get error.

myUnzip [] =()
myUnzip ((a,b):xs) = a:fst (myUnzip xs)  b:snd (myUnzip xs)

I know that problem is in the right side of the second line but I do know how to improve it . any hint please .

the error that I am getting is

ex1.hs:190:22:
Couldn't match expected type `()' with actual type `[a0]'
In the expression: a : fst (myUnzip xs) b : snd (myUnzip xs)
In an equation for `myUnzip':
    myUnzip ((a, b) : xs) = a : fst (myUnzip xs) b : snd (myUnzip xs)


ex1.hs:190:29:
Couldn't match expected type `(t0 -> a0, b0)' with actual type `()'
In the return type of a call of `myUnzip'
In the first argument of `fst', namely `(myUnzip xs)'
In the first argument of `(:)', namely `fst (myUnzip xs) b'

ex1.hs:190:49:
Couldn't match expected type `(a1, [a0])' with actual type `()'
In the return type of a call of `myUnzip'
In the first argument of `snd', namely `(myUnzip xs)'
In the second argument of `(:)', namely `snd (myUnzip xs)'

Answer 1

You could do it inefficiently by traversing the list twice

myUnzip [] = ([], []) -- Defaults to a pair of empty lists, not null
myUnzip xs = (map fst xs, map snd xs)

But this isn't very ideal, since it's bound to be quite slow compared to only looping once. To get around this, we have to do it recursively

myUnzip [] = ([], [])
myUnzip ((a, b):xs) = (a : ???, b : ???)
    where ??? = myUnzip xs

I'll let you fill in the blanks, but it should be straightforward from here, just look at the type signature of myUnzip and figure out what you can possible put in place of the question marks at where ??? = myUnzip xs

Answer 2

I thought it might be interesting to display two alternative solutions. In practice you wouldn't use these, but they might open your mind to some of the possibilities of Haskell.

First, there's the direct solution using a fold -

unzip' xs = foldr f x xs
  where
    f (a,b) (as,bs) = (a:as, b:bs)
    x               = ([],   [])

This uses a combinator called foldr to iterate through the list. Instead, you just define the combining function f which tells you how to combine a single pair (a,b) with a pair of lists (as, bs), and you define the initial value x.

Secondly, remember that there is the nice-looking solution

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

which looks neat, but performs two iterations of the input list. It would be nice to be able to write something as straightforward as this, but which only iterates through the input list once.

We can nearly achieve this using the Foldl library. For an explanation of why it doesn't quite work, see the note at the end - perhaps someone with more knowledge/time can explain a fix.

First, import the library and define the identity fold. You may have to run cabal install foldl first in order to install the library.

import Control.Applicative
import Control.Foldl

ident = Fold (\as a -> a:as) [] reverse

You can then define folds that extract the first and second components of a list of pairs,

fsts = map fst <$> ident
snds = map snd <$> ident

And finally you can combine these two folds into a single fold that unzips the list

unzip' = (,) <$> fsts <*> snds

The reason that this doesn't quite work is that although you only traverse the list once to extract the pairs, they will be extracted in reverse order. This is what necessitates the additional call to reverse in the definition of ident, which results in an extra traversal of the list, to put it in the right order. I'd be interested to learn of a way to fix that up (I expect it's not possible with the current Foldl library, but might be possible with an analogous Foldr library that gives up streaming in order to preserve the order of inputs).

---

Note that neither of these work with infinite lists. The solution using Foldl will never be able to handle infinite lists, because you can't observe the value of a left fold until the list has terminated.

However, the version using a right fold should work - but at the moment it isn't lazy enough. In the definition

unzip' xs = foldr f x xs
  where
    f (a,b) (as,bs) = (a:as, b:bs) -- problem is in this line!
    x               = ([],   [])

the pattern match requires that we open up the tuple in the second argument, which requires evaluating one more step of the fold, which requires opening up another tuple, which requires evaluating one more step of the fold, etc. However, if we use an irrefutable pattern match (which always succeeds, without having to examine the pattern) we get just the right amount of laziness -

unzip'' xs = foldr f x xs
  where
    f (a,b) ~(as,bs) = (a:as, b:bs)
    x                = ([],   [])

so we can now do

>> let xs = repeat (1,2)
>> take 10 . fst . unzip'  $ xs
^CInterrupted
<< take 10 . fst . unzip'' $ xs
[1,1,1,1,1,1,1,1,1,1]