Metacognitive processes involved in deriving a solution to unzip

Submitted by metaperl on Wed, 11/29/2006 - 1:10pm.
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