Composing functions
and beyond

dev* 2015


  • functions like this and that
  • composition for all!
  • beyond functions

examples in Haskell,
but the ideas carry to all functional languages

Disclaimer: I am yet to find the time to think about laws and prove my claims, so be a sceptical reader!


foo :: a -> b

"foo is a function from value of type a to value of type b"

public static <A,B> B foo(A a) {...} // java

function composition

(.) :: (b -> c) -> (a -> b) -> (a -> c)

baz = bar . foo

"dot is a function from two functions to a third function"

baz = bar ∘ foo // math
Function<A,C> baz = bar.compose(foo) // java

different kinds of functions

use case

  1. get the smallest integer from a list
  2. divide "some number" with this integer
  3. compose these in the spirit of functional programming

(types are commented out,
they carry no required information)

a -> b

a regular function

from a value to a value of possibly another type

ordinary function composition

--functionAB :: [Int] -> Int
functionAB a = minimum a

--functionBC :: Int -> Int
functionBC b = 42 `div` b

--function :: [Int] -> Int
function = functionBC . functionAB

f a -> f b

a lifted or a contextual function

like a -> b but lifted to work with values in a context

public static <A,B> F<B> foo(F<A> a) {...} // java

this is easily achieved by making f a Functor

"contextual" function composition

--liftedAB :: Maybe [Int] -> Maybe Int
liftedAB = fmap functionAB

--liftedBC :: Maybe Int -> Maybe Int
liftedBC = fmap functionBC

--lifted :: Maybe [Int] -> Maybe Int
lifted = liftedBC . liftedAB

sometimes we want to include some
pass-through context

logging, profiling...

still composable?

f (a -> b)

an applicative style function

like a -> b but whole function wrapped in a context

allows the abstraction to do something with the function

public static /* exercise for the reader ;) */ {...} // java

applicative function composition

-- composition for Applicatives (why is this not in hackage?)
(<.>) :: Applicative f => f (b -> c) -> f (a -> b) -> f (a -> c)
f <.> g = (.) <$> f <*> g

-- Tuple2 happens to be a suitable Applicative:
type Logged = (,) [String]

--applicativeAB :: Logged ([Int] -> Int)
applicativeAB = (["calculating minimums..."], minimum)

--applicativeBC :: Logged (Int -> Int)
applicativeBC = (["dividing by the value..."], (42 `div` ))

--applicative :: Logged ([Int] -> Int)
applicative = applicativeBC <.> applicativeAB

our example would sometimes divide by zero

and fails with an empty array

could we catch these in the type system?

a -> m b

a monadic function

public static <M,A,B> M<B> foo(A a) {...} // java, in theory...

monadic function composition

--monadicAmB :: [Int] -> Maybe Int
monadicAmB [] = Nothing
monadicAmB a = Just (minimum a)

--monadicBmC :: Int -> Maybe Int
monadicBmC 0 = Nothing
monadicBmC b = Just (42 `div` b)

--monadic :: [Int] -> Maybe Int
monadic  = monadicBmC <=< monadicAmB

our example has a magic constant

perhaps we would like to get the constant from
an environment?

w a -> b

a comonadic function

public static <W,A,B> B foo(W<A> wa) {...} // java, in theory...

comonadic function composition

-- Tuple2 happens to be a suitable Comonad,
-- so we can simply pass in the environment e as the left side:
type WithEnv e = (,) e

--comonadic_mAB :: WithEnv Int [Int] -> Int
comonadic_mAB (e,[]) = e
comonadic_mAB (e,a) = minimum a

--comonadic_mBC :: WithEnv Int Int -> Int
comonadic_mBC (e,0) = e
comonadic_mBC (e,b) = e `div` b

--comonadic :: WithEnv Int [Int] -> Int
comonadic  = comonadic_mBC =<= comonadic_mAB

composition, repeated:

regular functions

foo :: a -> b

bar :: b -> c

baz = bar . foo

"contextual" functions

foo :: f a -> f b

bar :: f b -> f c

baz = bar . foo

applicative functions

foo :: f (a -> b)

bar :: f (b -> c)

baz = bar <.> foo

<.> is defined in a few random places...

monadic functions

foo :: a -> m b

bar :: b -> m c

baz = bar <=< foo

<=< is defined in Control.Monad

comonadic functions

foo :: w a -> b

bar :: w b -> c

baz = bar =<= foo

=<= is defined in Control.Comonad

mon... comon... WTF?

monad is just an abstraction for
composing certain kind of functions

when functions like a -> m b compose
(and obey identity and associativity laws)
m forms a monad

Similarly for comonad. That's it. No burritos.

still need something?

with monadic functions
you can affect the subsequent behavior
via contextual return values

with comonadic functions,
their behavior can be affected
by context from the input

a passionate developer would like to have both!

--both_wAmB :: WithEnv Int [Int] -> Maybe Int
both_wAmB (e,[]) = Nothing
both_wAmB (e,a)  = Just (minimum a)

--both_wBmC :: WithEnv Int Int -> Maybe Int
both_wBmC (e,0) = Nothing
both_wBmC (e,b) = Just (e `div` b)

-- Whoops, how to compose these?
--both :: WithEnv Int [Int] -> Maybe Int
both = undefined

what next?

a -> b f a -> f b a -> m b w a -> b f (a -> b) ?

beyond functions

an applicative f (a -> b) is a really general absraction

can only apply the given argument and return the result

to interact with input and output we need more

our need, as a type

data MyFunctionType a b = MyFunctionType (WithEnv Int a -> Maybe b)

could make this an Applicative...
...but wouldn't help with composition

a Category

class Category cat where
  id :: cat a a
 (.) :: cat b c -> cat a b -> cat a c

category gives us composition

instance Category MyFunctionType where
  id = MyFunctionType $ Just . snd
  MyFunctionType g . MyFunctionType f = MyFunctionType $
	\(e,a) -> case f (e,a) of
                Nothing -> Nothing
                Just b -> g (e,b)

--cat_AB :: MyFunctionType [Int] Int
cat_AB = MyFunctionType f
  where f (_,[]) = Nothing
        f (_,a)  = Just (minimum a)

--cat_BC :: MyFunctionType Int Int
cat_BC = MyFunctionType f
  where f (_,0) = Nothing
        f (e,b) = Just (e `div` b)

--cat :: MyFunctionType [Int] Int
cat = cat_BC . cat_AB

now we can compose our sophisticated type

so that's it

... or could we get more?


class Functor f where
  fmap :: (a -> b) -> f a -> f b

actually, a covariant functor


class ContraFunctor f where
  contramap :: (a -> b) -> f b -> f a

a contravariant functor

homework: Google for covariance and contravariance


class Profunctor p where
  dimap :: (a -> b) -> (c -> d) -> p b c -> p a d

a functor of two type parameters,
first contravariant, second covariant

contravariant argument can be seen as input,
covariant as output

an ordinary function is a profunctor (it has input and output), but other things can be profunctors too


class Profunctor p => Strong p where
  first' :: p a b -> p (a, c) (b, c)

capability to "drop in" values to "pass through"

category +
profunctor +

simple and generic concept

combining these we get
component networks!

stream transformers, simple automata, FRP, Music signals, ...


class Profunctor p => Choice p where
  left' :: p a b -> p (Either a c) (Either b c)

can "choose its output type based on its input"

this gives us branching!


class Profunctor p => Costrong p where
  unfirst :: p (a, d) (b, d) -> p a b

can "drop out" values from input and output type

this gives us feedback loops!

all these simple concepts

are combined in a powerful interface:


instance Arrow MyFunctionType where
  arr = MyFunctionType . dimap snd Just 
  first = first'

instance ArrowChoice MyFunctionType where
  left = left'

instance ArrowLoop MyFunctionType where
  loop = unfirst

about syntax

different kinds of functions and "functions"

all can be composed,
although the operator looks different

but it's just syntax

to summarize

functional programming is all about
functions and composition

we can do composition
even though our functions are a bit weird

we can do composition
even when our functions are more than functions

recognize when you need
function composition

in any language

Haskell abstracts everything
but the concepts carry to other languages

Thank you!

this was just the tip of the iceberg

keep learning!


code from this presentation: