user2666425
user2666425

Reputation: 1691

What is happening when I compose * with + in Haskell?

I'm trying to understand the result of

(*) . (+) 

in Haskell. I know that the composition operator is just the standard composition of mathematical functions- so

(f . g) = f (g x)

But:

(*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a

I'm struggling to understand this type signature. I would have expected to be able to do things like:

((*) . (+)) 1 2 :: Num a => a -> a
= (* (+ 1 2))

What is the meaning of (*) . (+)'s type signature? I tried playing with it by something like (just matching up with its signature):

((*) . (+)) 1 (\x -> x + 1) 1

But that fails to compile. I'm trying to walk through the logical steps when composing these, but I'm not fully understanding how it's getting to this result (and what the result is).

Upvotes: 45

Views: 1710

Answers (5)

Aadit M Shah
Aadit M Shah

Reputation: 74244

I understand how you feel. I found function composition to be quite difficult to grasp at first too. What helped me grok the matter were type signatures. Consider:

(*) :: Num x => x -> x -> x
(+) :: Num y => y -> y -> y
(.) :: (b -> c) -> (a -> b) -> a -> c

Now when you write (*) . (+) it is actually the same as (.) (*) (+) (i.e. (*) is the first argument to (.) and (+) is the second argument to (.)):

(.) :: (b -> c) -> (a -> b) -> a -> c
       |______|    |______|
           |           |
          (*)         (+)

Hence the type signature of (*) (i.e. Num x => x -> x -> x) unifies with b -> c:

(*) :: Num x => x -> x -> x -- remember that `x ->  x -> x`
                |    |____| -- is implicitly `x -> (x -> x)`
                |       |
                b ->    c

(.) (*) ::          (a -> b) -> a ->    c
                          |             |
                          |          |‾‾‾‾|
           Num x =>       x          x -> x

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

Hence the type signature of (+) (i.e. Num y => y -> y -> y) unifies with Num x => a -> x:

(+) :: Num y => y -> y -> y -- remember that `y ->  y -> y`
                |    |____| -- is implicitly `y -> (y -> y)`
                |       |
       Num x => a ->    x

(.) (*) (+) ::  Num x                => a ->     x    ->    x
                                        |        |          |
                                        |     |‾‾‾‾|     |‾‾‾‾|
                              Num y  => y     y -> y     y -> y

(.) (*) (+) :: (Num (y -> y), Num y) => y -> (y -> y) -> y -> y

I hope that clarifies where the Num (y -> y) and Num y come from. You are left with a very weird function of the type (Num (y -> y), Num y) => y -> (y -> y) -> y -> y.

What makes it so weird is that it expects both y and y -> y to be instances of Num. It's understandable that y should be an instance of Num, but how y -> y? Making y -> y an instance of Num seems illogical. That can't be correct.

However, it makes sense when you look at what function composition actually does:

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

((*) . (+)) = \z -> (*) ((+) z)

So you have a function \z -> (*) ((+) z). Hence z must clearly be an instance of Num because (+) is applied to it. Thus the type of \z -> (*) ((+) z) is Num t => t -> ... where ... is the type of (*) ((+) z), which we will find out in a moment.

Therefore ((+) z) is of the type Num t => t -> t because it requires one more number. However, before it is applied to another number, (*) is applied to it.

Hence (*) expects ((+) z) to be an instance of Num, which is why t -> t is expected to be an instance of Num. Thus the ... is replaced by (t -> t) -> t -> t and the constraint Num (t -> t) is added, resulting in the type (Num (t -> t), Num t) => t -> (t -> t) -> t -> t.

The way you really want to combine (*) and (+) is using (.:):

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

Hence (*) .: (+) is the same as \x y -> (*) ((+) x y). Now two arguments are given to (+) ensuring that ((+) x y) is indeed just Num t => t and not Num t => t -> t.

Hence ((*) .: (+)) 2 3 5 is (*) ((+) 2 3) 5 which is (*) 5 5 which is 25, which I believe is what you want.

Note that f .: g can also be written as (f .) . g, and (.:) can also be defined as (.:) = (.) . (.). You can read more about it here:

What does (f .) . g mean in Haskell?

Upvotes: 67

Carsten S
Carsten S

Reputation: 205

There are good answers here, but let me quickly point out a few steps where you went wrong.

First, the correct definition of function composition is

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

you omitted the x on the LHS. Next, you should remember that in Haskell h x y is the same as (h x) y. So, contrary to what you expected,

((*) . (+)) 1 2 = (((*) . (+)) 1) 2 = ((*) ((+) 1)) 2 = ((+) 1) * 2,

and now you see why that fails. Also,

((*) . (+)) 1 (\x -> x + 1) 1

does not work, because the constraint Num (Int -> Int) is not satisfied.

Upvotes: 2

Syd Kerckhove
Syd Kerckhove

Reputation: 833

(*) and (+) both have the type signature Num a => a -> a -> a Now, if you compose them, you get something funky.

(*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a

That's because (*) and (+) are expecting two 'arguments'.

(+) with one argument gets you a function. The . operator expects that function (the a -> a that you see).

Here's the meaning of (*) . (+)

                                       x     f          y
 (*) . (+) :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a

(*) . (+) maps x f y to ((x +) * f) y where f is a function from a to a that is ALSO a number. The reason (*) expects a function is to make the types match while it expects two arguments, but that function has to be a number because (*) only works on numbers.

Really, this function makes no sense at all.

Upvotes: 9

effectfully
effectfully

Reputation: 12735

Some extensions first:

{-# LANGUAGE FlexibleContexts, FlexibleInstances, TypeSynonymInstances #-}

As the other answers show, your function is

weird :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a
weird x g = (x +) * g

But this function does have non-weird semantics.

There is a notion of difference lists. Accordingly, there is a notion of difference integers. I've seen them being used only in the dependently typed setting (e.g. here, but that's not the only case). The relevant part of the definition is

instance Enum DiffInt where
    toEnum   n = (n +)
    fromEnum n = n 0

instance Num DiffInt where
    n + m = n . m
    n * m = foldr (+) id $ replicate (fromEnum n) m

This doesn't make much sense in Haskell, but can be useful with dependent types.

Now we can write

test :: DiffInt
test = toEnum 3 * toEnum 4

Or

test :: DiffInt
test = weird 3 (toEnum 4)

In both the cases fromEnum test == 12.

EDIT

It's possible to avoid the using of the TypeSynonymInstances extension:

{-# LANGUAGE FlexibleContexts, FlexibleInstances #-}

weird :: (Num (a -> a), Num a) => a -> (a -> a) -> a -> a
weird x g = (x +) * g

instance (Enum a, Num a) => Enum (a -> a) where
    toEnum   n = (toEnum n +)
    fromEnum n = fromEnum $ n (toEnum 0)

instance (Enum a, Num a) => Num (a -> a) where
    n + m = n . m
    n * m = foldr (+) id $ replicate (fromEnum n) m

type DiffInt = Int -> Int

As before we can write

test' :: DiffInt
test' = weird 3 (toEnum 4)

But now we can also write

-- difference ints over difference ints
type DiffDiffInt = DiffInt -> DiffInt

test'' :: DiffDiffInt
test'' = weird (toEnum 3) (toEnum (toEnum 4))

And

main = print $ fromEnum $ fromEnum test'

prints 12.

EDIT2 Better links added.

Upvotes: 7

thor
thor

Reputation: 22560

Let:

m = (*)
a = (+)

then

(m.a) x = (m (a x)) = m (a x) 

Now m expects a Num a as a parameter, on the other hand (a x) , i.e. (x +) is a unary function (a -> a) by definition of (+). I guess what happened is that GHC tries to unite these two types so that, if you have a type that is both a number and a unary function, m can take a number and a unary function and return a unary function, since they are considered the same type.

As @Syd pointed, this unification wouldn't make sense for any normal number types such as integers and floating point numbers.

Upvotes: 2

Related Questions