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

Answer 2

in haskell:

compose :: a -> [a -> a] -> a
compose a (x:xs) = x (compose a xs)
compose a [] = a

Answer 3

Dan kind of gives it away, but here's a hint on how to do it yourself. You can recurse over numbers:

0! = 1
n! = (n-1)! * n

You can also recurse over structure. A list, for example, has a recursive structure, broken down into two cases: an empty list, and an item followed by the rest of the list. In no particular language:

List :=   Item x List 
        | Nil

Item marks the head of the list, x is the value stored in the head, and List is the tail. In this grammar, your list would be written:

Item ( fn N -> N + 1 ) Item ( fn N -> 2 * N ) Nil

The rule for a list in the syntax your professor invented could be written recursively as:

List :=   x ^ List
        | #

A function on a list must recurse over this structure, which means it handles each of the two cases:

sum l:List = Nil -> 0
           | Item x xs:List = x + sum xs

The recursion, specifically, is the term sum l:List = x + sum xs. Writing this function using the professor's syntax left as an exercise.

In your problem, your metafunction takes a list of functions and must return a function. Consider each case, the empty list and an item (the head) followed by a list (the tail). In the latter case, you can recursively use your function to get a function from the tail, then combine that somehow with the head to return a function. That's the gist, at any rate.

Answer 4

The same using monoids, point-free

import Data.Monoid
compose :: [a -> a] -> a -> a
compose = appEndo . mconcat . map Endo

Or somewhat more generally:

import Data.Monoid
compose :: (Functor t, Foldable t) => t (a -> a) -> a -> a
compose = appEndo . foldl1 (<>) . fmap Endo

Answer 5

Here's what I used:

compose :: [a -> a] -> a -> a
compose list startingvalue = foldl (\x f -> f x) startingvalue list