In this post we’ll deal only with finite lists. Questions regarding partial and infinite lists are left as an exercise for the reader.

Sometimes we have to answer questions like: I have something that looks like a functional equation, but I miss a function – how do I find it? To be more concrete, given the functions f,g,h, how do I find the function r in the equation: f.g = h.r? The purpose of this post is to show you how to find a function in a specific example and, after you found it, to proove that the functional equation holds.

Problem: Given the following equation: reverse . concat = concat . reverse . h, find the function h.

Part 1. First of all, we’ll start with the definitions of the functions concat and reverse.

concat is a function that takes a list of lists and concatenates the innermost lists into a single one.

Example: concat [ [1,2] , [3,4] ] = [1,2,3,4].

Definition of concat:

concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss

reverse is a function that takes a list and returns a list with the original elements read from end to beginning.

Example: reverse [1,2,3,4] = [4,3,2,1]

Definition of reverse:

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

Exercise: Proove that reverse (reverse xs) = xs, for all finite lists xs (in other words, we say that reverse is an involution).

Back to our problem, we want to find the function h that satisfies the functional equation reverse . concat = concat . reverse . h. Because reverse is an involution, we can simplify our equation by a standard technique – compose it on the left with reverse:

reverse . (reverse . concat) = reverse . (concat . reverse . h)

Because composing is associative, we have that:

(reverse . reverse) . concat = reverse . (concat . reverse . h)

Because reverse . reverse = Id (reverse is an involution), we derive that:

concat = reverse . (concat . reverse . h) (E1), which is much more amenable to manipulations than the initial equation, because the left-hand side has been reduced to a single function – concat.

Let’s simplify the problem a little and say we’re dealing with a finite list with 2 elements: L = [ [a1,a2] , [a3,a4] ]. Applying the equation E1 on L, we have:

concat L = reverse(concat(reverse( h L ))) (E2)

E2 is a very important equation, because it gives us a lot of information about the type of h.

Remark 1. h needs to work on L, which is a list of lists, so the domain of h is [[a]], for a fixed type ‘a’.

Remark 2. reverse(h L) in equation E2 says the function reverse needs to work on the values of function h. But reverse is a function that works on lists, so the value (h L) must be a list! In that way, we found that (h L) :: [b], for a fixed type b. So, the codomain of the function h is [b], for a fixed type b.

Conclusion 1: From remarks 1 and 2, we conclude that h :: [[a]] -> [b], for fixed types a and b.

As we said, h(L) :: [b]. We can write h(L) = [b1, b2, …, bm]. Equation E2 becomes:

concat L = reverse(concat(reverse [b1,…,bm]))

= {definition of reverse}
reverse(concat [bm,…,b1] ) (1)

But concat L = concat [ [a1,a2] , [a3, a4]] = [a1,a2,a3,a4]. Using the derived equation (1), we deduce that:

[a1,a2,a3,a4] = reverse(concat [bm,…,b1]) (E3)

Remark 3. In the right-hand side of E3, we have the expression concat [bm,…,b1], and knowing that concat works on lists of lists, we deduce that bm,…,b1 are also lists.

Remark 3 helps us to write bm,…,b1 as lists in the following way:

bm = [cm_1,cm_2,…., cm_im], … , b1 = [c1_1, c1_2, … , c1_i1].

In this way, concat [bm,…,b1] = [cm_1,cm_2, … , cm_im, … , c1_1, c1_2, … , c1_i1] (2)

Coming back to the equation E2, we’ll have (together with (2)):

[a1,a2,a3,a4] = reverse [cm_1,cm_2, … , cm_im, … , c1_1, c1_2, … , c1_i1]

= {definition of reverse}
[c1_i1, … , c1_1, …, cm_im, …, cm_1]

So, we have now that:

[a1,a2,a3,a4] = [c1_i1, … c1_2, c1_1, …, cm_im, …cm_2, cm_1] (E4)

Becuase in the left-hand side of the equation E4 we have only 4 elements, it’s clear that in the right-hand side we also have only 4 elements. We’ll pick two elements from b1 and two elements from b2, and see what happens next:

[a1,a2,a3,a4] = [c1_2,c1_1,c2_2,c2_1]

It’s clear now how to pick: c1_2 = a1; c1_1 = a2; c2_2 = a3; c2_1 = a4.

So we’re left only with b1 = [c1_1,c1_2] = [a2,a1] and b2 = [c2_1,c2_2] = [a4,a3].

We first introduced h(L) = [b1,…,bm], which becomes now:

h(L) = h [ [a1,a2], [a3,a4] ] = [b1,b2] = [ [a2,a1], [a4,a3] ] = [reverse [a1,a2], reverse [a3,a4]] = map reverse [[a1,a2], [a3,a4]] = map reverse L

This derivation says that h = map reverse, and we’ve found the function needed.

The equation in the problem becomes: reverse . concat = concat . reverse . map reverse

But we’ve been overspecific by now, working on a list of lists of 2 elements each. Is the equation found holding on all finite lists? The answer is yes, and we’ll proove:

Proposition (P): reverse . concat = concat . reverse . map reverse, for all finite lists.1

End of Part 1.

Part 2.

Prove that:

Proposition (P): reverse . concat = concat . reverse . map reverse, for all finite lists.1

We can proove this equation using induction, but the scope of this post is to introduce some advanced techniques that you’ll need in your future projects. For that, we’ll start with a little theory.

First of all, all the functions used in the proposition P can be rewritten using foldr. We’ll let the proofs as an exercise.

concat = foldr (++) []  

Also, we need to know a very important theorem, which is demonstrated in [1].

The fusion theorem.
Given a function f and a function h with the following conditions:

  1. f is a strict function.
  2. f(g x y) = h x (f y), for all x,y of appropriate types.

Let b = f a.

Then f . foldr g a = foldr h b.
End of fusion theorem.

The fusion theorem says that, in certain conditions, a function composed with a foldr is also a foldr. This theorem will be used to simplify a lot of equations in our exercise.

Now we’re ready to give the proof of our proposition, which is reminded below:

reverse . concat = concat . reverse . map reverse, for all finite lists

We’ll prove that in the following way:

  1. Express the left-hand side as a foldr.
  2. Express the right-hand side as a foldr.
  3. Compare the definitions to see that are equal.

1. Express the left-hand side as a foldr.

reverse . concat

= { because, as we said, concat = foldr (++) [] }

reverse . foldr (++) []

We have a composition of reverse with a foldr function, so the only thing we can think of is to try applying the fusion theorem:

reverse . foldr (++) [] = foldr h b.

  1. First of all, the first condition of the theorem is satisfied – reverse is a strict function.
  2. reverse ((++) xs ys) = h xs (reverse ys)

reverse ((++) xs ys)

= { infix notation for (++) }

reverse (xs ++ ys)

= { this can be easily proved }

reverse ys ++ reverse xs

We have in this way that:

reverse ys ++ reverse xs = h xs (reverse ys)

We define h to work generally like this:

h xs zs = zs ++ reverse xs, and we’re done, we’ve found the desired function h for the fusion theorem. The technique is simple: we just generalized reverse ys (present in left side and right side of the equation) to a fresh variable named zs.

The theorem states also that b = reverse [] = []. So b = [].

We’ve found our equation:

reverse . concat = reverse . foldr (++) [] = foldr h [], where h xs zs = zs ++ reverse xs. (R1)

End – express the left-hand side as a foldr.

2. Express the righ-hand side as a foldr (concat . reverse . map reverse)

We’ll use the following result, which is left also as an exercise to the reader: map f = foldr ((:) . f) [] (where ‘:’ is the lists operator).

Using the map rewriting as a foldr, we’ll have:

concat . reverse . map reverse

= { function composition is associative }

concat . (reverse . map reverse)

= { map f function as a foldr }

concat . (reverse . foldr ((:) . reverse) [] )

We apply now the fusion theorem for the composition:

reverse . foldr ((:) . reverse) [] = foldr h b.

It’s clear that reverse is a strict function.

Also, b = reverse [] = []. So b = [].

The second condition of the theorem becomes (instantiated in our case):

reverse ((:) . reverse xs yss) = h xs (reverse yss) (1)

reverse ((:). reverse xs yss)

= { function composition }

reverse ((:)(reverse xs) (yss) )

= { infix notation of (:) }

reverse(reverse xs : yss)

= { reverse definition, equation 2 }

reverse yss ++ [reverse xs]

This derivation, together with (1), gives us:
reverse yss ++ [reverse xs] = h xs (reverse yss)

Generalizing reverse yss (found in both sides of the equation) to the fresh variable zss, we have found our function h:

h xs zss = zss ++ [reverse xs].

Applying the fusion theorem, we have that:

reverse . foldr ((:) . reverse) [] = foldr h [], where the function h is:

h xs zss = zss ++ [reverse xs]

I’ll rewrite the function h above as h1, in order to not confuse notations in the following argument.

We have so the original equation, which became:

concat . reverse . map reverse = concat . foldr h1 [], where h1 xs zss = zss ++ [reverse xs].

We’ll try to apply again the fusion theorem and to write:

concat . foldr h1 [] = foldr h b.

We know that concat is a strict function, so the first condition of the theorem applies.

Let b = concat [] = []. So b = [].

concat (h1 xs zss) = h xs (concat zss) (2)

concat (h1 xs zss) 

= { definition of h1}

concat(zss ++ [reverse xs])

= {simple to proove: concat (xss ++ zss) = concat xss ++ concat zss}

concat zss ++ concat [reverse xs]

= { it’s trivial to see that concat [xs] = xs}

concat zss ++ reverse xs

From this derivation and equation (2), we conclude that:

h xs (concat zss) = concat zss ++ reverse xs

Generalizing concat zss into the fresh variable ys, we have that:

h xs ys = ys ++ reverse xs

In this way, we have that concat . foldr h1 [] = foldr h [], where h xs ys = ys ++ reverse xs.

We have completed, in this way, the right-hand side of the original equation:

concat . reverse . map reverse = foldr h [], where h xs ys = ys ++ reverse xs. (R2)

But we also have the result obtained for the left-hand side:

reverse . concat = foldr h [], where h xs zs = zs ++ reverse xs (R3)

3. Comparing R2 and R3, it’s clear that are equal. So the proposition holds:

reverse . concat = concat . reverse . map reverse

End of Part 2.

I know the exercise is a bit long and technical, but in this way we’ve shown some powerful techniques for finding functions with some properties given and for proving equations using the fusion theorem of foldr. This are mathematical tools that you can use for optimizing equations, for prooving and even for constructing new functions as folds (see more about it in [2]).

If you see some error in my calculations, I’m more than happy to listen your opinion.

You can also take a look on my page on Patreon (click this text).

References

[1]. Bird,R. (2015) Thinking Functionally with Haskell. Cambridge University Press.
[2]. Hutton,G. (1999) A tutorial on the universality and expressiveness of fold. J. Functional Programming.

Constantin Liculescu

Facebook 

Share Button