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

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_fstand

xs_sndlook 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

- metaperl's blog
- Login to post comments