# 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.

```      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
```