Writing my own implementation of unzip was difficult.

This morning I began to think that working top-down was not the best idea. Or perhaps that working both top-down and bottom-up is best... let's see.

First, let's apply our every-useful top-down tools for problem solving - typing, cases, pictures and induction step.

Let's start with typing unzip:

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

Ok, great, so we are getting in a list of 2-tuples and want to convert that into a 2-tuple in each element tuple element is a list. Let's continue with some easy cases:

      unzip [] = ([].[])
    

Ok, how about a picture of a non-trivial case:

      unzip [(1,4),(2,5),(3,6)] = ([1,2,3], [4,5,6])
    

Hmm, the first thing that I see is the tuple

(1,4)

has been broken out into the first elements of the output list. Let's give an algebraic expression of that:

      unzip (x:xs) = ( fst x : xs_fst , snd x : xs_snd )
    

Cool, I love it! Now we only need specify how to get

xs_fst

and

xs_snd

. Hmm... well, let's take a more trivial but nonetheless non-trivial case:

      unzip [(1,4)] = ([1], [4])
    

Now in this case, what do

xs_fst

and

xs_snd

look like? That's right, they are empty lists, which means our trivial case applies. In other words, in this case:

      (xs_fst, xs_snd) = unzip([])
    

Which means:

      unzip [(1,4)]    = (1 : xs_fst, 4 : xs_snd)      
        where 
           (xs_fst, xs_snd) = unzip xs -- Since xs == []
    

an entirely different approach

Lock in the base case

      unzip [] = ([].[])
    

Rewrite your type signature using the base case whenever possible

Sounds odd, but let's do it:

      unzip :: [(a, b)] -> ([a], [b])
      unzip [(a, b)] = ([a], [b])   -- this is true for a 1-elem input list
      unzip  (a, b) : []  = (a : [], b : []) -- rewrite in cons notation
      unzip ((a, b) : xs) = (a : a', b : b') -- this generally true! done!
        where (a', b') = unzip xs