Function Composition VS Function Application

Question

1. Do anyone can give example of function composition?

2. This is the definition of function composition operator?

   (.) :: (b -> c) -> (a -> b) -> a -> c
   f . g = \x -> f (g x)
   

This shows that it takes two functions and return a function but i remember someone has expressed the logic in english like

boy is human -> ali is boy -> ali is human

1. What this logic related to function composition?
2. What is the meaning of strong binding of function application and composition and which one is more strong binding than the other?

Please help.

Thanks.

Answer 1

(Edit 1: I missed a couple components of your question the first time around; see the bottom of my answer.)

The way to think about this sort of statement is to look at the types. The form of argument that you have is called a syllogism; however, I think you are mis-remembering something. There are many different kinds of syllogisms, and yours, as far as I can tell, does not correspond to function composition. Let's consider a kind of syllogism that does:

1. If it is sunny out, I will get hot.
2. If I get hot, I will go swimming.
3. Therefore, if it is sunny about, I will go swimming.

This is called a hypothetical syllogism. In logic terms, we would write it as follows: let S stand for the proposition "it is sunny out", let H stand for the proposition "I will get hot", and let W stand for the proposition "I will go swimming". Writing α → β for "α implies β", and writing ∴ for "therefore", we can translate the above to:

1. S → H
2. H → W
3. ∴ S → W

Of course, this works if we replace S, H, and W with any arbitrary α, β, and γ. Now, this should look familiar. If we change the implication arrow → to the function arrow ->, this becomes

1. a -> b
2. b -> c
3. ∴ a -> c

And lo and behold, we have the three components of the type of the composition operator! To think about this as a logical syllogism, you might consider the following:

1. If I have a value of type a, I can produce a value of type b.
2. If I have a value of type b, I can produce a value of type c.
3. Therefore, if I have a value of type a, I can produce a value of type c.

This should make sense: in f . g, the existence of a function g :: a -> b tells you that premise 1 is true, and f :: b -> c tells you that premise 2 is true. Thus, you can conclude the final statement, for which the function f . g :: a -> c is a witness.

I'm not entirely sure what your syllogism translates to. It's almost an instance of modus ponens, but not quite. Modus ponens arguments take the following form:

1. If it is raining, then I will get wet.
2. It is raining.
3. Therefore, I will get wet.

Writing R for "it is raining", and W for "I will get wet", this gives us the logical form

1. R → W
2. R
3. ∴ W

Replacing the implication arrow with the function arrow gives us the following:

1. a -> b
2. a
3. ∴ b

And this is simply function application, as we can see from the type of ($) :: (a -> b) -> a -> b. If you want to think of this as a logical argument, it might be of the form

1. If I have a value of type a, I can produce a value of type b.
2. I have a value of type a.
3. Therefore, I can produce a value of type b.

Here, consider the expression f x. The function f :: a -> b is a witness of the truth of proposition 1; the value x :: a is a witness of the truth of proposition 2; and therefore the result can be of type b, proving the conclusion. It's exactly what we found from the proof.

Now, your original syllogism takes the following form:

1. All boys are human.
2. Ali is a boy.
3. Therefore, Ali is human.

Let's translate this to symbols. Bx will denote that x is a boy; Hx will denote that x is human; a will denote Ali; and ∀x. φ says that φ is true for all values of x. Then we have

1. ∀x. Bx → Hx
2. Ba
3. ∴ Ha

This is almost modus ponens, but it requires instantiating the forall. While logically valid, I'm not sure how to interpret it at the type-system level; if anybody wants to help out, I'm all ears. One guess would be a rank-2 type like (forall x. B x -> H x) -> B a -> H a, but I'm almost sure that that's wrong. Another guess would be a simpler type like (B x -> H x) -> B Int -> H Int, where Int stands for Ali, but again, I'm almost sure it's wrong. Again: if you know, please let me know too!

And one last note. Looking at things this way—following the connection between proofs and programs—eventually leads to the deep magic of the Curry-Howard isomorphism, but that's a more advanced topic. (It's really cool, though!)

---

Edit 1: You also asked for an example of function composition. Here's one example. Suppose I have a list of people's middle names. I need to construct a list of all the middle initials, but to do that, I first have to exclude every non-existent middle name. It is easy to exclude everyone whose middle name is null; we just include everyone whose middle name is not null with filter (\mn -> not $ null mn) middleNames. Similarly, we can easily get at someone's middle initial with head, and so we simply need map head filteredMiddleNames in order to get the list. In other words, we have the following code:

allMiddleInitials :: [Char]
allMiddleInitials = map head $ filter (\mn -> not $ null mn) middleNames

But this is irritatingly specific; we really want a middle-initial–generating function. So let's change this into one:

getMiddleInitials :: [String] -> [Char]
getMiddleInitials middleNames = map head $ filter (\mn -> not $ null mn) middleNames

Now, let's look at something interesting. The function map has type (a -> b) -> [a] -> [b], and since head has type [a] -> a, map head has type [[a]] -> [a]. Similarly, filter has type (a -> Bool) -> [a] -> [a], and so filter (\mn -> not $ null mn) has type [a] -> [a]. Thus, we can get rid of the parameter, and instead write

-- The type is also more general
getFirstElements :: [[a]] -> [a]
getFirstElements = map head . filter (not . null)

And you see that we have a bonus instance of composition: not has type Bool -> Bool, and null has type [a] -> Bool, so not . null has type [a] -> Bool: it first checks if the given list is empty, and then returns whether it isn't. This transformation, by the way, changed the function into point-free style; that is, the resulting function has no explicit variables.

You also asked about "strong binding". What I think you're referring to is the precedence of the . and $ operators (and possibly function application as well). In Haskell, just as in arithmetic, certain operators have higher precedence than others, and thus bind more tightly. For instance, in the expression 1 + 2 * 3, this is parsed as 1 + (2 * 3). This is because in Haskell, the following declarations are in force:

infixl 6 +
infixl 7 *

The higher the number (the precedence level), the sooner that that operator is called, and thus the more tightly the operator binds. Function application effectively has infinite precedence, so it binds the most tightly: the expression f x % g y will parse as (f x) % (g y) for any operator %. The . (composition) and $ (application) operators have the following fixity declarations:

infixr 9 .
infixr 0 $

Precedence levels range from zero to nine, so what this says is that the . operator binds more tightly than any other (except function application), and the $ binds less tightly. Thus, the expression f . g $ h will parse as (f . g) $ h; and in fact, for most operators, f . g % h will be (f . g) % h and f % g $ h will be f % (g $ h). (The only exceptions are the rare few other zero or nine precedence operators.)