{"id":503,"date":"2017-01-31T23:36:52","date_gmt":"2017-01-31T23:36:52","guid":{"rendered":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/?p=503"},"modified":"2017-11-16T10:58:39","modified_gmt":"2017-11-16T10:58:39","slug":"old-graphs-from-new-types","status":"publish","type":"post","link":"https:\/\/blogs.ncl.ac.uk\/andreymokhov\/old-graphs-from-new-types\/","title":{"rendered":"Old graphs from new types"},"content":{"rendered":"

After I got back from the holiday that I planned in the previous blog post<\/a>, I spent the whole January playing with the algebra of graphs<\/a> and trying to find\u00a0interesting and useful ways of constructing graphs, focusing on writing polymorphic code that can manipulate\u00a0graph expressions without turning them into concrete data structures. I’ve put together a small toolbox containing a few\u00a0quirky\u00a0types, which I’d like to share with you in this blog post. If you are not familiar with the algebra of graphs, please read the introductory blog post<\/a> first.<\/p>\n

Update:<\/strong>\u00a0This series of blog posts was published as a functional pearl<\/a> at the Haskell Symposium 2017.<\/p>\n

<\/p>\n

Graph transpose<\/h3>\n

One of the simplest transformations one can apply to a graph is\u00a0to flip the direction of all of its edges. It’s usually straightforward to implement but whatever data structure you use to represent graphs, you will spend at least O(1)<\/em> time to modify it (say, by flipping the treatAsTransposed<\/code><\/strong> flag); much more often\u00a0you will have to traverse the data structure\u00a0and flip every edge, resulting in O(|V|+|E|)<\/em> time complexity. What if I told you that by using Haskell’s type system, we can transpose polymorphic graphs in zero<\/em>\u00a0time? Sounds\u00a0suspicious? Let’s see how this works.<\/p>\n

Consider the following Graph<\/code><\/strong> instance:<\/p>\n

newtype<\/span> Transpose<\/span> g =<\/span> T<\/span> { transpose ::<\/span> g }\r\n\r\ninstance<\/span> Graph<\/span> g<\/span> =><\/span> Graph<\/span> (Transpose<\/span> g<\/span>) where<\/span>\r\n    type<\/span> Vertex<\/span> (Transpose<\/span> g) =<\/span> Vertex<\/span> g\r\n    empty       =<\/span> T<\/span> empty\r\n    vertex      =<\/span> T<\/span> .<\/span> vertex\r\n    overlay x y =<\/span> T<\/span> $<\/span> transpose x `overlay`<\/span> transpose y\r\n    connect x y =<\/span> T<\/span> $<\/span> transpose y `connect`<\/span> transpose x -- flip<\/span>\r\n<\/pre>\n
We wrap a graph in a newtype<\/code><\/strong>\u00a0flipping the order of arguments to connect<\/code><\/strong>. Let’s check if this works:<\/p>\n
\u03bb><\/span> edgeList $<\/span> 1<\/span> * (2<\/span> +<\/span> 3<\/span>) * 4<\/span>\r\n[(1<\/span>,<\/span>2<\/span>),<\/span>(1<\/span>,<\/span>3<\/span>),<\/span>(1<\/span>,<\/span>4<\/span>),<\/span>(2<\/span>,<\/span>4<\/span>),<\/span>(3<\/span>,<\/span>4<\/span>)]\r\n\u03bb><\/span> edgeList $<\/span> transpose $<\/span> 1<\/span> * (2<\/span> +<\/span> 3<\/span>) * 4<\/span>\r\n[(2<\/span>,<\/span>1<\/span>),<\/span>(3<\/span>,<\/span>1<\/span>),<\/span>(4<\/span>,<\/span>1<\/span>),<\/span>(4<\/span>,<\/span>2<\/span>),<\/span>(4<\/span>,<\/span>3<\/span>)]\r\n<\/pre>\n
Cool! And this has zero runtime cost, because all we do is wrapping and unwrapping the newtype<\/strong><\/code>, which\u00a0is guaranteed to be free<\/a>. As an exercise, verify that transpose\u00a0is an antihomomorphism<\/a> on graphs, that is:<\/p>\n