File:Bird foldl map fusion.pdf

Summary

Description
English: Computation example for the fold-map fusion law from Bird.1989, p.123 rg. Our example uses integer numbers with binary addition ("") and unary minus sign (""); the binary subtraction ("") is defined from the two former operations.
Date
Source Own work
Author Jochen Burghardt
Other versions File:Bird foldl map fusion.pdf — File:Bird foldl map fusion svg.svg
LaTeX source code of file "Bird foldl map fusion.tex"
\documentclass[12pt]{article}

\setlength{\unitlength}{1mm}

\usepackage[pdftex]{color}
\usepackage{amssymb}
\usepackage[paperwidth=130mm,paperheight=80mm]{geometry}
        
\setlength{\topmargin}{-36mm}
\setlength{\textwidth}{130mm}
\setlength{\textheight}{80mm}
\setlength{\oddsidemargin}{-23mm}
\setlength{\parindent}{0cm}
        
\pagestyle{empty}        

\include{bird_Preamble}

\begin{document}
\begin{picture}(125,75)
        %\put(0,0){\makebox(0,0){$+$}}
        %\put(125,75){\makebox(0,0){$+$}}
%
\put(75.000,65.000){\makebox(0.000,0.000)[b]{{$\List{4\,5\,6\,7\,8\,9}$}}}%
\put(25.000,35.000){\makebox(0.000,0.000)[b]{{$\List{-4\,-5\,-6\,-7\,-8\,-9}$}}}%
\put(75.000,5.000){\makebox(0.000,0.000)[b]{{$\A{(((((0\+\B{(-4)})\+\B{(-5)})\+\B{(-6)})\+\B{(-7)})\+\B{(-8)})\+\B{(-9)}}$}}}%
%       
\thicklines
%       
\textcolor{cFct}{\put(70.000,62.000){\vector(-2,-1){40.000}}}%
\textcolor{cFct}{\put(49.000,52.000){\makebox(0.000,0.000)[br]{$\map \; (-)$}}}%
%
\textcolor{cFct}{\put(80.000,62.000){\vector(0,-1){50.000}}}%
\textcolor{cFct}{\put(82.000,35.000){\makebox(0.000,0.000)[bl]{$\foldl \; (\stackrel{.}{-}) \; 0$}}}%
\textcolor{bCmt}{\put(96.000,12.000){\makebox(0.000,0.000)[bl]{\rule{24mm}{16mm}}}}%
\textcolor{cCmt}{\put(97.000,13.000){\makebox(0.000,0.000)[bl]{%
        \shortstack[r]{where $x \stackrel{.}{-} y$\\is defined as\\$x + (-y)$}}}}%
%
\textcolor{cFct}{\put(30.000,32.000){\vector(2,-1){40.000}}}%
\textcolor{cFct}{\put(49.000,22.000){\makebox(0.000,0.000)[tr]{$\foldl \; (+) \; 0$}}}%
\end{picture}
\end{document}

The laws used in Bird's 1989 paper[1] are exemplified on lists of integer numbers, and arithmetic operations and constants. However, unless otherwise noted, no particular arithmetic properties (like + being commutative, or 0 being the neutral element for +) are presupposed, so that examples remain valid after changing operations and constants arbitrarily.

Lists, and some expressions, are colored by nesting depth; blue arrows indicate function application.

  1. ↑ Richard S. Bird (1989). "Algebraic Identities for Program Calculation". Computer Journal 32: 122–126.

Preamble source code

LaTeX source code of included file "bird_Preamble.tex"
% colors
\definecolor{cFct}      {rgb}{0.00,0.00,0.70}   % fcuntion
\definecolor{bCmt}      {rgb}{0.90,0.90,0.90}   % comment background
\definecolor{cCmt}      {rgb}{0.10,0.10,0.10}   % comment

%\definecolor{cLA}      {rgb}{0.99,0.00,0.00}   % list nest level 1
%\definecolor{cLB}      {rgb}{0.75,0.25,0.00}   % list nest level 2
%\definecolor{cLC}      {rgb}{0.50,0.50,0.00}   % list nest level 3
%\definecolor{cLD}      {rgb}{0.25,0.75,0.00}   % list nest level 4
%\definecolor{cLE}      {rgb}{0.00,0.99,0.00}   % list nest level 5, maximal nesting

%\definecolor{cLA}      {rgb}{0.99,0.00,0.00}   % list nest level 1
%\definecolor{cLB}      {rgb}{0.66,0.33,0.00}   % list nest level 2
%\definecolor{cLC}      {rgb}{0.33,0.66,0.00}   % list nest level 3
%\definecolor{cLD}      {rgb}{0.00,0.99,0.00}   % list nest level 4, maximal nesting

\definecolor{cLA}       {rgb}{0.99,0.00,0.00}   % list nest level 1
\definecolor{cLB}       {rgb}{0.50,0.50,0.00}   % list nest level 2
\definecolor{cLC}       {rgb}{0.00,0.99,0.00}   % list nest level 3, maximal nesting



% list nesting

\newcounter{nest}
\setcounter{nest}{1}

% set color according to current nesting depth
\newcommand{\nestcolor}{%
        \color{cL\Alph{nest}}%
        %(cL\Alph{nest}):%
}

% open a new sublist
\newcommand{\open}{%
        \nestcolor%
        \left[%
        \addtocounter{nest}{1}%
        \nestcolor%
}

% close current sublist
\newcommand{\close}{%
        \addtocounter{nest}{-1}%
        \nestcolor%
        \right]%
}

% separate elements in current lsist
\renewcommand{\,}{%
        \addtocounter{nest}{-1}%
        \nestcolor%
        ,
        \addtocounter{nest}{1}%
        \nestcolor%
}



% rendering commands

\newcommand{\List}[1]{\open #1 \close}
\newcommand{\Nil}{\List{\hspace{.7mm}}}

\newcommand{\Pair}[1]{\langle #1 \rangle}

\newcommand{\map}{\sf map}
\newcommand{\concat}{\sf concat}
\newcommand{\foldl}{\sf foldl}
\newcommand{\tails}{\sf tails}
\newcommand{\inits}{\sf inits}
\newcommand{\segs}{\sf segs}
\newcommand{\scanl}{\sf scanl}
\newcommand{\fst}{\sf fst}

\renewcommand{\sum}{\sf sum}
\renewcommand{\max}{\sf max}

\newcommand{\+}{\!+\!}
\renewcommand{\*}{\!*\!}

\newcommand{\A}[1]{\textcolor{cLA}{#1}}
\newcommand{\B}[1]{\textcolor{cLB}{#1}}
\newcommand{\C}[1]{\textcolor{cLC}{#1}}

Function definitions

An intuitive idea of the definition of the functions involved can be obtained from:

FunctionImageLocationdescription
concatFile:Bird foldl promotion.pdfupper leftConcatenate a given list of lists into a single list
concatFile:Bird map promotion.pdfupper left
foldlFile:Bird foldl promotion.pdflower leftJoin all elements of a given list by a given binary operator .
foldlFile:Bird horner rule 6789.pdfright
fstFile:Bird fold scan fusion 6789.pdflower rightReturn the left component of a pair.
initsFile:Bird scan lemma 6789.pdfupper leftReturn a list of all initial segments of a given list.
mapFile:Bird foldl map fusion.pdfupper leftApply a given unary operator pointwise to each element of a given list.
mapFile:Bird map promotion.pdflower left
scanlFile:Bird fold scan fusion 6789.pdfupper leftLike foldl, but keep intermediate results arranged in a list.
scanlFile:Bird scan lemma 6789.pdfright
tailsFile:Bird horner rule 6789.pdfupper leftReturn a list of all final segments of a given list.

Licensing

I, the copyright holder of this work, hereby publish it under the following license:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
Category:CC-BY-SA-4.0#Bird%20foldl%20map%20fusion.pdf
Category:Self-published work Category:Files by User:Jochen Burghardt Category:Commutative diagrams Category:String (computer science) Category:Images with LaTeX source code Category:Bird-Meertens formalism
Category:Bird-Meertens formalism Category:CC-BY-SA-4.0 Category:Commutative diagrams Category:Files by User:Jochen Burghardt Category:Images with LaTeX source code Category:Self-published work Category:String (computer science)