The composition of functions in a list of functions!

Question

I need to define a function 'Compose' which takes a list 'L' which is a list of functions. When I specify a parameter that will suit all the functions in the list, the last function evaluates itself using this param. The result is then passed to the second last function and so on until we get to the first item (function) in the list and we get the final result.

E.g.

Compose ( ( fn N -> N + 1 ) ^ ( fn N -> 2 * N ) ^ # ) 3 .

give the answer 7.

I have to write this in a functional programming language called SAL (simple applicative language) devised by a lecturer in my college (hence funny syntax above ( ^ seperates list items and # marks end of list)).

If any solutions could be written in pseudo-code bearing in mind I can't use loops, variables etc. that would be much appreciated. Apparently the solution is a one-line answer. I imagine it involves recursion (99% of our task functions do!).

Also I don't understand Haskell (guess I'll have to learn!) so psuedo code or even plain English would be great. –

Thanks a bunch.

Answer 1

If the solution is a one-line answer, it could be something involving a fold:

compose :: [a -> a] -> a -> a
compose fs v = foldl (flip (.)) id fs $ v

http://haskell.org/haskellwiki/Compose

You can also implement it as a right fold, which works the way you want:

compose = foldr (.) id

*Main> let compose = foldr (.) id
*Main> compose [\x -> x+1, \x -> 2 * x, id] 3
7