Composition is the beauty of functional programming & haskell with it's typeclasses excels at this.
Let's see what
Functors are and how they compose.
Almost all languages have a way to apply function on all elements of a data structure.
Haskell goes beyond just mapping over array-like objects & allows defining an abstract method for multiple structures.
If we consider the example of a
Maybe data-type (which
may hold a value), a common
use-case is to apply function to inner value if it is present:
x = Just 1 fmap (+1) x -- # => Just 2 y = Nothing fmap (+1) y -- # => Nothing
One can think of structures as boxes.
fmap applies function to element inside that box, wraps it in the
same box and returns it. link
fmap is a function of
Functor typeclass & structures like List & Maybe implement Functor typeclass:
class Functor f where fmap :: (a -> b) -> f a -> f b -- f is abstract structure here
Well-defined functors are structure-preserving - ie. they don't modify the structure.
fmap (+2) [1,2,3] -- # => [3,4,5]
Now suppose we want to apply function to nested lists
fmap (fmap (+1)) [[1,2,3],[4,5]] -- # => [[2,3,4],[5,6]]
Can we compose these two
fmap1 :: (a -> b) -> (f1 a -> f1 b) fmap2 :: (x -> y) -> (f2 x -> f2 y)
In haskell, all functions are curried - which means
fmap1 when supplied with
one argument (
a -> b) returns another function which takes
f1 a and returns
x -> y with
f1 a -> f1 b: (replace
f1 a &
fmap2 :: (f1 a -> f1 b) -> (f2 (f1 a) -> f2 (f1 b))
f2 (f1 a) there? Nested structure! We just got
fmap for a nested structure!
We took the output of
(f1 a -> f1 b) and passed it as first argument to
fmap2. Which is nothing but function composition:
(.) :: (b -> c) -> (a -> b) -> a -> c
Output of function
a -> b (b) is passed to
b -> c.
Above example becomes:
(fmap2 . fmap1) :: (a -> b) -> (f2 (f1 a) -> f2 (f1 b))
Cleaning it up a bit & adding typeclass constraints:
(fmap . fmap) :: (Functor f1, Functor f2) => (a -> b) -> f1 (f2 a) -> f1 (f2 b)
Note the entire structure
f1 (f2) is preserved in the output - only
as are transformed to
Now we can do this:
(fmap . fmap) (+1) [[1,2,3],[4,5]] -- # => [[2,3,4],[5,6]]
We jumped inside two lists & applied the function
(+1). But note those two structures(functors) need not be lists or rather need not even be of the same type.
They can be different (
f2 in above definition), although both must have instances of Functor.
(fmap . fmap) (+1) [Just 1, Nothing, Just 2] -- # => [Just 2, Nothing, Just 3]
But why limit to just two?
(fmap . fmap . fmap) (+1) [Just , Nothing, Just ] -- # => [Just ,Nothing,Just ]
Being pure & structure preserving allows Functors to compose in such a neat way. Just beautiful!