[SOLVED] Composing function composition: How does (.).(.) work?

`(.)` takes two functions that take one value and return a value:

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

Since `(.)` takes two arguments, I feel like `(.).(.)` should be invalid, but it's perfectly fine:

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

What is going on here? I realize this question is badly worded...all functions really just take one argument thanks to currying. Maybe a better way to say it is that the types don't match up.

@Mirzhan Irkegulov 2015-06-16 16:45:37

(Read my answer on function composition, \$ operator and point-free style first.)

Imagine you have a simple function: it adds up 2 numbers and then negates the result. We'll call it `foo`:

``````foo a b = negate (a + b)
``````

Now let's make it point-free step by step and see what we end up with:

``````foo a b = negate \$ a + b
foo a b = negate \$ (+) a b
foo a b = negate \$ (+) a \$ b
foo a b = negate . (+) a \$ b
foo a   = negate . (+) a -- f x = g x is equivalent to f = g
foo a   = (.) negate ((+) a) -- any infix operator is just a function
foo a   = (negate.) ((+) a) -- (2+) is the same as ((+) 2)
foo a   = (negate.) \$ (+) a
foo a   = (negate.) . (+) \$ a
foo     = (negate.) . (+)
foo     = ((.) negate) . (+)
foo     = (.) ((.) negate) (+) -- move dot in the middle in prefix position
foo     = ((.) ((.) negate)) (+) -- add extra parentheses
``````

Now let's analyze expression `(.) ((.) negate)` more closely. It's a partial application of `(.)` function, whose first argument is `((.) negate)`. Can we transform it even further? Yes we can:

``````(.) ((.) negate)
(.) . (.) \$ negate -- because f (f x) is the same as (f . f) x
(.)(.)(.) \$ negate
((.)(.)(.)) negate
``````

`(.).(.)` is equivalent to `(.)(.)(.)`, because in the 1st expression, the dot in the middle can be moved in prefix position and surrounded with parentheses, which gives rise to the 2nd expression.

Now we can rewrite our `foo` function:

``````foo = ((.).(.)) negate (+)
foo = ((.)(.)(.)) negate (+) -- same as previous one
foo = negate .: (+)
where (.:) = (.).(.)
``````

Now you know that `(.).(.)` is equivalent to `(\f g x y -> f (g x y))`:

``````(\f g x y -> f (g x y)) negate (+) 2 3 -- returns -5
((.).(.)) negate (+) 2 3 -- returns -5
``````

@Chris Taylor 2013-07-11 10:33:59

This is one of those neat cases where I think it's simpler to grasp the more general case first, and then think about the specific case. So let's think about functors. We know that functors provide a way to map functions over a structure --

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

But what if we have two layers of the functor? For example, a list of lists? In that case we can use two layers of `fmap`

``````>>> let xs = [[1,2,3], [4,5,6]]
>>> fmap (fmap (+10)) xs
[[11,12,13],[14,15,16]]
``````

But the pattern `f (g x)` is exactly the same as `(f . g) x` so we could write

``````>>> (fmap . fmap) (+10) xs
[[11,12,13],[14,15,16]]
``````

What is the type of `fmap . fmap`?

``````>>> :t fmap.fmap
:: (Functor g, Functor f) => (a -> b) -> f (g a) -> f (g b)
``````

We see that it maps over two layers of functor, as we wanted. But now remember that `(->) r` is a functor (the type of functions from `r`, which you might prefer to read as `(r ->)`) and its functor instance is

``````instance Functor ((->) r) where
fmap f g = f . g
``````

For a function, `fmap` is just function composition! When we compose two `fmap`s we map over two levels of the function functor. We initially have something of type `(->) s ((->) r a)`, which is equivalent to `s -> r -> a`, and we end up with something of type `s -> r -> b`, so the type of `(.).(.)` must be

``````(.).(.) :: (a -> b) -> (s -> r -> a) -> (s -> r -> b)
``````

which takes its first function, and uses it to transform the output of the second (two-argument) function. So for example, the function `((.).(.)) show (+)` is a function of two arguments, that first adds its arguments together and then transforms the result to a `String` using `show`:

``````>>> ((.).(.)) show (+) 11 22
"33"
``````

There is then a natural generalization to thinking about longer chains of `fmap`, for example

``````fmap.fmap.fmap ::
(Functor f, Functor g, Functor h) => (a -> b) -> f (g (h a)) -> f (g (h b))
``````

which maps over three layers of functor, which is equivalent to composing with a function of three arguments:

``````(.).(.).(.) :: (a -> b) -> (r -> s -> t -> a) -> (r -> s -> t -> b)
``````

for example

``````>>> import Data.Map
>>> ((.).(.).(.)) show insert 1 True empty
"fromList [(1,True)]"
``````

which inserts the value `True` into an empty map with key `1`, and then converts the output to a string with `show`.

These functions can be generally useful, so you sometimes see them defined as

``````(.:) :: (a -> b) -> (r -> s -> a) -> (r -> s -> b)
(.:) = (.).(.)
``````

so that you can write

``````>>> let f = show .: (+)
>>> f 10 20
"30"
``````

Of course, a simpler, pointful definition of `(.:)` can be given

``````(.:) :: (a -> b) -> (r -> s -> a) -> (r -> s -> b)
(f .: g) x y = f (g x y)
``````

which may help to demystify `(.).(.)` somewhat.

@eccstartup 2013-12-24 15:15:20

Cool! Those examples are interesting and helpful!

@Toxaris 2013-07-11 08:20:16

Here is a simpler example of the same phenomenon:

``````id :: a -> a
id x = x
``````

The type of id says that id should take one argument. And indeed, we can call it with one argument:

``````> id "hello"
"hello"
``````

But it turns out what we can also call it with two arguments:

``````> id not True
False
``````

Or even:

``````> id id "hello"
"hello"
``````

What is going on? The key to understanding `id not True` is to first look at `id not`. Clearly, that's allowed, because it applies id to one argument. The type of `not` is `Bool -> Bool`, so we know that the `a` from id's type should be `Bool -> Bool`, so we know that this occurrence of id has type:

``````id :: (Bool -> Bool) -> (Bool -> Bool)
``````

Or, with less parentheses:

``````id :: (Bool -> Bool) -> Bool -> Bool
``````

So this occurrence of id actually takes two arguments.

The same reasoning also works for `id id "hello"` and `(.) . (.)`.

@Jon Purdy 2013-07-11 06:44:40

Let’s ignore types for a moment and just use lambda calculus.

• Desugar infix notation:
`(.) (.) (.)`

• Eta-expand:
`(\ a b -> (.) a b) (\ c d -> (.) c d) (\ e f -> (.) e f)`

• Inline the definition of `(.)`:
`(\ a b x -> a (b x)) (\ c d y -> c (d y)) (\ e f z -> e (f z))`

• Substitute `a`:
`(\ b x -> (\ c d y -> c (d y)) (b x)) (\ e f z -> e (f z))`

• Substitute `b`:
`(\ x -> (\ c d y -> c (d y)) ((\ e f z -> e (f z)) x))`

• Substitute `e`:
`(\ x -> (\ c d y -> c (d y)) (\ f z -> x (f z)))`

• Substitute `c`:
`(\ x -> (\ d y -> (\ f z -> x (f z)) (d y)))`

• Substitute `f`:
`(\ x -> (\ d y -> (\ z -> x (d y z))))`

• Resugar lambda notation:
`\ x d y z -> x (d y z)`

And if you ask GHCi, you’ll find that this has the expected type. Why? Because the function arrow is right-associative to support currying: the type `(b -> c) -> (a -> b) -> a -> c` really means `(b -> c) -> ((a -> b) -> (a -> c))`. At the same time, the type variable `b` can stand for any type, including a function type. See the connection?

@eccstartup 2013-12-24 15:08:10

Can you explain a bit how to use this `boobs operator`?

@Jon Purdy 2013-12-24 18:47:23

@eccstartup: `(.:) = (.) . (.); countWhere = length .: filter; countWhere = (length .) . filter; countWhere (>5) [1..10] == 5`

@J. Abrahamson 2013-07-11 06:08:00

Let's first play typechecker for the mechanical proof. I'll describe an intuitive way of thinking about it afterward.

I want to apply `(.)` to `(.)` and then I'll apply `(.)` to the result. The first application helps us to define some equivalences of variables.

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

let b = (b' -> c')
c = (a' -> b') -> a' -> c'

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

Then we begin the second, but get stuck quickly...

``````let a = (b'' -> c'')
``````

This is key: we want to `let b = (a'' -> b'') -> a'' -> c''`, but we already defined `b`, so instead we must try to unify --- to match up our two definitions as best we can. Fortunately, they do match

``````UNIFY b = (b' -> c') =:= (a'' -> b'') -> a'' -> c''
which implies
b' = a'' -> b''
c' = a'' -> c''
``````

and with those definitions/unifications we can continue the application

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

then expand

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

and clean it up

``````substitute b'' -> b
c'' -> c
a'  -> a
a'' -> a1

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

which, to be honest, is a bit of a counterintuitive result.

Here's the intuition. First take a look at `fmap`

``````fmap :: (a -> b) -> (f a -> f b)
``````

it "lifts" a function up into a `Functor`. We can apply it repeatedly

``````fmap.fmap.fmap :: (Functor f, Functor g, Functor h)
=> (a -> b) -> (f (g (h a)) -> f (g (h b)))
``````

allowing us to lift a function into deeper and deeper layers of `Functors`.

It turns out that the data type `(r ->)` is a `Functor`.

``````instance Functor ((->) r) where
fmap = (.)
``````

which should look pretty familiar. This means that `fmap.fmap` translates to `(.).(.)`. Thus, `(.).(.)` is just letting us transform the parametric type of deeper and deeper layers of the `(r ->)` `Functor`. The `(r ->)` `Functor` is actually the `Reader` `Monad`, so layered `Reader`s is like having multiple independent kinds of global, immutable state.

Or like having multiple input arguments which aren't being affected by the `fmap`ing. Sort of like composing a new continuation function on "just the result" of a (>1) arity function.

It's finally worth noting that if you think this stuff is interesting, it forms the core intuition behind deriving the Lenses in Control.Lens.

@Vlad the Impala 2013-07-11 21:38:04

Holy balls. Your intuition section suddenly made this a lot more clear.

@J. Abrahamson 2013-07-11 21:47:31

Haha, I'm glad! It's definitely the "right" way to think about it :)

@Jerry 2014-06-04 07:00:24

Hi J. Abrahamson, I don't follow your step of "((.) (.) (.) :: (b'' -> c'') -> (a' -> b') -> (a' -> c'))", which I highlighted in my question/answer stackoverflow.com/questions/24029422/how-to-derive-the-type-‌​of Any pointer will be greatly appreciated!

@J. Abrahamson 2014-06-04 09:41:52

That's me using the unification results from a few steps prior which unified `b' = a'' -> b''` and `c' = a'' -> c''`. It had to hold to get this far, so replacing expressions with their unions is a valid step.

@Gerard Yin 2013-07-11 06:08:29

Yes this is due to currying. `(.)` as all functions in Haskell only takes one argument. What you are composing is the first partial call to each respective composed `(.)` which takes its first argument (the first function of the composition).

@Tarrasch 2013-07-11 05:36:05

You're right, `(.)` only takes two arguments. You just seem to be confused with the syntax of haskell. In the expression `(.).(.)`, it's in fact the dot in the middle that takes the other two dots as argument, just like in the expression `100 + 200`, which can be written as `(+) 100 200`.

``````(.).(.) === (number the dots)
(1.)2.(3.) === (rewrite using just syntax rules)
(2.)(1.)(3.) === (unnumber and put spaces)
(.) (.) (.) ===
``````

And it should be even more clear from `(.) (.) (.)` that the first `(.)` is taking the second `(.)` and third `(.)` as it's arguments.

@Vlad the Impala 2013-07-11 05:52:07

Right, I'm clear on that. My point is, the first argument has the type `(b -> c)`, which is not `(.)`'s type.

@amalloy 2013-07-11 07:10:28

@VladtheImpala, the type of `(.)` is `(y -> z) -> (x -> y) -> (x -> z)`. If you let `b` be `(y -> z)` and `c` be `(x -> y) -> (x -> z)`, you'll see that the two types are compatible after all.

[SOLVED] Haskell currying explanation needed

• 2018-08-22 09:03:02
• Wouter Vandenputte
• 112 View
• 4 Score
• 2 Answer
• Tags:   haskell currying

[SOLVED] Shorthand way for assigning a single field in a record, while copying the rest of the fields?

• 2013-02-19 10:51:46
• jaymmer
• 22724 View
• 106 Score
• 3 Answer
• Tags:   haskell record

[SOLVED] How does ap fromMaybe compose?

• 2016-01-05 22:34:27
• Mark Seemann
• 647 View
• 19 Score
• 4 Answer
• Tags:   haskell monads

[SOLVED] Test if a value matches a constructor

• 2014-08-30 23:09:27
• ridiculous_fish
• 2654 View
• 39 Score
• 3 Answer
• Tags:   haskell