Composing a chain of 2-argument functions

Question

So I have a list of a functions of two arguments of the type [a -> a -> a]

I want to write a function which will take the list and compose them into a chain of functions which takes length+1 arguments composed on the left. For example if I have [f,g,h] all of types [a -> a -> a] I need to write a function which gives:

chain [f,g,h] = \a b c d -> f ( g ( h a b ) c ) d

Also if it helps, the functions are commutative in their arguments ( i.e. f x y = f y x for all x y ).

I can do this inside of a list comprehension given that I know the the number of functions in question, it would be almost exactly like the definition. It's the stretch from a fixed number of functions to a dynamic number that has me stumped.

This is what I have so far:

f xs = f' xs
    where
        f' []   = id
        f' (x:xs) = \z -> x (f' xs) z

I think the logic is along the right path, it just doesn't type-check.

Thanks in advance!

Answer 1

The comment from n.m. is correct--this can't be done in any conventional way, because the result's type depends on the length of the input list. You need a much fancier type system to make that work. You could compromise in Haskell by using a list that encodes its length in the type, but that's painful and awkward.

Instead, since your arguments are all of the same type, you'd be much better served by creating a function that takes a list of values instead of multiple arguments. So the type you want is something like this: chain :: [a -> a -> a] -> [a] -> a

There are several ways to write such a function. Conceptually you want to start from the front of the argument list and the end of the function list, then apply the first function to the first argument to get something of type a -> a. From there, apply that function to the next argument, then apply the next function to the result, removing one element from each list and giving you a new function of type a -> a.

You'll need to handle the case where the list lengths don't match up correctly, as well. There's no way around that, other than the aforementioned type-encoded-lengths and the hassle associate with such.

Answer 2

I wonder, whether your "have a list of a functions" requirement is a real requirement or a workaround? I was faced with the same problem, but in my case set of functions was small and known at compile time. To be more precise, my task was to zip 4 lists with xor. And all I wanted is a compact notation to compose 3 binary functions. What I used is a small helper:

-- Binary Function Chain
bfc :: (c -> d) -> (a -> b -> c) -> a -> b -> d
bfc f g = \a b -> f (g a b)

For example:

ghci> ((+) `bfc` (*)) 5 3 2 -- (5 * 3) + 2
17
ghci> ((+) `bfc` (*) `bfc` (-)) 5 3 2 1 -- ((5 - 3) * 2) + 1
5
ghci> zipWith3 ((+) `bfc` (+)) [1,2] [3,4] [5,6]
[9,12]
ghci> getZipList $ (xor `bfc` xor `bfc` xor) <$> ZipList [1,2] <*> ZipList [3,4] <*> ZipList [5,6] <*> ZipList [7,8]
[0,8]

That doesn't answers the original question as it is, but hope still can be helpful since it covers pretty much what question subject line is about.