This problem comes from the reddit haskell question here: Haskell question regarding foldr

The exercise can be stated like this: given a list of functions (with appropriate types), construct the composition of the functions from that list using a foldr.

The strategy to follow for this problem (and for others that request to write a function in a foldr form) is the following:

1. Write the function in a more mathematical notation (in order to be easier to manipulate it).
2. Derive a recursive version of the function.
3. Use the foldr universality property for the recursive definition and derive the foldr version of it.

So let’s see how we concretely apply these steps to our problem.

Step 1. A more mathematical specification of our problem can be done like this:

compFuncs [f1,f2,…,fn] = f1 o f2 . … . o fn (where o is the symbol for function composition)

In this moment we’re not interested in which is the definition for compFuncs [], because that will be given in the step 2.


 

Step 2. Let’s derive a recursive definition for our function.

compFuncs [f1,f2,…,fn]

=(by definition)
f1 o f2 . … . o fn

=(functions composition is associative)
f1 o (f2 o … o fn)

=(by definition, f2 o … o fn = compFuncs [f2,…,fn])
f1 o compFuncs [f2,…,fn]

So what we have by now is: compFuncs [f1,f2,…,fn] = f1 o compFuncs [f2,…,fn] (1)

To convert it in a Haskell form, let’s do some notations:

  • o is denoted in Haskell by dot: .
  • the list [f1,f2, … , fn] can be split into the head f1 and the tail [f2,…,fn]; we write the tail as fs = [f2,…,fn]

With these notations, we rewrite the relation (1) into:

compFuncs (f1:fs) = f1 o compFuncs fs, or equivalently (because I don’t like f1, I’ll write it as f):

compFuncs (f:fs) = f . compFuncs fs (2)

The only problem that remains is which form has compFuncs []. For that, let’s see how the function works:

f1 o f2 o … o fn

=(by definition)
compFuncs f1:[f2, … ,fn]
=(using the relation 1)
f1 o compFuncs [f2, … , fn]
=(using the relation 1)
f1 o (f2 o compFuncs [f3, … , fn])
=

=
f1 o f2 o … o fn o (compFuncs [])

 

So we have that f1 o f2 o … o fn = f1 o f2 o … o fn o (compFuncs [])We know that the identity function (id x = x) has the property that f o id = f for all functions f, so the obvious choice here is compFuncs [] = id (3)

Using the equalities (2) and (3), we obtain the recursive definition of compFuncs:

compFuncs [] = id
compFuncs (f:fs) = f . compFuncs fs 


Step 3. Convert the recursive definition into a foldr.

In this moment we’ll use the foldr universality property (you can read it in detail in [1])

Theorem (foldr universality property):

    g = foldr h v
      <=>
    g [] = v 
    g (x : xs) = h x (g xs)

 

So let’s apply this to our recursive definition.

compFuncs = foldr h v

=>

The first equation of the theorem:

compFuncs [] = v, but from our recursive deiniftion we know that  compFuncs [] = id, so v = id (A)

The second equation of the theorem:

compFuncs (f:fs) = h f (compFuncs fs)

So our task here is to find the function h.

We know from the recursive definition that compFuncs (f:fs) = f o compFuncs fs, so we have:

compFuncs (f:fs) = f o compFuncs fs =  h f (compFuncs fs)

Now let’s focus on the bolded part: f o compFuncs fs =  h f (compFuncs fs)

We notice that compFuncs fs appears in the left and right parts of the equation, and because h must work in all cases, we can bring in a fresh variable r = compFuncs fs; so, h becomes: f o r = h f r.

So with h f r = f o r , the second equation of the theorem is satisfied.

Let’s write the composition with dot notation, like in Haskell: h f r= f . r (B)

Putting together the equalities (A)and (B), we transformed compFuncs into a foldr:

 


[1] Hutton, Graham (1999). A tutorial on the universality and expressiveness of fold. Journal of Functional Programming. Cambridge University Press.

 

Constantin Liculescu

Facebook 

Share Button