File:Bird foldl map fusion.pdf

From Wikimedia Commons, the free media repository
Jump to navigation Jump to search

Bird_foldl_map_fusion.pdf(767 × 472 pixels, file size: 45 KB, MIME type: application/pdf)


Add a one-line explanation of what this file represents



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.


Own work


Jochen Burghardt

Other versions

File:Bird foldl map fusion.pdfFile:Bird foldl map fusion svg.svg

LaTeX source code of file "Bird foldl map fusion.tex"




\textcolor{cFct}{\put(49.000,52.000){\makebox(0.000,0.000)[br]{$\map \; (-)$}}}%
\textcolor{cFct}{\put(82.000,35.000){\makebox(0.000,0.000)[bl]{$\foldl \; (\stackrel{.}{-}) \; 0$}}}%
        \shortstack[r]{where $x \stackrel{.}{-} y$\\is defined as\\$x + (-y)$}}}}%
\textcolor{cFct}{\put(49.000,22.000){\makebox(0.000,0.000)[tr]{$\foldl \; (+) \; 0$}}}%

General explanations for this and related images[edit]

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[edit]

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


% set color according to current nesting depth

% open a new sublist

% close current sublist

% separate elements in current lsist

% rendering commands

\newcommand{\List}[1]{\open #1 \close}

\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}



Function definitions[edit]

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

Function Image Location description
concat File:Bird foldl promotion.pdf upper left Concatenate a given list of lists into a single list
concat File:Bird map promotion.pdf upper left
foldl File:Bird foldl promotion.pdf lower left Join all elements of a given list by a given binary operator .
foldl File:Bird horner rule 6789.pdf right
fst File:Bird fold scan fusion 6789.pdf lower right Return the left component of a pair.
inits File:Bird scan lemma 6789.pdf upper left Return a list of all initial segments of a given list.
map File:Bird foldl map fusion.pdf upper left Apply a given unary operator pointwise to each element of a given list.
map File:Bird map promotion.pdf lower left
scanl File:Bird fold scan fusion 6789.pdf upper left Like foldl, but keep intermediate results arranged in a list.
scanl File:Bird scan lemma 6789.pdf right
tails File:Bird horner rule 6789.pdf upper left Return a list of all final segments of a given list.


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.

File history

Click on a date/time to view the file as it appeared at that time.

current13:54, 25 September 2019Thumbnail for version as of 13:54, 25 September 2019767 × 472 (45 KB)Jochen Burghardt (talk | contribs)User created page with UploadWizard


Structured data

Items portrayed in this file

no value