Alex Rivera | Logout

Importance of isomorphic functions

Asked 2012-06-28T12:57:19.580
80

Short Question: What is the importance of isomorphic functions in programming (namely in functional programming)?

Long Question: I'm trying to draw some analogs between functional programming and concepts in Category Theory based off of some of the lingo I hear from time-to-time. Essentially I'm trying to "unpackage" that lingo into something concrete I can then expand on. I'll then be able to use the lingo with an understanding of just-what-the-heck-I'm-talking about. Which is always nice.

One of these terms I hear all the time is Isomorphism, I gather this is about reasoning about equivalence between functions or function compositions. I was wondering if someone could provide some insights into some common patterns where the property of isomorphism comes in handy (in functional programming), and any by-products gained, such as compiler optimizations from reasoning about isomorphic functions.

functional-programming isomorphism
Edit
Report

1 Answer

25

An isomorphism u :: a -> b is a function that has an inverse, i.e. another function v :: b -> a such that the relationships

u . v = id
v . u = id

are satisfied. You say that two types are isomorphic if there is an isomorphism between them. This essentially means that you can consider them to be the same type - anything that you can do with one, you can do with the other.

Isomorphism of functions

The two function types

(a,b) -> c
a -> b -> c

are isomorphic, since we can write

u :: ((a,b) -> c) -> a -> b -> c
u f = \x y -> f (x,y)

v :: (a -> b -> c) -> (a,b) -> c
v g = \(x,y) -> g x y

You can check that u . v and v . u are both id. In fact, the functions u and v are better known by the names curry and uncurry.

Isomorphism and Newtypes

We exploit isomorphism whenever we use a newtype declaration. For example, the underlying type of the state monad is s -> (a,s) which can be a little confusing to think about. By using a newtype declaration:

newtype State s a = State { runState :: s -> (a,s) }

we generate a new type State s a which is isomorphic to s -> (a,s) and which makes it clear when we use it, we are thinking about functions that have modifiable state. We also get a convenient constructor State and a getter runState for the new type.

Monads and Comonads

For a more advanced viewpoint, consider the isomorphism using curry and uncurry that I used above. The Reader r a type has the newtype declaration

newType Reader r a = Reader { runReader :: r -> a }

                        
                        

                            answered 2012-06-28T14:58:42.687

Your Answer