Metamorphisms

It appears that I have insufficient time, or at least insufficient discipline, to contribute to this blog, except when I am on sabbatical. Which I now am… so let’s see if I can do better.

Hylomorphisms

I don’t think I’ve written about them yet in this series—another story, for another day—but hylomorphisms consist of a fold after an unfold. One very simple example is the factorial function: ${n!}$ is the product of the predecessors ${[n,...,1]}$ of ${n}$ . The predecessors can be computed with an unfold:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{preds} &::& \mathit{Integer} \rightarrow [\mathit{Integer}] \\ \mathit{preds} &=& \mathit{unfoldr}\;\mathit{step} \; \mathbf{where} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{step}\;0 &=& \mathit{Nothing} \\ \mathit{step}\;n &=& \mathit{Just}\;(n, n-1) \end{array} \end{array}$

and the product as a fold:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{prod} &::& [\mathit{Integer}] \rightarrow \mathit{Integer} \\ \mathit{prod} &=& \mathit{foldr}\;(\times)\;1 \end{array}$

and then factorial is their composition:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{factorial} &::& \mathit{Integer} \rightarrow \mathit{Integer} \\ \mathit{factorial} &=& \mathit{prod} \cdot \mathit{preds} \end{array}$

Another example is a tree-based sorting algorithm that resembles Hoare’s quicksort: from the input list, grow a binary search tree, as an unfold, and then flatten that tree back to a sorted list, as a fold. This is a divide-and-conquer algorithm; in general, these can be modelled as unfolding a tree of subproblems by repeatedly dividing the problem, then collecting the solution to the original problem by folding together the solutions to subproblems.

An unfold after a fold

This post is about the opposite composition, an unfold after a fold. Some examples:

${\mathit{regroup}\;n = \mathit{group}\;n \cdot \mathit{concat}}$ to reformat a list of lists to a given length;
${\mathit{heapsort} = \mathit{flattenHeap} \cdot \mathit{buildHeap}}$ to sort a list;
${\mathit{baseconv}\;(b,c) = \mathit{toBase}\;b \cdot \mathit{fromBase}\;c}$ to convert a fraction from base ${c}$ to base ${b}$ ;
${\mathit{arithCode} = \mathit{toBits} \cdot \mathit{narrow}}$ to encode a text in binary by “arithmetic coding”.

In each of these cases, the first phase is a fold, which consumes some structured representation of a value into an intermediate unstructured format, and the second phase is an unfold, which generates a new structured representation. Their composition effects a change of representation, so we call them metamorphisms.

Hylomorphisms always fuse, and one can deforest the intermediate virtual data structure. For example, one need not construct the intermediate list in the factorial function; since each cell gets constructed in the unfold only to be immediately deconstructed in the fold, one can cut to the chase and go straight to the familiar recursive definition. For the base case, we have:

$\displaystyle \begin{array}{ll} & \mathit{factorial}\;0 \\ = & \qquad \{ \mathit{factorial} \} \\ & \mathit{prod}\;(\mathit{preds}\;0) \\ = & \qquad \{ \mathit{preds} \} \\ & \mathit{prod}\;[\,] \\ = & \qquad \{ \mathit{prod} \} \\ & 1 \end{array}$

and for non-zero argument ${n}$ , we have:

$\displaystyle \begin{array}{ll} & \mathit{factorial}\;n \\ = & \qquad \{ \mathit{factorial} \} \\ & \mathit{prod}\;(\mathit{preds}\;n) \\ = & \qquad \{ \mathit{preds} \} \\ & \mathit{prod}\;(n : \mathit{preds}\;(n-1)) \\ = & \qquad \{ \mathit{prod} \} \\ & n \times \mathit{prod}\;(\mathit{preds}\;(n-1)) \\ = & \qquad \{ \mathit{factorial} \} \\ & n \times \mathit{factorial}\;(n-1) \\ \end{array}$

In contrast, metamorphisms only fuse under certain conditions. However, when they do fuse, they also allow infinite representations to be processed, as we shall see.

Fusion seems to depend on the fold being tail-recursive; that is, a ${\mathit{foldl}}$ :

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{foldl} &::& (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow \beta \\ \mathit{foldl}\;f\;b\;(a:x) &=& \mathit{foldl}\;f\;(f\;b\;a)\;x \\ \mathit{foldl}\;f\;b\;[\,] &=& b \end{array}$

For the unfold phase, we will use the usual list unfold:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{unfoldr} &::& (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow \beta \rightarrow [\gamma] \\ \mathit{unfoldr}\;g\;b &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{unfoldr}\;g\;b' \\ \mathit{Nothing} &\rightarrow& [\,] \end{array} \end{array}$

We define a metamorphism as their composition:

$\displaystyle \begin{array}{l} \mathit{meta} :: (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow [\gamma] \\ \mathit{meta}\;g\;f\;b = \mathit{unfoldr}\;g \cdot \mathit{foldl}\;f\;b \end{array}$

This transforms input of type ${[A]}$ to output of type ${[C]}$ : in the first phase, ${\mathit{foldl}\;f\;b}$ , it consumes all the input into an intermediate value of type ${B}$ ; in the second phase, ${\mathit{unfoldr}\;g}$ , it produces all the output.

Streaming

Under certain conditions, it is possible to fuse these two phases—this time, not in order to eliminate an intermediate data structure (after all, the intermediate type ${B}$ need not be structured), but rather in order to allow some production steps to happen before all the consumption steps are complete.

To that end, we define the ${\mathit{stream}}$ function as follows:

$\displaystyle \begin{array}{@{}lcl@{}} \multicolumn{3}{@{}l}{\mathit{stream} :: (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow [\gamma]} \\ \mathit{stream}\;g\;f\;b\;x &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{stream}\;g\;f\;b'\;x \\ \mathit{Nothing} &\rightarrow& \mathbf{case}\;x\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} a:x' &\rightarrow& \mathit{stream}\;g\;f\;(f\;b\;a)\;x' \\ {[\,]} &\rightarrow& [\,] \end{array} \end{array} \end{array}$

This takes the same arguments as ${\mathit{meta}}$ . It maintains a current state ${b}$ , and produces an output element ${c}$ when it can; and when it can’t produce, it consumes an input element instead. In more detail, it examines the current state ${b}$ using function ${g}$ , which is like the body of an unfold; this may produce a first element ${c}$ of the result and a new state ${b'}$ ; when it yields no element, the next element ${a}$ of the input is consumed using function ${f}$ , which is like the body of a ${\mathit{foldl}}$ ; and when no input remains either, we are done.

The streaming condition for ${f}$ and ${g}$ is that

$\displaystyle g\;b = \mathit{Just}\;(c,b') \quad\Rightarrow\quad \forall a \mathbin{.} g\;(f\;b\;a) = \mathit{Just}\;(c, f\;b'\;a)$

Consider a state ${b}$ from which the body ${g}$ of the unfold is productive, yielding some ${\mathit{Just}\;(c,b')}$ . From here we have two choices: we can either produce the output ${c}$ , move to intermediate state ${b'}$ , then consume the next input ${a}$ to yield a final state ${f\;b'\;a}$ ; or we can consume first to get the intermediate state ${f\;b\;a}$ , and again try to produce. The streaming condition says that this intermediate state ${f\;b\;a}$ will again be productive, and will yield the same output ${c}$ and the same final state ${f\;b'\;a}$ . That is, instead of consuming all the inputs first, and then producing all the outputs, it is possible to produce some of the outputs early, without jeopardizing the overall result. Provided that the streaming condition holds for ${f}$ and ${g}$ , then

$\displaystyle \mathit{stream}\;g\;f\;b\;x = \mathit{meta}\;g\;f\;b\;x$

for all finite lists ${x}$ .

As a simple example, consider the `buffering’ process ${\mathit{meta}\;\mathit{uncons}\;(\mathbin{{+}\!\!\!{+}})\;[\,]}$ , where

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{uncons}\;x &=& \mathbf{case}\;x\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} [\,] &\rightarrow& \mathit{Nothing} \\ c:x' &\rightarrow& \mathit{Just}\;(c,x') \end{array} \end{array}$

Note that ${\mathit{unfoldr}\;\mathit{uncons} = \mathit{id}}$ , so ${\mathit{meta}\;\mathit{uncons}\;(\mathbin{{+}\!\!\!{+}})\;[\,]}$ is just a complicated way of writing ${\mathit{concat}}$ as a ${\mathit{foldl}}$ . But the streaming condition holds for ${\mathbin{{+}\!\!\!{+}}}$ and ${\mathit{uncons}}$ (as you may check), so ${\mathit{concat}}$ may be streamed. Operationally, the streaming version of ${\mathit{concat}}$ consumes one list from the input list of lists, then peels off and produces its elements one by one; when they have all been delivered, it consumes the next input list, and so on.

Flushing

The streaming version of ${\mathit{concat}}$ is actually rather special, because the production steps can always completely exhaust the intermediate state. In contrast, consider the `regrouping’ example ${\mathit{regroup}\;n = \mathit{meta}\;(\mathit{chunk}\;n)\;(\mathbin{{+}\!\!\!{+}})\;[\,]}$ where

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{chunk}\;n\;[\,] &=& \mathit{Nothing} \\ \mathit{chunk}\;n\;x &=& \mathit{Just}\;(\mathit{splitAt}\;n\;x) \end{array}$

from the introduction (here, ${\mathit{splitAt}\;n\;x}$ yields ${(y,z)}$ where ${y \mathbin{{+}\!\!\!{+}} z = x}$ , with ${\mathit{length}\;y=n}$ when ${n \le \mathit{length}\;x}$ and ${y=x}$ otherwise). This transforms an input list of lists into an output list of lists, where each output `chunk’ except perhaps the last has length ${n}$ —if the content doesn’t divide up evenly, then the last chunk is short. One might hope to be able to stream ${\mathit{regroup}\;n}$ , but it doesn’t quite work with the formulation so far. The problem is that ${\mathit{chunk}}$ is too aggressive, and will produce short chunks when there is still some input to consume. (Indeed, the streaming condition does not hold for ${\mathbin{{+}\!\!\!{+}}}$ and ${\mathit{chunk}\;n}$ —why not?) One might try the more cautious producer ${\mathit{chunk'}}$ :

$\displaystyle \begin{array}{@{}lclcl@{}} \mathit{chunk'}\;n\;x &\mid& n \le \mathit{length}\;x &=& \mathit{Just}\;(\mathit{splitAt}\;n\;x) \\ &\mid& \mathbf{otherwise} &=& \mathit{Nothing} \end{array}$

But this never produces a short chunk, and so if the content doesn’t divide up evenly then the last few elements will not be extracted from the intermediate state and will be lost.

We need to combine these two producers somehow: the streaming process should behave cautiously while there is still remaining input, which might influence the next output; but it should then switch to a more aggressive strategy once the input is finished, in order to flush out the contents of the intermediate state. To achieve this, we define a more general flushing stream operator:

$\displaystyle \begin{array}{@{}lcl@{}} \multicolumn{3}{@{}l@{}}{\mathit{fstream} :: (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow [\gamma]) \rightarrow (\beta \rightarrow \alpha \rightarrow \beta) \rightarrow \beta \rightarrow [\alpha] \rightarrow [\gamma]} \\ \mathit{fstream}\;g\;h\;f\;b\;x &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{fstream}\;g\;h\;f\;b'\;x \\ \mathit{Nothing} &\rightarrow& \mathbf{case}\;x\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} a:x' &\rightarrow& \mathit{fstream}\;g\;h\;f\;(f\;b\;a)\;x' \\ {[\,]} &\rightarrow& h\;b \end{array} \end{array} \end{array}$

This takes an additional argument ${h :: \beta \rightarrow [\gamma]}$ ; when the cautious producer ${g}$ is unproductive, and there is no remaining input to consume, it uses ${h}$ to flush out the remaining output elements from the state. Clearly, specializing to ${h\;b=[\,]}$ retrieves the original ${\mathit{stream}}$ operator.

The corresponding metamorphism uses an apomorphism in place of the unfold. Define

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{apo} &::& (\beta \rightarrow \mathsf{Maybe}\;(\gamma,\beta)) \rightarrow (\beta \rightarrow [\gamma]) \rightarrow \beta \rightarrow [\gamma] \\ \mathit{apo}\;g\;h\;b &=& \mathbf{case}\;g\;b\;\mathbf{of} \\ & & \quad \begin{array}[t]{@{}lcl@{}} \mathit{Just}\;(c,b') &\rightarrow& c : \mathit{apo}\;g\;h\;b' \\ \mathit{Nothing} &\rightarrow& h\;b \end{array} \end{array}$

Then ${\mathit{apo}\;g\;h}$ behaves like ${\mathit{unfoldr}\;g}$ , except that if and when ${g}$ stops being productive it finishes up by applying ${h}$ to the final state. Similarly, define flushing metamorphisms:

$\displaystyle \mathit{fmeta}\;g\;h\;f\;b = \mathit{apo}\;g\;h \cdot \mathit{foldl}\;f\;b$

Then we have

$\displaystyle \mathit{fstream}\;g\;h\;f\;b\;x = \mathit{fmeta}\;g\;h\;f\;b\;x$

for all finite lists ${x}$ if the streaming condition holds for ${f}$ and ${g}$ . In particular,

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{regroup}\;n\;\mathit{xs} &=& \mathit{fmeta}\;(\mathit{chunk'}\;n)\;(\mathit{unfoldr}\;(\mathit{chunk}\;n))\;(\mathbin{{+}\!\!\!{+}})\;[\,]\;\mathit{xs} \\ &=& \mathit{fstream}\;(\mathit{chunk'}\;n)\;(\mathit{unfoldr}\;(\mathit{chunk}\;n))\;(\mathbin{{+}\!\!\!{+}})\;[\,]\;\mathit{xs} \end{array}$

on finite inputs ${\mathit{xs}}$ : the streaming condition does hold for ${\mathbin{{+}\!\!\!{+}}}$ and the more cautious ${\mathit{chunk'}\;n}$ , and once the input has been exhausted, the process can switch to the more aggressive ${\mathit{chunk}\;n}$ .

Infinite input

The main advantage of streaming is that it can allow the change-of-representation process also to work on infinite inputs. With the plain metamorphism, this is not possible: the ${\mathit{foldl}}$ will yield no result on an infinite input, and so the ${\mathit{unfoldr}}$ will never get started, but the ${\mathit{stream}}$ may be able to produce some outputs before having consumed all the inputs. For example, the streaming version of ${\mathit{regroup}\;n}$ also works for infinite lists, providing that the input does not end with an infinite tail of empty lists. And of course, if the input never runs out, then there is no need ever to switch to the more aggressive flushing phase.

As a more interesting example, consider converting a fraction from base 3 to base 7:

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{fromBase3} &=& \mathit{foldr}\;\mathit{stepr}\;0 \quad \mathbf{where}\;\mathit{stepr}\;d\;x = (d+x)/3 \\ \mathit{toBase7} &=& \mathit{unfoldr}\;\mathit{next} \quad \mathbf{where}\; \begin{array}[t]{@{}lcl@{}} \mathit{next}\;0 &=& \mathit{Nothing} \\ \mathit{next}\;x &=& \mathbf{let}\;y=7\times x\;\mathbf{in}\;\mathit{Just}\;(\lfloor y\rfloor, y-\lfloor y\rfloor) \end{array} \end{array}$

We assume that the input digits are all either 0, 1 or 2, so that the number being represented is in the unit interval.

The fold in ${\mathit{fromBase3}}$ is of the wrong kind; but we have also

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{fromBase3} &=& \mathit{extract} \cdot \mathit{foldl}\;\mathit{stepl}\;(0,1) \quad \mathbf{where}\; \mathit{stepl}\;(u,v)\;d = (u \times 3 + d, v / 3) \end{array}$

Here, the intermediate state ${(u,v)}$ can be seen as a defunctionalized representation of the function ${(v\times) \cdot (u+)}$ , and ${\mathit{extract}}$ applies this function to ${0}$ :

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{apply}\;(u,v)\;x &=& v \times (u + x) \\ \mathit{extract}\;(u,v) &=& \mathit{apply}\;(u,v)\;0 \end{array}$

Now there is an extra function ${\mathit{extract}}$ between the ${\mathit{foldl}}$ and the ${\mathit{unfoldr}}$ ; but that’s no obstacle, because it fuses with the ${\mathit{unfoldr}}$ :

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{toBase7} \cdot \mathit{extract} &=& \mathit{unfoldr}\;\mathit{next'} \quad \mathbf{where}\; \begin{array}[t]{@{}lcl@{}} \mathit{next'}\;(0,v) &=& \mathit{Nothing} \\ \mathit{next'}\;(u,v) &=& \begin{array}[t]{@{}l} \mathbf{let}\;y = \lfloor{7 \times u \times v}\rfloor\;\mathbf{in} \\ \mathit{Just}\;(y,(u - y/(v \times 7), v \times 7)) \end{array} \end{array} \end{array}$

However, the streaming condition does not hold for ${\mathit{stepl}}$ and ${\mathit{next'}}$ . For example,

$\displaystyle \begin{array}{@{}lcl@{}} \mathit{next'}\;(1,{{}^{1\!}/_{\!3}}) &=& \mathit{Just}\;(2, ({{}^{1\!}/_{\!7}},{{}^{7\!}/_{\!3}})) \\ \mathit{next'}\;(\mathit{stepl}\;(1,{{}^{1\!}/_{\!3}})\;1) &=& \mathit{next'}\;(4,{{}^{1\!}/_{\!9}}) \\ &=& \mathit{Just}\;(3,({{}^{1\!}/_{\!7}},{{}^{7\!}/_{\!9}})) \end{array}$

That is, ${0.1_3 \simeq 0.222_7}$ , but ${0.11_3 \simeq 0.305_7}$ , so it is premature to produce the first digit 2 in base 7 having consumed only the first digit 1 in base 3. The producer ${\mathit{next'}}$ is too aggressive; it should be more cautious while input remains that might invalidate a produced digit.

Fortunately, on the assumption that the input digits are all 0, 1, or 2, the unconsumed input—a tail of the original input—again represents a number in the unit interval; so from the state ${(u,v)}$ the range of possible unproduced outputs represents a number between ${\mathit{apply}\;(u,v)\;0}$ and ${\mathit{apply}\;(u,v)\;1}$ . If these both start with the same digit in base 7, then (and only then) is it safe to produce that digit. So we define

$\displaystyle \mathit{next''}\;(u,v) = \mathbf{if}\;\lfloor{u \times v \times 7}\rfloor = \lfloor{(u+1) \times v \times 7}\rfloor\;\mathbf{then}\;\mathit{next'}\;(u,v)\;\mathbf{else}\;\mathit{Nothing}$

and we have

$\displaystyle \mathit{unfoldr}\;\mathit{next'} = \mathit{apo}\;\mathit{next''}\;(\mathit{unfoldr}\;\mathit{next'})$

Now, the streaming condition holds for ${\mathit{stepl}}$ and ${\mathit{next''}}$ (as you may check), and therefore

$\displaystyle \mathit{toBase7}\;(\mathit{fromBase3}\;x) = \mathit{fstream}\;\mathit{next''}\;(\mathit{unfoldr}\;\mathit{next'})\;\mathit{stepl}\;(0,1)\;x$

on finite digit sequences ${x}$ in base 3. Moreover, the streaming program works also on infinite digit sequences, where the original does not.

(Actually, the only way this could possibly produce a finite output in base 7 would be for the input to be all zeroes. Why? If we are happy to rule out this case, we could consider only the case of taking infinite input to infinite output, and not have to worry about reaching the end of the input or flushing the state.)

7 Responses to Metamorphisms

Mark Dominus says:

Friday, October 13th, 2017 at 5:52 pm

I was thrilled to see an update on your blog. I’ve read this once and I am looking forward to rereading it more carefully.

Thanks for posting.

- jeremygibbons says:
  
  Friday, October 13th, 2017 at 6:55 pm
  
  That’s very kind of you, Mark!
  
Pingback: The Digits of Pi | Patterns in Functional Programming
Daniel Díaz Carrete says:

Monday, November 13th, 2017 at 7:17 am

Great post!

It seems that, when constructing data structures like trees, we can often choose to do it either with an unfold (like in the “tree-based sorting algorithm”) or with a fold (like in the heapsort metamorphsim).

Another example: sometimes I have to annotate a syntax tree with information that flows from the root to the leaves, and it seems one can do that with an unfold, or with a catamorphism that returns a function.

Is there a principled way to choose between folds/unfolds in these cases?

- jeremygibbons says:
  
  Tuesday, November 14th, 2017 at 11:12 am
  
  I don’t know about “principled way to choose”; I think that’s largely a matter of taste. Try it both ways, and see which you prefer! More concretely, consider which properties you might like to prove of such functions; maybe those properties are more easily proved using coinduction than induction, in which case you should probably look for a coinductive program (an unfold) over an inductive one (a fold).
  
  Specifically on the topic of annotating a syntax tree, you might like the paper I wrote for Doaitse Swierstra’s festschrift: https://www.cs.ox.ac.uk/publications/publication6894-abstract.html
  
jeremygibbons says:

Tuesday, November 14th, 2017 at 5:36 pm

Hm… ignore the last paragraph, which is nonsense. If the value represented by the sequence x has a finite representation in base 7, then the toBase7 part hangs. Of course.

Pingback: Resumen de lecturas compartidas durante octubre de 2017 | Vestigium

Metamorphisms

Hylomorphisms

An unfold after a fold

Streaming

Flushing

Infinite input

Related

About jeremygibbons

7 Responses to Metamorphisms

Leave a Reply Cancel reply

Where to Start

Recent Posts

Archives

Meta

Where to go next?