composing functions with higher arity

Question

I don't understand composing functions with arity > 1. in ghci 7.4.1 i typed:

((*).succ) 3 4
> 16

i don't fully understand the math transformation but it's clear that it's the same as

(*) (succ 3) 4

but when i do:

( (\x y z -> x).(\a b -> a*b) ) 2 3 4 5
> 10
( (\x y z -> y).(\a b -> a*b) ) 2 3 4 5
> No instance for (Num (a0 -> t0))

and now i'm totally lost. can anyone explain what happens? ps. I know that everything in haskell has only 1 parameter but it doesn't really help me :)

Answer 1

In

( (\x y z -> x).(\a b -> a*b) ) 2 3 4 5

1. they first evaluate (\a b -> a*b) 2 resulting in function like this (\b -> 2*b)
2. then evaluate (\x y z -> x) (\b -> 2*b) 3 4 that say that take the function take the 3 and take the 4 and return the function, something like this: ((\b -> 2*b) 3 4 -> (\b -> 2*b))
3. and only remains (\b -> 2*b) 5 resulting 2*5 = 10

but in

( (\x y z -> y).(\a b -> a*b) ) 2 3 4 5

the second evaluation will result in this ((\b -> 2*b) 3 4 -> 3) remaining 3 5 causing a error

Answer 2

Since you understand everything is a one-argument function, let's start from that point. Keep in mind that (\x y z -> x) is really (\x -> (\y z -> x)), which in turn really is (\x -> (\y -> (\z -> x))), but let's stop at the first step to keep the noise from brackets down.

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

hence

((\x -> (\y z -> x)) . (\a b -> a*b)) 2 =
(\x -> (\y z -> x)) ((\a -> (\b -> a*b)) 2) =
(\x -> (\y z -> x)) (\b -> 2*b) =
(\y z -> (\b -> 2*b))

Now remember the second step and expand (\y z -> ...):

(\y z -> (\b -> 2*b)) 3 4 =
(\y -> (\z -> (\b -> 2*b))) 3 4 =
   -- \y -> ... given anything, returns a function \z -> ...
(\z -> (\b -> 2*b)) 4 =
   -- \z -> ... given anything, returns a function \b -> ...
(\b -> 2*b)

which finally is:

(\b -> 2*b) 5 = 2*5 = 10

The story unfolds differently, if the first function returns y instead of x:

((\x -> (\y z -> y)) . (\a -> (\b -> a*b))) 2 =
(\x -> (\y z -> y)) ((\a -> (\b -> a*b)) 2) =
(\x -> (\y z -> y)) (\b -> 2*b) =
   -- \x -> ... given anything, returns a function \y z -> ...
(\y z -> y)

so you get:

(\y -> (\z -> y)) 3 4 5 =
   -- \y -> ... given anything, returns a function \z -> ...
(\z -> 3) 4 5 =
   -- \z -> ... given anything, returns a constant 3
3 5  -- now still trying to apply 5 to 3

It is attempting to treat 3 as a function that can take 5.

Answer 3

Combinator . is a function composition operator. Let's examine its type:

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

So it takes the result of the second function and passes it to the first function.

In your example, the important thing to consider is that we can view * as a single-argmuent function whose result is a function:

(*) :: Num a => a -> (a -> a)

It takes a number and returns a function that multiplies its argument by the number. (This approach is called Currying). The type operator -> associates to the right, so the parentheses are optional - its just in our minds, if we view (*) as a two-argument function returning a number or a one-argument function returning another function.

This helps us view what (*) . succ does: It increments its argument (which must be Enum), and then converts it into a function that multiplies its argument by the number (so the argument must also be Num). The result is then

(*) . succ :: (Enum a, Num a) => a -> (a -> a)

Again, we can view it as a one-argument function, or more conveniently two-argument function: It increments its first argument and multiplies it with the second.

Answer 4

When you compose (\x y z -> x) . (\a b -> a*b) you compose functions of the following signatures:

(\x y z -> x) :: a -> b -> c -> a
(\a b -> a*b) :: Num a => a -> a -> a

The signature of (.) is

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

Now, let's put things together to get a specialized version of signature of (.) for those functions.

1. First we specialize the (b -> c) part of (.) signature to a -> b -> c -> a:

   (b -> (z -> x -> b)) -> (a -> b) -> a -> (z -> x -> b)
   

   Get it? The c becomes (z -> x -> b).

2. Now let's specialize the (a -> b) part of (.) signature to a -> a -> a:

   ((a -> a) -> (z -> x -> (a -> a))) -> (a -> (a -> a)) -> a -> (z -> x -> (a -> a))
   

   The b becomes (a -> a).

3. Now let's drop the redundant braces:

   ((a -> a) -> z -> x -> a -> a) -> (a -> a -> a) -> a -> z -> x -> a -> a
   

4. Now here's a session from ghci showing how the signature changes while I consequently apply all the arguments to a function of that signature:

   > let f = undefined :: ((a -> a) -> z -> x -> a -> a) -> (a -> a -> a) -> a -> z -> x -> a -> a
   > :t f (\x y z -> x)
   f (\x y z -> x) :: (a -> a -> a) -> a -> z -> x -> a -> a
   > :t f (\x y z -> x) (\a b -> a*b)
   f (\x y z -> x) (\a b -> a*b) :: Num a => a -> z -> x -> a -> a
   > :t f (\x y z -> x) (\a b -> a*b) 2
   f (\x y z -> x) (\a b -> a*b) 2 :: Num a => z -> x -> a -> a
   > :t f (\x y z -> x) (\a b -> a*b) 2 3
   f (\x y z -> x) (\a b -> a*b) 2 3 :: Num a => x -> a -> a
   > :t f (\x y z -> x) (\a b -> a*b) 2 3 4
   f (\x y z -> x) (\a b -> a*b) 2 3 4 :: Num a => a -> a
   > :t f (\x y z -> x) (\a b -> a*b) 2 3 4 5
   f (\x y z -> x) (\a b -> a*b) 2 3 4 5 :: Num a => a    
   

The above explains how ( (\x y z -> x).(\a b -> a*b) ) 2 3 4 5 works.

Now here's how ( (\x y z -> y).(\a b -> a*b) ) 2 3 4 5 translates:

((a -> a) -> z -> x -> z) -> (a -> a -> a) -> a -> z -> x -> z

And here are the session results:

> let f = undefined :: ((a -> a) -> z -> x -> z) -> (a -> a -> a) -> a -> z -> x -> z
> :t f (\x y z -> x)
f (\x y z -> x) :: (a -> a -> a) -> a -> (a -> a) -> x -> a -> a
> :t f (\x y z -> x) (\a b -> a*b)
f (\x y z -> x) (\a b -> a*b)
  :: Num a => a -> (a -> a) -> x -> a -> a
> :t f (\x y z -> x) (\a b -> a*b) 2
f (\x y z -> x) (\a b -> a*b) 2 :: Num a => (a -> a) -> x -> a -> a
> :t f (\x y z -> x) (\a b -> a*b) 2 3
f (\x y z -> x) (\a b -> a*b) 2 3
  :: (Num a, Num (a -> a)) => x -> a -> a

The last line explains your error message. There obviously can't be any Num instance for a -> a.

Answer 5

Work it out this way:

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

Then replace f with (*), g with succ and x and y with their values:

((*) . succ) 3 4 = (*) (succ 3) 4
                 = (*) 4 4
                 = 16