Blog/Loop fusion in PureScript with Coyoneda
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
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
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:
liftCoyonedawill cause the
hto build up the composition
length <<< show <<< (\x -> x * x).
lowerCoyonedawill pass the composition to the list functor, exploiting the law mentioned above.