Blog/Loop fusion in PureScript with Coyoneda

From foldr
Jump to: navigation, search

Information icon.svg This is a blog post. If you want to comment on this blog post, please mention me on Twitter @rightfold. I will set up proper comment functionality later.

WordPress blue logo.svg This blog post was migrated from my old WordPress blog. If you want to link to this blog post, please link to this page instead of to the WordPress blog.

Consider the following transformation functions:

f :: forall f. (Functor f) => f Int -> f Int
f = map \x -> x * x

g :: forall f. (Functor f) => f Int -> f String
g = map show

h :: forall f. (Functor f) => f String -> f Int
h = map length

i :: forall f. (Functor f) => f Int -> f Int
i x = h (g (f x))

We may call this function on lists, for there is a list functor:

i (1 : 2 : 3 : 4 : Nil)

This will apply f, g, and h to each element of the list. While this works, it causes three list iterations. This is expensive for large lists.

Instead, we want to loop over the list only once. This is possible, because there is a law that states that map f <<< map g is the same as map (f <<< g) for any f and g. This would however require us to change the definition of i, which may be outside our control.

To solve this problem we can use the coyoneda functor. The coyoneda functor, rather than immediately applying a given function to each list element, stores a composition of the functions passed to it. This composition can then finally be applied to each element of the list; looping only once as a result. We can use the coyoneda functor as follows:

lowerCoyoneda (i (liftCoyoneda (1 : 2 : 3 : 4 : Nil)))

There are two steps in this:

  1. liftCoyoneda will cause the map applications in f, g and h to build up the composition length <<< show <<< (\x -> x * x).
  2. lowerCoyoneda will pass the composition to the list functor, exploiting the law mentioned above.

This way we have performed loop fusion without restructuring the original code. You can find a demo on Try PureScript. You can read more about Coyoneda on Pursuit.