Since Josh has already mentioned it, I had better give it a full account.

Back in 2003 when I just started my postdoc in PSD Lab in University of Tokyo, my colleagues there were discussing about the third homomorphism theorem. The theorem says that if a function

$f\; =\; foldr\; (\ll )\; e$

f = foldl (≫) e

there exists some associative binary operator

$f\; []\; =\; e$

f [a] = a ≪ e = e ≫ a

f (xs ⧺ ys) = f xs ⊚ f ys

Being a list homomorphism implies the potential of parallel computation.

The paper we studied was, of course, The Thrid Homomorphism Theorem by Jeremy. The aim then was to automatically, or semi-automatically, derive

f = sum , where⊚ can simply be+ .f = sort , where⊚ can be the functionmerge merging two sorted lists.f = scanr ⊛ e . Whilescanr appears to be an inherently sequential function, it is actually possible to computef “from the middle”, provided that⊛ is associative, if we takexs ⊚ (y : ys) = map (⊛y) xs ⧺ (y : ys) .

Can we come up with a method to derive

I myself was not particularly interested in automation. I was interested in the challenge for two reasons. Firstly, it appears that some kind of inverse function is needed. Secondly, when I looked at Jeremy’s proof, I felt there is a relational proof inside waiting to be discovered. So I tried.

### Setting the Stage

For the ease of point-free calculation, we define alternatives of folds where the input is paired with the base-cases:

$foldrp\; (\ll )\; ([],a)\; =\; a$

foldrp (≪) (x:xs,a) = x ≪ foldrp (≪) (xs,a)

foldlp (≫) (a,[]) = a

foldlp (≫) (a, xs⧺[x]) = foldlp (≫) (a,xs) ≫ x

The advantage is that we can shift a suffix or a prefix of the input list to the base case. That is:

$foldr\; (\ll )\; e\; (xs\u29fays)\; =\; foldrp\ll \; (xs,\; foldr\ll \; e\; ys)$

foldl (≫) e (xs⧺ys) = foldlp≪ (foldl ≪ e xs, ys)

or, in point-free style:

$foldr\; (\ll )\; e\; .\; cat\; =\; foldrp\; (\ll )\; .\; (id\; \times \; foldr\; (\ll )\; e)$(1)

foldl (≫) e . cat = foldlp (≫) . (foldlp (≫) e × id) (2)

where

The key property, however, is one that was shown in (possibly among other literature) Algebra of Programming: for a simple relation (i.e. a partial function)

$S\; .\; S\xb0\; .\; S\; =\; S$

where

Recall our aim: given

### Proving the Theorem

The third homomorphism theorem is a direct corollary of the following lemma:

Lemma 1:

f = foldr (≪) e = f = foldl (≫) e implies thatf is prefix and postfix insensitive. That is:$f\; xs\; =\; f\; xs\u2019\; \wedge \; f\; ys\; =\; f\; ys\u2019\; \Rightarrow \; f\; (xs\u29fays)\; =\; f\; (xs\u2019\u29fays\u2019).$In point-free style:

f . cat . (f°. f × f°. f) = f . cat .

Once we have the lemma proved, the theorem follows by taking

The proof of Lemma 1 is simply some applications of (1), (2), and

$f\; .\; cat$

={ (1) }

foldrp (≪) . (id × f)

={ since f . f° . f = f }

foldrp (≪) . (id × f) . (id × f° . f)

={ (1) }

f . cat . (id × f° . f)

={ (2) }

foldlp (≫) . (f × id) . (id × f° . f)

={ since f . f° . f = f }

foldlp (≫) . (f × id) . (f° . f × f° . f)

={ (2) }

f . cat . (f° . f × f° . f)

The proof is still the same as that of Jeremy’s, but in a relational disguise.

### Refining to Functions

To derive actual algorithms, we have yet to refine

For example, consider the special case

For

### Some more Properties

Some more properties are needed to deal with

$foldrp\; (\ll )\; (xs\u29fa[x],a)\; =\; foldrp\; (\ll )\; (xs,\; x\; \ll \; a)$

foldlp (≫) (a, x:xs) = foldlp (≫) (a ≫ x, xs) (3)

When simple approaches of refining

$\u229a\; =\; f\; .\; cat\; .\; (f\xb0\times \; f\xb0)$

={ (1) }

foldrp (≪) . (id × f) . (f°× f°)

⊇{ since f . f° ⊇ ran f }

foldrp (≪) . (f°× ran f)

={ since f = foldl ≫ [] }

foldrp (≪) . ((foldl ≫ [])°× ran f)

Symetrically,

$\u229a\; =\; foldlp\; (\gg )\; .\; (ran\; f\; \times \; (foldr\; \ll \; [])\xb0)$(4)

### Scanr “from the Middle”

Finally, consider

$scanr\; \u229b\; e\; =\; foldr\; \ll \; [e]$

x ≪ (y : xs) = x ⊛ y : y : xs

scanr ⊛ e = foldl ≫ [e]

xs ≫ x = map (⊛x) xs ⧺ [e]

From

$xs\; \u229a\; (x\; :\; y\; :\; ys)$

={ (4) }

foldlp (≫) (xs, (foldr ≪ [e])° (x : y :ys))

={ definition of ≪ , letz ⊛ y = x }

foldlp (≫) (xs, z : (foldr ≪ [e])° (y :ys))

={ (3) }

foldlp (≫) (xs ≫ z, (foldr ≪ [])° (y :ys))

={ (4) }

(xs ≫ z) ⊚ (y : ys)

={ induction }

map (⊛ y) (xs ≫ z) ⧺ ys

={ definition of ≫ }

map (⊛ y) (map (⊛ z) xs ⧺ [e]) ⧺ ys

={ map, e identity }

map (λv → (v ⊛ y) ⊛ z) xs ⧺ [y] ⧺ ys

={ associtivity of ⊛ }

map (λv → v ⊛ (y ⊛ z)) xs ⧺ [y] ⧺ ys

={ z ⊛ y =x }

map (⊛ x) xs ⧺ [x] ⧺ (y:ys)

### Prologue

Given the complexity of the proof above, I did not think there was a hope to automatically construct

Being just graduated from AoP, I was perhaps too arrogant and proud of all the clever derivation we did to care about automatic program construction. (Like Jeremy, in the end of my thesis I quoted “善數不用籌策 (Those who good at calculation need no mechanical aids)” from 老子 Lao Tzu. And didn’t Dijkstra say “I hardly used the computer they gave me. I was perfectly happy without it.”?) The relational method, which seemed to cover everything, gave me a false feeling that I knew the problem inside out.

Last year, however, my colleagues and I met again and I was told that they eventually published a paper on this subject:

Kazutaka Morita, Akimasa Morihata, Kiminori Matsuzaki, Zhenjiang Hu, Masato Takeichi. Automatic Inversion Generates Divide-and-Conquer Parallel Programs, PLDI 2007.

They focused on weak inverses that returns only lists with fixed lengths. The advantage is that calculations like the one above are no longer necessary — since the lists are of fixed-length,

Well, I think the moral is that we cannot just stop when it appears that is no elegant solution that suits our taste. It sometimes pays to get our hands dirty, through which we may eventually discover the beauty within.

Pingback: Tiempo finito y logarítmico » Tercer teorema de homomorfismo