outer product -> partially applied functions -> composition

Question

I have a list of binary functions such that (a -> b -> a) and a list of items [b]. I need to produce a transformation (a -> a) as follows. For each of the bs I need to partially apply the functions and produce their composition, which gives me a list of unary functions the same length as the bs. Call each of these compositions a processor; I next need to compose the processors. So for example, if I have functions [f0,f1] and items [b0,b1], I need the function (f1 b1) . (f0 b1) . (f1 b0) . (f0 b0). I can see that I'm folding across the bs, but this also looks like a composition of an outer product. So, does Haskell offer a clever way to produce this with some kind of outer product? (Order matters, of course.) If so, please explain in terms understandable to a complete novice.

Answer 1

You can use <**> (which is located in Control.Applicative) and fold the result:

combine :: [(a -> b -> a)] -> [b] -> (a -> a)
combine fs bs = foldr (flip (.)) id $ bs <**> (map flip fs)

Let's have a look at the components:

map flip fs

This just flips the functions from a -> b -> a to b -> a -> a so we can ap them later on.

bs <**> (map flip fs)
-- ex: [b0, b1] <**> [f0, f1] == [f0 b0, f1 b0, f0 b1, f1 b1]

This function partially applys all the bs to the fs and puts them in a list. All we have to do now is to fold the result using the composition operator ((.)). Note that using flip (.) we reverse order of composition since the list generated by <**> is the reverse of what we want:

foldr (flip (.)) id $ it -- alternatively foldr1
-- ex: foldr (flip (.)) id [f0 b0, f1 b0, f0 b1, f1 b1] ==
--     (f1 b1) . (f0 b1) . (f1 b0) . (f0 b0)

Answer 2

See ThreeFx's answer for a solution using only standard functions.

---

You also need to fold the list of partially applied functions itself with (.).

First, get your list of partially applied functions:

-- If f :: a -> b -> a, then (`f` b) :: a -> a
[ (`f` b) | b <- [b0, b1], f <- [f0, f1] ]
-- Result: [(`f0` b0), (`f1` b0), (`f0` b1), (`f1` b1)]

(It would be nice to use fs <*> bs but you need to partially apply f to its second argument, not first, and the resulting list would have the wrong order for the composition step.)

Next, fold that list with (.). I can never quite remember which fold to use (or how to use it to ensure the correct ordering you need), so here is a custom recursive function that I know does the right thing:

composeAll :: [(a -> a)]
composeAll [] = id
composeAll (f:fs) = composeAll fs . f

Putting it all together:

fs = [f0, f1, f2]
bs = [b0, b1, b2]
f = composeAll [(`f` b) | b <- bs, f <- fs]