What is a function composition algorithm that will

问题:

For example, suppose we had the functions double(x) = 2 * x, square(x) = x ^ 2 and sum(x,y) = x + y. What is a function compose such as compose(compose(sum, square), double) = x^2 + 2*x? Notice that I'm asking a function that can be used for functions of any arity. For example, you could compose f(x,y,z) with g(x), h(x), i(x) into f(g(x), h(x), i(x)).

回答1:

This is a common Haskell idiom, applicative functors:

composed = f <$> g1 <*> g2 <*> ... <*> gn

(A nicer introduction can be found here).

This looks very clean because of automatic partial application, and works like this:

(<*>) f g x = f x (g x)
(<$>) f g x = f (g x) -- same as (.)

For example,

f <$> g <*> h <*> i ==>
(\x -> f (g x)) <*> h <*> i ==>
(\y -> (\x -> f (g x)) y (h y)) <*> i ==>
(\y -> f (g y) (h y)) <*> i ==>
(\z -> (\y -> f (g y) (h y)) z (i z)) ==>
(\z -> f (g z) (h z) (i z)).

Applicative functors are more general, though. They are not an "algorithm", but a concept. You could also do the same on a tree, for example (if properly defined):

(+) <$> (Node (Leaf 1) (Leaf 2)) <*> (Node (Leaf 3) (Leaf 4)) ==>
Node (Leaf 4) (Leaf 6)

But I doubt that applicatives are really usable in most other languages, due to the lack of easy partial application.