Haskell function composition, type of (.)(.) and how it's presented

Question

So i know that:

(.) = (f.g) x = f (g x)

And it's type is (B->C)->(A->B)->A->C But what about:

(.)(.) = _? = _?

How this is represented? I thought of:

(.)(.) = (f.g)(f.g)x = f(g(f(g x))) // this
(.)(.) = (f.g.h)x = f(g(h x)) // or this

But as far as i tried to get type of it, it's not correct to what GHCi tells me. So what are both "_?"

Also - what does function/operator $ do?

I wonder whether we should add a tag for the name of `(.)(.)` and `(.).(.)`? — leftaroundabout, Apr 24 '13 at 22:25

dave4420 · Answer 1 · 2013-04-24T21:42:02.760

14

First off, you're being sloppy with your notation.

(.) = (f.g) x = f (g x)  -- this isn't true

What is true:

(.) f g x = (f.g) x = f (g x)
(.) = \f g x -> f (g x)

And its type is given by

(.) :: (b -> c) -> (a -> b) -> a -> c
       -- n.b. lower case, because they're type *variables*

Meanwhile

(.)(.) :: (a -> b -> d) -> a -> (c -> b) -> c -> d
          -- I renamed the variables ghci gave me

Now let's work out

(.)(.) = (\f' g' x' -> f' (g' x')) (\f g x -> f (g x))
       = \g' x' -> (\f g x -> f (g x)) (g' x')
       = \g' x' -> \g x -> (g' x') (g x)
       = \f y -> \g x -> (f y) (g x)
       = \f y g x -> f y (g x)
       = \f y g x -> (f y . g) x
       = \f y g -> f y . g

And ($)?

($) :: (a -> b) -> a -> b
f $ x = f x

($) is just function application. But whereas function application via juxtaposition is high precedence, function application via ($) is low precedence.

square $ 1 + 2 * 3 = square (1 + 2 * 3)
square 1 + 2 * 3 = (square 1) + 2 * 3  -- these lines are different

edited Apr 24 '13 at 21:42

answered Apr 24 '13 at 21:33

dave4420

46,404
6
118
152

It's all fine, but lets say i want to use (.)(.) operator in GHCi. If i want to use (.) i say: (.) function1 function2 parameters_for_f2 but if i want to use (.)(.) what would i have to write next? – RippeR Apr 24 '13 at 21:44
2

`(.)(.)` isn't really an operator, it's an expression. You could write `(.) (.) f y g`. – dave4420 Apr 24 '13 at 21:48
That's the problem. If i write: (.) (.) succ succ succ 3 i get error. Also if i write: (.) (.) id succ succ 3 it now magicly works but id and succ hase same arity. – RippeR Apr 24 '13 at 21:53
1

@RippeR no, `id` is polymorphic while `succ` is only defined on enums. Since `a -> b` is not an enum, `(.)(.) succ succ succ 3` does not make sense. `(.) (.) id = (.)` – Philip JF Apr 24 '13 at 22:04
So if: (.)(.) f g h _____ is not equal to (f.g.h) ___, that what is this euqal to? (using it in infix form)? – RippeR Apr 24 '13 at 22:10
2

@RippeR `(.) (.) f y g x = f y (g x)`, as in my answer. – dave4420 Apr 24 '13 at 22:14
It would be a lot clearer if you woudn't name funtion as 'y' but... maybe 'h'? :> So now i can use: id succ (succ 5) in example, but i still cant figure out why first one has to be polymorphic and not any type. I still can do (succ.succ.succ) 3 and it gives me 6. Lets say that i have: f g (h x) does that mean that h take's x as argument, g takes h(x) as argument and f takes g (not g(h(x))) as argument? It would explain it, since id can take function as well as number, but succ can't take function. – RippeR Apr 24 '13 at 22:26
1

@RippeR `y` is *not* a function. Read again the type signature I gave for `(.)(.)`. – dave4420 Apr 24 '13 at 22:34
1

It would be a lot easier if i understood at least 10% of that... ;) I think it's too much for me, at least for now... It's a middle of the night and it's just to strage for me (someone whos all programming experience is in C++ and similiar languages). Buth thanks anyway, i will try to get something out of it tommorrow (which is latter today for me now ;)). Btw. do you know good tutorial or book for begginers (or someone who programmed in C++/C#/Java/PHP etc.)? You sound very good at subject so maybe you know something good. ;) – RippeR Apr 24 '13 at 22:42

score 7 · Answer 2 · edited May 23 '17 at 12:34

As dave4420 mentions,

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

So what is the type of (.) (.)? dave4420 skips that part, so here it is: (.) accepts a value of type b -> c as its first argument, so

(.) :: (   b     ->       c             ) -> (a -> b) -> a -> c
(.) ::  (d -> e) -> ((f -> d) -> f -> e)

so we have b ~ d->e and c ~ (f -> d) -> f -> e, and the resulting type of (.)(.) is (a -> b) -> a -> c. Substituting, we get

(a -> d -> e) -> a -> (f -> d) -> f -> e

Renaming, we get (a -> b -> c) -> a -> (d -> b) -> d -> c. This is a function f that expects a binary function g, a value x, a unary function h and another value y:

f g x h y = g x (h y)

That's the only way this type can be realized: g x :: b -> c, h y :: b and so g x (h y) :: c, as needed.

Of course in Haskell, a "unary" function is such that expects one or more arguments; similarly a "binary" function is such that expects two or more arguments. But not less than two (so using e.g. succ is out of the question).

We can also tackle this by writing equations, combinators-style¹. Equational reasoning is easy:

(.) (.) x y z w q = 
((.) . x) y z w q =
(.) (x y) z w q =
(x y . z) w q =
x y (z w) q

We just throw as much variables as needed into the mix and then apply the definition back and forth. q here was an extra, so we can throw it away and get the final definition,

_BB x y z w = x y (z w)

(coincidentally, (.) is known as B-combinator).

¹ a b c = (\x -> ... body ...) is equivalent to a b c x = ... body ..., and vice versa, provided that x does not appear among {a,b,c}.

Haskell function composition, type of (.)(.) and how it's presented

2 Answers2

Linked