Haskell complex function composition

Question

I'm trying to learn function composition in Haskell. I have following exercise.
I have function:h x y = f (g x y)and i need to find function composition equal to it:

a) f . g  
b) (f.).g  
c) (.)f(.g)  
d) f(.g)

I know that (.)f g = f.g = f(g x) but i don't understand this complicated function composition

Side note: writing `f.g = f(g x)` is a bit sloppy. In fact, `f.g = \x -> f(g x)`. — Daniel Wagner, Jun 21 '17 at 19:01

score 4 · Accepted Answer · answered Jun 21 '17 at 18:48

4

The correct answer is (b): (f.).g

Let us analyze this function. The (f.) part is short for ((.) f), so we already solved that one, and thus the function - without syntactical sugar - is:

(.) ((.) f) g

Now we can rewrite the first (.) function to a lambda-expression:

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

And now when we evaluate the second function on the left (((.) f)) further, we obtain:

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

or:

\x -> f . g x

So if we convert the (.) function in a lambda expression, we obtain:

\x -> (\y -> f ((g x) y))

Now we can make this expression more elegantly. (g x) y can be rewritten to g x y:

\x -> (\y -> f (g x y))

and we can rewrite nested lambda expressions into a single lambda expression:

\x y -> f (g x y)

Which is what we wanted.

answered Jun 21 '17 at 18:48

Willem Van Onsem

443,496
30
428
555

I think i understand. So d) is `f(.g) = f((.)g) = f(\x -> g x)` ? – Tomasz Jun 21 '17 at 18:59
1

@Tomasz: the last step is incorrect: `(.) g` is `\h x -> g (h x)`. So for your example `f (. g) = f ((.) g) = f (\h x -> g (h x))`. – Willem Van Onsem Jun 21 '17 at 19:00
"h" is missing function? – Tomasz Jun 21 '17 at 19:03
@Tomasz: `h` is a parameter, but it indeed should be a function. – Willem Van Onsem Jun 21 '17 at 19:03
@WillemVanOnsem `f (. g)` is not `f ((.) g)` -- the latter is `f (g .)`. (This is about your comment, not your answer.) – chi Jun 21 '17 at 20:11
@chi: euh yeah, I don't know where that came from :s. – Willem Van Onsem Jun 21 '17 at 21:52

Mulan · Answer 2 · 2017-06-22T05:28:47.030

3

You can also use (.) (.) (.) - despite it being somewhat challenging to understand, the evaluation results in an elegant form identical to the one you're looking for

comp2 = (.) (.) (.)
comp2 f g x y == f (g x y)

Evaluation of (.) (.) (.)

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

-- evaluate
(.) (.) (.)
(\f -> \g -> \x -> f (g x)) (.) (.)
(\g -> \x -> (.) (g x)) (.)
\x -> (.) ((.) x)
\x -> (\f -> \g -> \x' -> f (g x')) ((.) x)
\x -> \g -> \x' -> ((.) x) (g x')
\x -> \g -> \x' -> ((\f -> \g' x'' -> f (g' x'')) x) (g x')
\x -> \g -> \x' -> (\g' -> \x'' -> x (g' x'')) (g x')
\x -> \g -> \x' -> \x'' -> x ((g x') x'')
\x -> \g -> \x' -> \x'' -> x (g x' x'')

-- alpha rename
\f -> \g -> \x -> \y -> f (g x y)

-- collapse lambdas 
\f g x y -> f (g x y)

Understanding a pattern of (.) compositions

-- comp2
comp2 = (.) (.) (.)
comp2 f g x y == f (g x y)

-- comp3
comp3 = (.) (.) comp2
comp3 f g x y z == f (g x y z)

-- comp4
comp4 = (.) (.) comp3
comp4 f g w x y z == f (g w x y z)

edited Jun 22 '17 at 05:28

answered Jun 21 '17 at 18:58

Mulan

129,518
31
228
259

3

I downvoted, for three reasons: 1. The level of knowledge displayed in the question doesn't support the assumption that the behavior of this kind of double-composition would be immediately apparent to the question asker, so some explanatory sentences at the beginning are needed. 2. This doesn't actually "tie the knot" back to the original question, so some explanatory sentences at the end are needed to show how we can start with double-composition of this form and end with one of the four possible choices. 3. I agree that this is a stupid name for it. So don't propagate that name! – Daniel Wagner Jun 21 '17 at 19:06
@DanielWagner thanks for the thorough comment. I've adjusted my answer some in hopes that it's more informative. – Mulan Jun 21 '17 at 19:32

Haskell complex function composition

2 Answers2

Linked