Algebra of Programming: Chapter 1 section 5
Inverses are (horrible)-1This section gives an introduction to the extremely interesting concept of implementing a function as the inverse of another with zip and unzip as the examples. First, the goal is to build out our zip and unzip functions to satisfy the equation
zip . unzip = id
A couple of notes here. Previously everything has been defined in terms of Haskell, but this is simply an equation. Also, if you're coming from a non-functional background, id is a function that gives you back the same thing you pass to it. No matter what. In this case the equation is meant to point out that, if you give unzip a list of pairs (two element tuples) and give that result, a tuple of two lists, to zip, in the end you'll get back the original list of pairs. So zip compose unzip is equivalent to the id function. You get back just what you gave it.
zip $ unzip [(1,2), (3,4)] = [(1,2), (3,4)]
Before we get into why this is immediately useful lets define the two functions as the book does, but with Haskell.
data Listr a = Empty | Cons (a, Listr a) deriving Show foldr' c h Empty = c foldr' c h (Cons (a, x)) = h a $ foldr' c h x
Our old friends the Cons list and foldr here. If you're new to these you can check out more information on them here.
unzip' :: Listr (a, b) -> (Listr a, Listr b) unzip' = foldr' emptys conss where emptys = (Empty, Empty) conss (a, b) (x, y) = (Cons (a, x) , Cons (b, y)) unzip_' :: Listr (a, b) -> (Listr a, Listr b) unzip_' Empty = (Empty, Empty) unzip_' (Cons ((a,b), x)) = (Cons (a, left $ unzip_' x), Cons (b, right $ unzip_' x)) where left (x, y) = x right (x, y) = y
unzip' and unzip_' represent two possible ways of unzipping a list of pairs. Of interest here is the fact that my own, much less efficient, implementation involves two "folds" over the data structure, and the one implemented in the book only requires one. Apparently, any and all functions defined by a pair of folds can be defined in terms of a single fold (to be demonstrated later in the book).
zip' :: (Listr a, Listr b) -> Listr (a, b) zip' (Empty, _) = Empty zip' (_, Empty) = Empty zip' (Cons (a, x), Cons (b, y)) = Cons ( (a, b) , zip' (x, y) ) -- > let x = zip' . unzip' -- > x $ Cons ((1, 'a'), Cons ((2, 'b'), Empty)) -- Cons ((1,'a'),Cons ((2,'b'),Empty)) -- > let y = zip' . unzip_' -- > y $ Cons ((1, 'a'), Cons ((2, 'b'), Empty)) -- Cons ((1,'a'),Cons ((2,'b'),Empty))
Finally we have an exhaustive (can handle lists of different lengths) definition of zip' and the results of composing zip' with unzip' and unzip_' using ghci.