Haskell function composition operator of type (c→d) → (a→b→c) → (a→b→d)

Ordinary function composition is 开发者_C百科of the type

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

I figure this should generalize to types like:

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

A concrete example: calculating difference-squared. We could write diffsq a b = (a - b) ^ 2, but it feels like I should be able to compose the (-) and (^2) to write something like diffsq = (^2) . (-).

I can't, of course. One thing I can do is use a tuple instead of two arguments to (-), by transforming it with uncurry, but this isn't the same.

Is it possible to do what I want? If not, what am I misunderstanding that makes me think it should be possible?

---

Note: This has effectively already been asked here, but the answer (that I suspect must exist) was not given.

---

My preferred implementation for this is

fmap . fmap :: (Functor f, Functor f1) => (a -> b) -> f (f1 a) -> f (f1 b)

If only because it is fairly easy to remember.

When instantiating f and f1 to (->) c and (->) d respectively you get the type

(a -> b) -> (c -> d -> a) -> c -> d -> b

which is the type of

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

but it is a bit easier to rattle off the fmap . fmap version and it generalizes to other functors.

Sometimes this is written fmap fmap fmap, but written as fmap . fmap it can be more readily expanded to allow more arguments.

fmap . fmap . fmap 
:: (Functor f, Functor g, Functor h) => (a -> b) -> f (g (h a)) -> f (g (h b))

fmap . fmap . fmap . fmap 
:: (Functor f, Functor g, Functor h, Functor i) => (a -> b) -> f (g (h (i a))) -> f (g (h (i b))

etc.

In general fmap composed with itself n times can be used to fmap n levels deep!

And since functions form a Functor, this provides plumbing for n arguments.

For more information, see Conal Elliott's Semantic Editor Combinators.

---

The misunderstanding is that you think of a function of type a -> b -> c as a function of two arguments with return type c, whereas it is in fact a function of one argument with return type b -> c because the function type associates to the right (i.e. it's the same as a -> (b -> c). This makes it impossible to use the standard function composition operator.

To see why, try applying the (.) operator which is of type (y -> z) -> (x -> y) -> (x -> z) operator to two functions, g :: c -> d and f :: a -> (b -> c). This means that we must unify y with c and also with b -> c. This doesn't make much sense. How can y be both c and a function returning c? That would have to be an infinite type. So this does not work.

Just because we can't use the standard composition operator, it doesn't stop us from defining our own.

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

 diffsq = (^2) `compose2` (-)

Usually it is better to avoid using point-free style in this case and just go with

 diffsq a b = (a-b)^2

---

I don't know of a standard library function that does this, but the point-free pattern that accomplishes it is to compose the composition function:

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

---

I was going to write this in a comment, but it's a little long, and it draws from both mightybyte and hammar.

I suggest we standardize around operators such as .* for compose2 and .** for compose3. Using mightybyte's definition:

(.*) :: (c -> d) -> (a -> b -> c) -> (a -> b -> d)
(.*) = (.) . (.)

(.**) :: (d -> e) -> (a -> b -> c -> d) -> (a -> b -> c -> e)
(.**) = (.) . (.*)

diffsq :: (Num a) => a -> a -> a
diffsq = (^2) .* (-)

modminus :: (Integral a) => a -> a -> a -> a
modminus n = (`mod` n) .* (-)

diffsqmod :: (Integral a) => a -> a -> a -> a
diffsqmod = (^2) .** modminus

Yes, modminus and diffsqmod are very random and worthless functions, but they were quick and show the point. Notice how eerily easy it is to define the next level by composing in another compose function (similar to the chaining fmaps mentioned by Edward).

(.***) = (.) . (.**)

On a practical note, from compose12 upwards it is shorter to write the function name rather than the operator

f .*********** g
f `compose12` g

Though counting asterisks is tiring so we may want to stop the convention at 4 or 5 .

---

[edit] Another random idea, we could use .: for compose2, .:. for compose3, .:: for compose4, .::. for compose5, .::: for compose6, letting the number of dots (after the initial one) visually mark how many arguments to drill down. I think I like the stars better though.

---

As Max pointed out in a comment:

diffsq = ((^ 2) .) . (-)

You can think of f . g as applying one argument to g, then passing the result to f. (f .) . g applies two arguments to g, then passes the result to f. ((f .) .) . g applies three arguments to g, and so on.

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

If we left-section the composition operator with some function f :: c -> d (partial application with f on the left), we get:

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

So we have this new function which expects a function from b -> c, but our g is a -> b -> c, or equivalently, a -> (b -> c). We need to apply an a before we can get what we need. Well, let's iterate once more:

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

---

Here's what I think is an elegant way to achieve what you want. The Functor type class gives a way to 'push' a function down into a container so you can apply it to each element using fmap. You can think of a function a -> b as a container of bs with each element indexed by an element of a. So it's natural to make this instance:

instance Functor ((->) a) where
  fmap f g = f . g

(I think you can get that by importing a suitable library but I can't remember which.)

Now the usual composition of f with g is trivially an fmap:

o1 :: (c -> d) -> (b -> c) -> (b -> d)
f `o1` g = fmap f g

A function of type a -> b -> c is a container of containers of elements of type c. So we just need to push our function f down twice. Here you go:

o2 :: (c -> d) -> (a -> (b -> c)) -> a -> (b -> d)
f `o2` g = fmap (fmap f) g

In practice you might find you don't need o1 or o2, just fmap. And if you can find the library whose location I've forgotten, you may find you can just use fmap without writ ing any additional code.