File:Bird foldl map fusion.pdf
Jump to navigation
Jump to search
No higher resolution available.
Bird_foldl_map_fusion.pdf (766 × 470 pixels, file size: 45 KB, MIME type: application/pdf)
Captions
Captions
Add a one-line explanation of what this file represents
Summary[edit]
| 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}
|
[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.
- ↑ 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
\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[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. |
Licensing[edit]
I, the copyright holder of this work, hereby publish it under the following license:
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.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 13:54, 25 September 2019 |  | 766 × 470 (45 KB) | Jochen Burghardt (talk | contribs) | User created page with UploadWizard |
You cannot overwrite this file.
File usage on Commons
The following page uses this file: