Tacit Talk

Episode 32: Richard Bird's Algebraic Laws 🟦

• Conor Hoekstra

Share episode

Use Left/Right to seek, Home/End to jump to start or end. Hold shift to jump forward or backward.

0:00 | 41:45

In this episode, the "Richard Bird's Algebraic Laws for Program Calculation" which is a summary of the important papers that introduced the algebraic laws of programming (generated by Claude 4.6 Opus) is read by the Speechify text-to-speech app.

Socials

Show Notes

Date Released: 2026-03-14

SPEAKER_00

Welcome to episode 32 of Tacit Talk. In this episode, we're going to be doing something a little bit different. Recently, for research that I was doing for my day job, I was putting together or having Claude 4.6 Opus put together a opposition research survey paper, which is entitled Survey of Lazy Deferred Array Runtimes, Array DSLs, and Automatic Fusion. And I can link this survey paper that the AI put together in the show notes if folks are interested. But it reminded me of a paper that my boss, Michael Garland, put on my radar on May 12th, 2023. So this is almost three years ago, pre-GPT explosion. And the paper is called Algebraic Identities for Program Calculation by Richard Bird, who, for those of you that might have heard or not heard, is the author of The Algebra of Programming, which was published in 1996. And then later on, I believe co-authored with Jeremy Gibbons The Algorithm Design with Haskell book, which now to my knowledge is apparently a kind of revision of the algebra of programming with less category theory and symbolic notation and more just done in Haskell. And the reason that the research that I was doing on array fusion reminded me of this algebraic identities paper by Richard Byrd, which at the time in 2023, I didn't even realize that the author of this paper was the same author that had written the algebra of programming, is that in section five of this paper, it mentions the fold scan fusion law, where you can turn a scan followed by a fold into just a fold, which is very elegant. And there are other laws that are mentioned in the paper, and it also mentions that there are just other laws that exist. It says there are a number of other identities concerning scan, of which we will cite just one, which is the fold scan fusion law. And at the time I found this very, very curious. And also in the paper, it mentions one of my favorite problems. It's in the top 10 problems, linked to that GitHub repo. It's 10 problems that I like thinking about. It's the max maximum segment sum, aka M CSS, aka Cadan's algorithm, and it shows this program transformation starting with max of mapping sum over the segments of a list, and how that is an O N cubed algorithm, but using the program transformation techniques and the laws that he has constructed, you can get it down to an ON solution. And this is the BQN spelling of this problem is one of the most beautiful, if not the most beautiful, piece of code that I've seen in my life. I've tweeted about this in the past. Anyway, so this this paper's great. And doing this research for the array fusion stuff made me think of this paper. And then I ended up going down a huge deep dive of all of Richard Byrd's research, Myrton's research, who he co-authored a number of things with, and apparently that led to the BM formalism, which is the Bird Myrton's formalism, which I hadn't heard of. And I think all of this is very, very fascinating because before algebra of the algebra of programming was published, and then later on the algorithm design using Haskell, those two publications use kind of Miranda slash Haskell syntax. But before that, in publications like an Introduction to the Theory of Lists, they actually used APL-esque notation. They borrowed the slash and backslash for fold and scan, and they use symbols for binary operations. And a few of the publications even reference APL. Later on, there's a paper by Jeremy Gibbons, who is the co-author of the algorithm design with Haskell textbook, and they were working on something called Squiggle, SQUIGGOL. And in there they use kind of arrow slashes for left folds and right folds. Anyways, it's all very, very curious if you are interested in array languages. And on top of that, for commuting a binary operation, they have this symbol which is a tilde overstruck of a, I can't remember which cross it is, but it's a basically a plus sign inside of a circle. And that made me think of the commute operator from APL and the swap from BQN, which are both tildes. Um and an APL just has the double diurasis on top. Anyways, I went ahead and had Claude 4.6 Opus as well as GPT 5.4 put together an overview of what the AI called the tier one or primary publications that led to these different algebraic laws. So without further ado, this is a text-to-speech reading of the summary of Richard Byrd's algebraic laws.

SPEAKER_01

Richard Byrd's Algebraic Laws for Program Calculation, a detailed survey of the eight primary publications, compiled from Byrd's Publications, 1984 to 2020, March 2026. Introduction. Between 1984 and 2020, Richard Byrd developed a body of algebraic laws for transforming functional programs from clear but inefficient specifications into efficient implementations. These laws, concerning map, fold, scan, promotion, accumulation, Horner's rule, and fusion, form the core of the Bird Mirton's Formalism, BMF, colloquially known as Squiggle. This document surveys the eight primary publications in which these laws are defined and proved in chronological order. For each paper, we describe the context, the specific laws introduced, their formal statements, and their significance. 1. The Promotion and Accumulation Strategies in Transformational Programming, 1984. Citation. R. S. Byrd. The Promotion and Accumulation Strategies in Transformational Programming. ACM Transactions on Programming Languages and Systems. 6, 4, 487 to 504, October 1984. Addendum. R. S. Byrd. Addendum to the Promotion and Accumulation Strategies in Transformational Programming. ACM Toplus 7.3, 490-492, July 1985. Context. This is Byrd's first systematic treatment of two named transformation strategies for deriving efficient programs from specifications over list structures. The paper predates the squiggly BMF notation. It uses a more conventional mathematical style. It was published in Topless, the premier venue for programming language theory at the time. Laws introduced the promotion strategy. The promotion strategy concerns the interaction of a function with the concatenation, or join, of data structure. In modern terms, this encompasses map promotion. If f is applied element-wise, mapped, over a concatenated structure, it can be promoted into the components. Map F, concat XSS, equal to concat, map, mapf, XSS. Reduce promotion. If a reduction, fold is applied to a concatenated structure, it can be promoted into the components. Folder, E, concat XSS, equal to folder, E, Map, folder, E, XSS. These promotion laws allow transformations that decompose a computation over a compound structure into computations over its parts. The accumulation strategy. The accumulation strategy introduces the idea of computing all intermediate results of a fold, what we now call a scan. The key insight is that independent fold computations or overlapping prefixes or suffixes of a list can be replaced by a single left-to-right or right-to-left accumulation, map, fold, E, in its XS, equal to scan, EXS. This replaces O, N2, work, one fold per prefix, with O, N, work, one scan. Significance. This paper established the two core strategies that recur throughout all of Byrd's subsequent work. Every derivation in the 1989 paper and beyond uses promotion and accumulation as fundamental moves. 2. An Introduction to the Theory of Lists, 1986. Citation. R. S. Byrd. An Introduction to the Theory of Lists. Technical Monograph PRG 56. Programming Research Group, Oxford University, October 1986. Published in M. Broy ed. Logic of Programming and Calculi of Discrete Design. Springer Verlag, 1987, pp. 3-42. Context. This is the foundational reference for the entire BMF as applied to lists. Written as Lecture Notes at Oxford, PRG 56 introduces a complete notation and calculus for list manipulation, defines all the core operations and their algebraic properties, and proves the principal laws. Much of the subsequent work, including the 1989 paper, is a condensation or application of material first presented here. Operations defined. The monograph defines with full types and algebraic properties. Concatenation plus plus associative with identity. Distributes through concatenation. Reduce collapses a list via an associative operator. Filter P selects elements satisfying predicate P. Directed reductions, E and E, left and right folds with a seed value. Accumulations, E and E, left and right scans, producing all intermediate fold results. Segments, inits, tails, segs, all initial segments, final segments, and contiguous segments, laws stated and proved. Promotion laws, F concat equal to CONCAT, F concat equal to PET duality and specialization. 6. Duality lemma. Left and right folds are related by reversal, foldal, e equal to folder, e reverse, where a B equal to B, A. 7. Specialization lemma. Every list homomorphism can be expressed as either a left or a right reduction. The accumulation lemma, scan lemma, 8, accumulation lemma, scale, e equal to map, foldal, e, inits, and a dual for right accumulations and tails. This is the defining specification of scan. The kth element of a left scan is the left fold over the first k elements. Computing map foldal E inits takes O N2 time. Computing scale. 9. Horner's rule, if distributes backwards over that is a B, C equal to A C B C, then tails equal to E, where E equal to ID and a B equal to ABE. This converts an O N to computation, reduce over each tail, then reduce the results into an O N single right fold. Homomorphism homomorphism lemma every list homomorphism H satisfying H X plus plus Y equal to HXHY can be decomposed as H equal to F, and conversely, every such composition is a homomorphism. Significance. PRG 56 is the single most important reference for the list level algebraic laws. All subsequent papers and books by Byrd build on definitions and results, first stated here. The notation evolved from squiggles to Miranda to Haskell, but the laws themselves are unchanged. 3. A calculus of functions for program derivation, 1987. Citation, R. S. Byrd. A calculus of functions for program derivation. Technical monograph PRG 64, Programming Research Group, Oxford University, December 1987. Published in D. A. Turner, ed. Research Topics in Functional Programming, Addison Wesley, 1990. Context. This monograph extends the theory of PRG 56 by developing a more complete calculus, a systematic notation, and two general theorems for transforming specifications into efficient implementations. Byrd explicitly argues that an effective calculus of program derivation must be built upon useful. General theorems relating certain forms of expression to common patterns of computation. Key contributions. Notation. PRG64 introduces a refined notation for curried functions, functional composition, and operators, aiming for a calculus as usable as integral calculus is for mathematicians. The notation is intermediate between the early squiggles, PRG 56, and the later Miranda Haskell conventions. 2. General Theorems. The paper states and proves two main theorems. 1. Theorem. One concerns the efficient evaluation of expressions of the form, FG, where G generates a data structure and F maps over it. Under suitable conditions, distributivity, associativity, this can be transformed into a directed reduction. 2. Theorem 2 generalizes the first to handle more complex patterns involving nested compositions of reductions and maps. These theorems subsume the promotion laws, the accumulation lemma, and Horner's rule as special cases, providing a unified framework for the individual laws of PRG-56. Application, run-length encoding. The paper demonstrates the calculus by deriving an efficient algorithm for run-length encoding from its specification, the shortest sequence of pairs that decodes to the given input. The derivation proceeds entirely by equational reasoning, applying the general theorems. Significance. PRG 64 is the most calculus-like of Byrd's presentations. It argues for and demonstrates a style of derivation modeled on mathematical problem solving, like formal integration, where one applies known theorems rather than ad hoc reasoning. The two general theorems provide a unifying perspective on the individual laws. 4. Lectures on Constructive Functional Programming, 1988. Citation, R. S. Byrd. Lectures on Constructive Functional Programming. Technical Monograph PRG 69, Programming Research Group, Oxford University, September 1988. Published in M. Broy ed. Constructive Methods and Computer Science, Springer Verlag, 1988, pp. 151-218. NATO Aussie Series, F. Volume 55. Context. These are Byrd's Mark Toberdorf Summer School Lectures, an extended fully worked treatment spanning 68 pages across five lectures. Each lecture poses a problem, develops the necessary theory, and solves the problem by calculation. This is the most detailed and pedagogically complete presentation of the laws, and the direct precursor to the 1989 journal paper, Structure Lecture 1, lists covers all the definitions and laws from PRG 56, plus several extensions, multiple forms of Horner's rule, the basic form, a variant for non-empty lists without requiring ID, and a form involving map, F, tails equal to, E, ray B equal to A, F B, E. Segment Decomposition Theorem, a general scheme that combines promotion, Horner's rule, and the accumulation lemma, if s equal to f segs and t equal to f tails and t can be expressed as t equal to h, e, then s equal to h scannel, e. Lecture 2, homomorphisms, extends the homomorphism, lemma, and proves the identity lemma. H equal to FHA equal to F A and H X plus plus Y equal to HXHY. Includes worked examples, length, reverse, sort, as homomorphisms. Lecture 3. Arrays generalizes the entire theory to two-dimensional arrays. Array accumulations, top accumulation, and left accumulation operators, orthogonal accumulation rules, laws for composing accumulations along different axis. Array Horner's rule, a two-dimensional version requiring an additional condition, abiding, lecture four, segments of arrays, applies the laws to array segment problems. Lecture 5 trees extends to tree structures with tree reductions and tree accumulations, upwards and downwards. Tree accumulation lemma. Tree homomorphisms, key applications. Maximum segment sum MSS, the derivation from O N3, 2, O, N, that later appeared in the 1989 paper. Maximum segment product, a harder variant requiring a pair of tracked values, maximum and minimum products, solved via a generalized Horner's rule. Significance. PRG69 is the most comprehensive single treatment of the laws across multiple data structures, lists, arrays, trees. It is the only source that presents the full generalization to arrays and trees alongside the list theory. 5. Algebraic Identities for Program Calculation, 1989. Citation, R. S. Byrd. Algebraic Identities for Program Calculation. The Computer Journal 32, 2, 122 to 126, April 1989. Context. This five-page journal paper is a condensed, polished presentation of the maximum segment, some derivation from PRG 69 Lecture 1. It is the most widely cited single source for the BMF laws in their standard form. Byrd deliberately uses the notation of Byrd and Waddler's Introduction to Functional Programming, 1988, rather than squiggles, to maximize accessibility. Laws used, numbered equations 1 to 13. The paper contains 13 numbered equations. The named laws deployed are 1. Definitions EQS. 1 to 4. Map Foldal Scale Inits. Concat. 2. Map Promotion EQ. 5. Map F Concat equal to CONCAT MAP MAP F3. Fold Promotion. EQ. 6. Foldal. Econcat equal to Foldal. E map. Foldal. E. 4. Horner's rule. EQ 9. Expressed as a transformation of tails into a single fold under the distributivity condition. 5. Scan lemma. Accumulation lemma. EQ. 11. Scan. E equal to map. Foldal. E. Inits. H equal to F H X plus plus Y equal to H X H Y and H A equal to F A. Foldal. A scannel. B equal to FST foldal. A B, B, where is a suitably defined ternary combination of and. This fuses a fold composed after a scan into a single fold, eliminating the intermediate list. Bird notes, there are a number of other identities concerning scale, of which we cite just one, the MSS derivation. The paper derives the linear time maximum segment, sum algorithm in a chain of equational steps. MSS equal to max, some segs equal to max, some concat map tails in its equal to max. Max, some tails, in its equal to max, zero, in its equal to max, scale, zero. O, N3, defin of segs. Map and reduce promotion Horner's rule. A B equal to A plus B, 0. Scan Lemma, Own Significance. This is the canonical reference that most subsequent authors cite when invoking the BMF laws. Its brevity, five pages, and accessibility, standard Haskell-like notation, made it far more widely read than the longer monographs. The fold scan fusion law, EQ 13, is particularly important for practical program optimization. 6. The Algebra of Programming, 1996, Citation, R. Byrd, and O. D. Moore, The Algebra of Programming. Their National Series in Computing Science, Volume 100, Prentice, Hall, 1996, dated 1997. Context. This is the comprehensive book, Length Treatment. So, authored with Oige Demore. It represents the culmination of a decade of BMF development. The major intellectual shift from the earlier work is the move from functions to relations as the primary mathematical framework, and the adoption of category theory, functors, natural transformations, initial algebras, as the organizing principle, structure, and scope. The book is organized around increasingly powerful algebraic structures. Part one, sets and categories, categories, functors, natural transformations, products, coproducts, initial and terminal objects, part two. 2. Data types. Initial algebras and catamorphisms generalized folds. For any functor f with initial algebra f in, the unique F algebra homomorphism from F to any F algebra A is the catamorphism, satisfying the universal property, H equal to hoin, OF. Anamorphisms, generalized unfolds, and hylomorphisms, unfold then fold. Paramorphisms, folds with access to the original structure. Part 3. Relations. Relational catamorphisms and their laws. Relational division, a generalization of residuation, and weakest per specification, power allegories as the categorical framework. Key laws generalized all the laws from PRG 561989 are restated in the categorical relational setting. Fx equal to X equal to F04 equal to F F. Single Pass O D D equal to F1 F2. 3. Acid rain theorem, build, fold fusion, folder, build. Eliminates intermediate data structures. 4. Accumulation and scan as natural transformations on initial algebras. 5. Greedy and thinning theorems for optimization problems. Conditions under which a greedy algorithm produces an optimal solution. Dynamic programming conditions, when greedy fails, conditions for efficient, memoized computation. Significance. Algebra of programming is the most general and most powerful treatment of the laws. It provides categorical proofs that work for any inductively defined data type, not just lists. However, as Jeremy Gibbons noted, it contains a lot of laws and is a difficult read. The relational framework, while elegant, proved too complex for wide adoption, and both Byrd and the community eventually retreated to a purely functional approach. 7. Generic functional programming with types and relations, 1996. Citation, R. Byrd, O'Demore, and P. Hugendijk. Generic Functional Programming with Types and Relations. Journal of Functional Programming. 6.1.1-28 1996. Context. This paper bridges the gap between the list-specific laws of PRG 56-1000, 9, 189ths, and the fully categorical treatment of algebra of programming. It asks, what did the scan lemma and Horner's rule mean for nonlinear data types like trees? Key contributions, data type generic tales, and inits. For lists, tails returns all suffixes, and inits returns all prefixes. For a general data type, for example, a tree, a tail, or subtree of a data structure is a subterm. An initial segment is the structure with some subterms replaced by the empty structure. The paper introduces the labeled variant of a data type, given a type constructor F. The labeled variant provides exactly one label per node, regardless of the original labeling. This gives a data type generic notion of the tree of all subterms. Data type generic scan lemma. Scans equal to map, fold phi, subtrees, where subtrees produces the labeled variant tree, whose node labels are the subterms of the original tree, and scans replaces each node's label with the fold of the subtree rooted there. This generalizes scan. E equal to map, fold, e, inits from lists to arbitrary data types. Data type generic Horner's rule. The paper also generalizes Horner's rule, given a sum algebra and a product algebra under suitable distributivity conditions. Map inits equal to fold for a suitably defined combining and significance. This paper shows that the laws discovered for lists are not list-specific accidents, but instances of general algebraic principles that hold for any inductively defined data type. The data type generic scan lemma is a particularly beautiful result, and Gibbons later expanded on it in his work on generic downwards accumulations. 8. Algorithm Design with Haskell, 2020. Citation, R. S. Byrd, N.J. Gibbons. Algorithm Design with Haskell, Cambridge University Press, 2020. Context. This book is Byrd's final major work. Co-authored with Jeremy Gibbons, it represents a deliberate return to the original vision of a textbook on algorithmics, the imagined book that motivated the entire BMF project from the 1970s onward. Unlike algebra of programming, it uses plain Haskell with no squiggles, no category theory, and only a minimal excursion into non-determinism. Structure. The book covers algorithm design techniques, each presented as a calculational derivation. Divide and conquer, including MSS, maximum non-segment sum, greedy algorithms, including Huffman coding, scheduling, thinning. When greedy fails, a thinning step prunes the search space. Dynamic programming, systematic memoization of recursive specifications, exhaustive search, backtracking, branch and bound laws presented. All the core laws are re-derived in Haskell notation. 1. Map Fusion Map F. Map G equal to map F G. 2. Fold fusion folder. G A equal to folder. HB provided F A equal to B and F. G XY equal to HX FY for all x y. 4. Fold scan fusion. Foldal G A. Scan left B equal to F S T. Foldal H A B for suitably defined H. 5. Horner's rule. Expressed as a derivation pattern for problems of the form maximum. Map. Foldal FE tails. 7. Greedy Conditions. The greedy algorithm produces an optimal solution when a. A greedy choice can always be extended to an optimal solution. 8. Thinning conditions. When greediness is too aggressive, a thinning step retains a manageable subset of candidates. Notation. Where the 1989 paper used max, sum segs. This book writes maximum, mapsum, segs. The laws are the same, only the surface syntax has changed. Significance. Algorithm design with Haskell closes the circle opened in the 1970s. It is the accessible textbook on algorithmics that Byrd and Myrtons envisioned, written in a notation that a broad audience can read. It demonstrates that the algebraic approach to algorithm design, deriving efficient programs from clear specifications by equational reasoning, is viable and practical, without any special notation or advanced mathematics. Byrd passed away in 2022. This book stands as his final statement on the subject, the evolution of notation for fold and scan. The symbols used for reduce, fold, and scan changed substantially across Byrd's publications and the broader BMF community. This section traces that evolution. Phase 1, APL Origins, 1962 to 1978, Kenneth Iverson's A Programming Language, 1962, introduced, APL name, meaning plus seven, plus reduce scan sum of a vector, fold right with plus running sums, prefix sums. The slash for reduce and backslash for scan became standard in APL. In 1978, Iverson's operators and functions added the commute operator, written with the tilde diurasis glyph, which swaps the arguments of a dyadic function, a precursor to Byrd's tilde notation for flip. APLs reduce and scan are symmetric. They assume the operator is associative and make no left, right distinction. Phase 2. Mearton's Algorithmics, 1984 to 1986. Lambert Myrton's adopted APLs/ directly into his algorithmics notation at CWI Amsterdam. Symbol, meaning, symmetric reduce from APLs plus, symmetric scan from APLs plus. These still require associativity and have no left, right distinction. Phase 3, the Squiggle period, 1985 to 1988, Byrd and Meartons, working within IFIP WG, 2.1, introduced directed folds and scans. The key innovation was adding directional arrows over the slash to indicate processing order. According to Gibbons, the School of Squiggle, 2020, arrows for directed folds and scans, and now called fold, and scunt in Haskell, to preserve the historical glyph shapes, the exact fold and scan symbols are shown below as readable. PRG, 69 facsimiles rather than being squeezed into tiny table cells. Directed folds, t directed scans. Upper left, 2, right, lower right, 2, left, upper left, 2, right, lower modern, foldal, plus, e, folder, e, right, 2, left, modern, scale, 4, e, scanner, plus, e. Other symbols from the same period were still written compositionally, for symmetric reduce, f for map, and for flip. The design principle, single slash, equal to fold, one result, double slash, equal to scan, all intermediate results. The arrow indicates processing direction, left, to, right on the upper fold, scan form, right, 2, left on the lower one. This is the notation used in PRG 56, 1986, PRG 64, 1987, and PRG-69, 1988. Though the printed monographs were typeset, with 1980s tools, and the exact glyph rendering varies. Phase 4, the Retreat from Squiggles, 1988-1989. Byrd and Waddler's textbook Introduction to Functional Programming, 1988, abandoned the squiggly symbols in favor of alphabetic Miranda. Style names. The 1989 Algebraic Identities Paper followed suit, explicitly stating, in order to make the material as accessible as possible, we shall use the notation for functional programming described by Byrd and Waddler. 1989 Notation, meaning left fold, right fold, left scan, foldle, for, folder, for, E. Scan, E scan, E, map, F. Right shon, shar. The squiggly symbols for fold. Scan were never used again by Byrd in published work after 1989. Phase 5. Categorical notation, 1993 to 1997. In the Algebra of Programming 1996, Bird and Demore replaced fold with the MF, catamorphism, in banana brackets, and unfold with the anamorphism in lens brackets. Symbol, meaning, dead, catamorphism, generalized fold, anamorphism, generalized unfold, hylomorphism, unfold, then fold. Scans are expressed indirectly as natural transformations on initial algebra. There is no dedicated scan symbol. Phase 6. Plain Haskell, 1998 to 2020. From the second edition of Byrd's textbook, 1998, through algorithm design with Haskell, 2020. All notation is standard Haskell. Foldle. Folder. Scanl. Scanner. Map. No special symbols. Summary Timeline. Year source. Fold scan. 1962. Iverson. APL. 1978. Iverson. Operators and Functions. 1984. Meartons. Algorithmics. 1986 to 1900. Nearten's and 986-9. 1988. Bird and Waddler. Textbook. 1989. Bird. Algebraic Identities. 1996. Bird and Damore. AOP 2020. Bird and Gibbons. A.D. Witch. Plus. Same. Directed Fold Glyphs. See Phase 3. Foldal. Folder Foldal Folder. Or Phi or Foldal Folder. Plus. Same. Directed scan glyphs. See phase 3. Scale. Scanner scale. Scanner. Natural transformation. Scan. Scanner. The exact 1986 to 1988 fold. Scan facsimiles are shown at readable size in phase 3 above. The summary timeline. Names the notation without shrinking. Scanned glyphs into illegible table cells. Note on the tilde, birds for flip, where a B equal to B A appeared in PRG 56, 1986. Iverson had used the related glyph, tilde de racis, APL glyph, for the commute operator in APL since 1978. When Iverson designed J circa 1990, he simplified this to a bare tilde. Whether Byrd's notation was directly influenced by APL's or arrived independently. From the mathematical convention of tilde's variant is unclear, but Byrd was demonstrably familiar with APL. The BMF borrowed, produced directly from it. Summary. An introduction to the theory of lists. Theorems, or plus, Byrd, Demore, and Hugendike, 1996, or Generic Functional Programming, or Data Type Generic Scan Lemma and Horner's Rule, or V. Byrd and Gibbons, 2020. Algorithm Design with Haskell, Modern Haskell rederivation, no squiggles, the accessible textbook Byrd always envisioned. Appendix A. Quick reference of core laws. For convenience, here are the principal laws in modern Haskell style notation. L1. Map Fusion. Map Promotion. Map F Concat equal to Concat. Map Map F L3. Fold Promotion. Folder F E. CONCAT equal to folder F E. Map folder F E L4. Fold Fusion. H folder. F A equal to folder G B. Provided H A equal to B and H Fx Y equal to G X H Y L5. Scan lemma. Accumulation lemma. Scale F E equal to map foldal F E in its L6. Last fold identity. Last. Scale F Equal to Foldal F E L seven. Fold scan fusion. Foldal G A. Scale F B equal to F S T. Foldal H A G B B. Where H A C C S X equal to A C C G F S X F S X L eight. Horner's rule if distributes backwards over folder. 1G map foldal F E tails equal to Foldal H E, where H a B equal to G, F a B, E L9. Homomorphism, Lemma, H equal to folder 1G, map, F, F H A, equal to F A, and H XS plus plus Y S equal to H XS G. H Y S L10. Duality, foldal, F E equal to folder, flip F, E reverse. Appendix B. Core laws in BMF symbolic notation. The same laws as Appendix A, expressed in the Bird Mirtons, squiggle notation as used in PRG-56, 1986, and PRG-69, 1988. The fold and scan symbols use the arrow, over, slash convention, confirmed by Gibbons, 2020. Symbol, Al, meaning map, apply to every element, symmetric reduce by, requires associativity, left fold with seed, over left, to right, modern foldal, right fold with scode, over, right to left, modern folder, left scan with seed E. Over, left to right accumulation, modern scale. C binary, right scan with seed E. Over, right to left accumulation, modern scan. List concatenation plus plus I A conclatten. Reduce by concatenation. Singleton list containing A empty list. Ida flip of ABBA. Filter by predicate P functional composition. Haskell's boo design principle. Single slash equal to fold. One result, double slash, scan, all intermediate results. The arrow indicates direction, left to right, plus equal to right to left. LL map fusion distributivity over composition. Nuf egal a f plus g's l2 map promotion. Join rule for map f equal to f L3 reduce promotion. Join rule for reduce 41 times 1 equal to L Tor fold fusion for right reduction. H 670 equal to B provided HAB and HI equal to Ha Y for all. Y L5 accumulation lemma scan lemma equal to seventh inits L6 last fold identity. Last E equal to E L seven fold scan fusion a b equal to P1, a B B where R S X equal to R S X S X a lacht. Horner's rule if distributes backwards over that is a B C equal to A C B C then tails egal a e, where equal to I D and a B equal to a B E L9 Homomorphism Lemma H equal to F H A equal to F A and H XY equal to H X H Y. L ten duality lemma e equal to e reverse where a b equal to b a