How It Works: Union

Here is a recursive version of the set-theoretic function, Union, which returns the common elements of two or more sets (represented as Lists in Mathematica).

There are two base cases: 1) The union of any set with the empty set is the set itself, and 2) The union of any set with a single element set is the single element set appended to the other set. The recursive case is: 3) The union of any two Lists is the union of the first List with the First element of the second List (i.e. the single element base case), which, calling itself, recurses down the Rest of the second List until it hits the empty set base case (an empty List), at which point it unwinds back out to produce the overall union.

Union produces a set of unique elements  — no duplicates — so we need to de-dupe the List. An easy way to do that is Sort it and use a replacement Rule (we could also use the built-in DeleteDuplicates or How It Works: DeleteDuplicates).

I show two ways to control the Precedence of the abbreviate operators for ReplaceRepeated vs Postfix. Since with Precedence of 110 ReplaceRepeated is a little 'stickier' than Postfix at 70 Sort will stick to the ReplaceRepeated function unless we do something. So we can either enclose the compound function in parentheses before applying ReplaceRepeated as in the 2^nd base case or we can use Postfix with Slot (#) and pure Function (&) as typical in my extended Postfix syntax as in the recursive case.

Clear@myUnion;

myUnion[list1_List,{}]:=list1; (* 1st base case *)

myUnion[list1_List,element_]:=(If[MemberQ[list1,element],list1,list1/.{x___}->{x,element}] //Sort)//.{a___,b_,b_,c___}->{a,b,c}(* 2nd base case *)

myUnion[list1_List,list2_List]:=Module[{union},union=myUnion[myUnion[list1,First@list2],Rest@list2]//Sort//#//.{a___,b_,b_,c___}->{a,b,c}&
] (* recursive case *)


myUnion[{1,2,3,4},{}]

{1,2,3,4}

myUnion[{1,2,3,4},5]

{1,2,3,4,5}

myUnion[{1,2,3,4},2]

{1,2,3,4}

This shows the need to add a delete duplicates function:

myUnion[{1,2,2,3},2]

{1,2,2,3}

A simple replacement Rule does the job, but use ReplaceRepeated or only the first instance of a duplicate will be replaced:

{1,2,2,3,4,4}/.{a___,b_,b_,c___}->{a,b,c}

{1,2,3,4,4}

{4,4,1,3,3,2,2}//.{a___,b_,b_,c___}->{a,b,c}

This works without the delete duplicates function.

myUnion[{1,2,3,4},{3,4,5,6}]

{1,2,3,4,5,6}

But this would fail without it. First without delete duplicates.

myUnion[{1,2,2,3,4},{3,4,5}]

{1,2,2,3,4,5}

And now with delete duplicates.

myUnion[{1,2,2,3,4},{3,4,5}]

{1,2,3,4,5}

And the base case.

myUnion[{3,2,1,2,2,3},3]

{1,2,3}

And the recursive case.

myUnion[{1,2},{2,3,4}]

{1,2,3,4}

Examples of Postfix Usage and Precedence Analysis

As stated in the Mathematica archives and this blog (two parts), one of the unique aspects of my book is extensive, pervasive usage of Prefix to simplify code and save keystrokes. Like any usage of abbreviated operators, this can require knowledge of operator Precedence.


First, here's a common example of abbreviated operator precedence without Prefix. Do we need parens around the exponential coefficients?

Plot[E^-r t/.{r->.5},{t,-2,10}]

The graph shows something is wrong and Precedence analysis tells us yes, we need parens.

Precedence/@{Power,Minus,Times,ReplaceAll}

{590.,480.,400.,110.}

Plot[E^(-r t)/.{r->.5},{t,-2,10}]

Here's a typical example using Prefix. Will this function work as intended? (It's from S11: What's New in Mathematica 8 by Paul Wellin.)

f1@x_ := 1/x Cos[Log@x/x]; Plot[f1@x, {x, 0, .01}]

What would speed up Precedence analysis would be seeing an operator's Precedence popup on Mouseover, like a Tooltip. And a more minor recommendation to WRI is to make Precedence Listable to avoid needing Map. But that only saves one keystroke and I'm after much bigger game by recommending extensive usage of Prefix.

A tip is to list the operators in the order they appear in your function. Then it's easier to see which are 'stickier' than if they are out of order. Anyway, using Precedence, we see that the function will work as intended.


Unprotect@Precedence; SetAttributes[Precedence,Listable]; Protect@Precedence; Precedence@{Divide,Times,Prefix}

{470.,400.,640.}


f1@x_ := 1/x Cos[Log@x/x]; Plot[f1@x, {x, 0, .01}]

Now that we know the Precedence of Prefix and Divide, we can write the following interesting usage of Range with impunity; we don't need Table or Map. It works because Divide is Listable.

Range@5/6

{1/6,1/3,1/2,2/3,5/6}

A New Mathematica Programming Style, Part Two

The list of abbreviated operators from which this table was generated is in the previous post (Part One). Now we continue the slides from my 2007 presentation of a new Mathematica dialect.








Suggestions for Wolfram Research

• Use the Precedence table in documentation instead of Operator Input Forms table
• Add mouseover Tooltips with Precedence to all abbreviated operators so we can readily see their Precedence
• Map Tones on to all abbreviated operators' Tooltips, scaled appropriately, so we can mouseover them and hear their Precedence
• And liberate Tones from CellularAutomata; Tones should permeate Mathematica—Mathematica should sound like R2D2

Questions for Wolfram Research

• How does PrecedenceForm work?
• How do the "structural elements," all having Precedence = 670, work?
• Why not make Comma right-associative with actual Precedence 670 so we can write multiple-argument Prefix functions like this:

f@a,b,c := g@i,j,k

Next: Syntax Problems 3, 4, 5 and 6

Nested matchfix violates various programming good practices

"The guiding principle [of the order of statements of code] is the Principle of Proximity: Keep related actions together."

Manipulate[
 GraphicsRow[{Graphics[Disk[]], Graphics[Disk[]], Graphics[Disk[]]},
  Spacings -> Scaled[i], Frame -> True, Dividers -> All],  {i, .1, 1}]

"If you draw a box around each statement, they should not overlap."

"As a general principle, make the program read from top to bottom rather than jumping around. Experts agree that top-to-bottom order contributes most to readability."

"The Fundamental Theorem of Formatting is that good visual layout shows the logical structure of the program."
-Steve McConnell, Code Complete

'The price paid for functional style programs without excess auxiliary variables is "a large number of brackets."'
  -Michael Trott

Postfix "afterthought" functions can't take arguments, which stymies extended command-line programming

For example, how do you enter options for Plot:

3 Cos[x] + 2 Cos[2 x] + Cos[3 x] //Plot[ ??]

Initiates to functional programming need to learn to think "inside out" or right-to-left

Procedural programmers are often less than thrilled with functional syntax

We would like to write code to emphasize what's important and downplay what's not

Illustration of Matchfix Readability Problems

Compare three versions of a simple function using increasing numbers of optional arguments

Note the violation of the Principle of Proximity

Do boxes drawn around statements overlap?

In example #3, note the code is structured to emphasize whichever expression we wish, in this case, GraphicsRow, not Manipulate, which is just the "wrapper"

Manipulate[GraphicsRow[{Graphics[Disk[]], Graphics[Disk[]], Graphics[Disk[]]},
  Spacings -> Scaled[i], Frame -> True, Dividers -> All],  {i, .1, 1}]

Manipulate[ GraphicsRow[{Graphics[Disk[]], Graphics[Disk[]], Graphics[Disk[]]},
  Spacings -> Scaled[i], Frame -> True, Dividers -> All,
  Alignment -> {Center, Center} , AlignmentPoint -> Center,
  AspectRatio -> Automatic, Axes -> False, AxesLabel -> None,
  AxesOrigin -> Automatic, AxesStyle -> {}, Background -> None,
  BaselinePosition -> Automatic, BaseStyle -> {},
  ColorOutput -> Automatic, ContentSelectable -> Automatic,
  DisplayFunction :> $DisplayFunction, Dividers -> None,
  Epilog -> {}],  {i, .1, 1}]

GraphicsRow[{Graphics@Disk[], Graphics@Disk[], Graphics@Disk[]},
 Spacings -> Scaled@i, Frame -> True, Dividers -> All,
 Alignment -> {Center, Center} , AlignmentPoint -> Center,
 AspectRatio -> Automatic, Axes -> False, AxesLabel -> None,
 AxesOrigin -> Automatic, AxesStyle -> {}, Background -> None,
 BaselinePosition -> Automatic, BaseStyle -> {},
 ColorOutput -> Automatic, ContentSelectable -> Automatic,
 DisplayFunction :> $DisplayFunction, Dividers -> None, Epilog -> {}]
// Manipulate[#,  {i, .1, 1}] &

And the more nested the function, the worse it is

Postfix/Pure Function Style: Functional-Procedural Fusion

A Solution: extended usage of Postfix and pure Function

As an alternative to this 'traditional' usage of matchfix (the error is deliberate):

expr7 [ expr6 [ expr5 [expr4 [expr3 [expr2 [expr1 ] ] ] ] ] ] ]

Consider writing this, using Postfix and pure Function:

expr1 // expr2 # & // expr3 # & // expr4 # & // expr5 # & // expr6 # & // expr7 # &

And you can write it down the page, too:

expr1 //
expr2 # & //
expr3 # & //
expr4 # & //
expr5 # & //
expr6 # & //
expr7 # &

It works as simply as this:

expr1 // expr2 #& is parsed as: expr2[expr1]

Amounts to a fusion of procedural and functional styles

Functional programming that looks procedural

FP Fusion Examples

Command line or one-liner

Sin@x//Plot[#,{x, -5, 5}]&

Extended one-liner or function

This fits the general pattern of a class of functions. You generate some data or intialize a function, then perform a few transformations on it, and then you want to view it.

Here we write it as a readable one-liner, sequentially across the page.

Clear@g; g@x_ := RandomReal[];
Table[g@i, {i, 100}] //Take[#, 80]& //100 #& //#^2& //ListPlot[#, Filling->Axis]&

Or sequentially down the page, nice and clean.

g@x_ := RandomReal[];
Table[g@i, {i, 100}] //
Take[#, 80]& //
100 #& //
#^2& //
ListPlot[#, Filling->Axis]&

If needed, we can use variable assignment within Postfix statements by appropriate parentheses:

Range@6 // (list1 = Partition[#, 3]) &; list1[[1]]

{1, 2, 3}

Summary

Computer programming's destiny is to control high-order complexity

Mathematica is a modern scientific synthesis whose core is the most advanced programming language paradigm

Mathematica's destiny is to play a lead role in the scientific challenges of our age

Version 8 shows its capabilities go far beyond those of any other programming language

Prefix and FP Fusion are a suggested improvement in syntax toward more understandable and controllable programs

Comments and suggestions are welcome: lowlevelfunctionary@kriscarlson.com

Acknowledgements and References

Stephen Wolfram

The Mathematica Book
Code examples in A New Kind of Science

Roman Maeder, harry calkins

A First Course in Mathematica
Programming in Mathematica

Roman Maeder

Programming in Mathematica 2nd Ed.
The Mathematica Programmer
The Mathematica Programmer II
Computer Science with Mathematica

David B. Wagner

Power Programming in Mathematica: The Kernel

John W. Gray

Mastering Mathematica, 2nd Ed.: Programming Methods and Applications

Michael Trott

The Mathematica Guidebook: Programming

Paul R. Wellin, Richard J. Gaylord, and Samuel N. Kamin

An Introduction to Programming with Mathematica, 3rd Ed.

Christian Jacob

Illustrating Evolutionary Computation with Mathematica

Nancy Blachman

Mathematica: A Practical Approach

Stan Wagon

Mathematica in Action

And thanks to the attendees of this talk who had valuable suggestions, in particular Paul Abbott, and their forbearance of my first effort using a Mathematica slide show

A New Mathematica Programming Style, Part One

This is the presentation I gave at the Wolfram User Conference in 2007, updated for version 8. Part Two is here.

A New Mathematica Programming Style, Part One

Kris Carlson

Author, The Way of Mathematica (forthcoming)

An Historical Perspective on Computer Programming

"The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of ... procedural epistemology--the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects. Mathematics provides a framework for dealing precisely with notions of 'what is.' Computation provides a framework for dealing precisely with notions of 'how to.'"

Harold Abelson and Gerald Jay Sussman, The Structure and Interpretation of Computer Programs

Origins of Geometry

Beginnings: Accurately surveying land boundaries

Destiny: Euclid's creation of the first axiomatic science

Origins of Computer Programming

Beginnings: Very abstract notions of computation by Church, Turing, Kleene and others

Destiny: The control of complex processes

The Main Challenges of Modern Science

Genetic Engineering

Taking control of the analog computer program immanent in DNA-RNA-protein

Artificial Intelligence

Reverse-engineering the agencies of intelligence created by evolution and creating new ones

Creating and initially controlling intelligences greater than our own

Nanotechnology

Programming at the atomic and molecular level to control materials

These challenges put the Abelson/Sussman thesis in perspective : It' s all about controlling complex processes

What about "A Theory of Everything?"

A misnomer. If created, which I doubt it will be, it would be nothing more than a theory of the currently known physical microcosm

Note that computer programming cannot be derived from it--but it can be derived from computer programming

Mathematica's Place in History

Mathematica is a scientific synthesis like those of Euclid, Spinoza, Newton, Locke, Lagrange, Hamilton, Darwin, Maxwell, Gibbs, Shannon, and others

"Everything is an expression"--a central unifying syntactic principle like energy in physics or bits in information theory

More Elements of the Mathematica Synthesis

General symbol manipulation program

Pattern matching engine

A variety of programming styles and devices

Axiomatization of lower-level functionality (Table, Map* family, Nest* family, etc.)

Interpret and compile modes

Interface/IDE\--the Front End Notebook

Plethora of built-in functions

Extension to all special functions via Mathematica Functions site

Extensive and growing graphics and visualization capabilities

Effectively unlimited notation synthesis

Equation solving

Numerical analysis/evaluation

Axiomatization of higher-level functionality (CellularAutomata, Manipulate, TuringMachine, etc.)

gridMathematica

Documentation Center

MathWorld

Presentation and documentation formats

webMathematica

Demonstrations site

Curated data/Data paclets

Incipient semantic net (WordData)

What is the goal of programming style?

Help manage ever-increasing complexity

Streamline the human-computer interface from both sides

A New Mathematica Programming Style

First principle: Replace all matchfix single argument function applications f [ arg ] with Prefix function applications f @ arg

Requires some knowledge of the 1000-level Precedence table

Second principle: Replace nested matchfix with Postfix + pure Function

Prefix Functional Syntax

Cleaner and more efficient than matchfix

Use prefix function application, @, for single-argument functions

Matchfix style:

f[ g[ h[ i [j] ] ] ]

Prefix style:

f @ g @ h @ i @ j

First two syntactical problems with list- or matchfix-based language

1. Humans have difficulty parsing deeply nested expressions (>3)
2. Humans are not regular expression parsers

Basic Benefits of Prefix style

Every pair of brackets we lose makes our expressions easier to read and understand

Every pair of brackets for which we don't have to type or move the cursor saves us time

A Prefix Style Example

Each @ tells us there is no complex nesting for that function, no options or arguments to look for, no brackets to match.

We can focus our attention on the functions that do use matchfix and identify their arguments and options.

There are fewer nested brackets to sort out.

Here's some code from Trott, The Mathematica Guide to Graphics, in matchfix and Prefix styles:

Show[GraphicsArray[

Block[{$DisplayFunction = Identity},

(* display absolute value of 2D Fourier transform *)

ListDensityPlot[Abs[Fourier[Table[1/#[i, j], {i, 256}, {j, 256}]]],

Mesh -> False, ColorFunction -> (Hue[0.8 #]&)]& /@

{GCD, LCM}]]]

Show@GraphicsArray@

Block[{$DisplayFunction = Identity},

(* display absolute value of 2D Fourier transform *)

ListDensityPlot[

Abs@Fourier@Table[1/#[i, j], {i, 256}, {j, 256}],

Mesh -> False, ColorFunction -> (Hue[0.8 #]&)]& /@

{GCD, LCM}]

More Prefix Style Examples

Basic Usages

One argument function definitions:

f[x_] := Sin[x]

f@x_ := Sin@x

One argument functions or assignments:

Log@100^100//N

2.11139*10^66

walk1D3@n_:= NestList[#+Random[Real,{-1,1}]&, Random[Real, {-1,1}],n];

walk1D3@10

{-0.206019, -0.914893, -0.951759, -1.04967, -0.299963, -0.8917, -0.147434, 0.764746, 1.57289, 1.40045, 2.13796}

list5 = Range@10;

Clear@list5;

Histogram@%

Histogram[Null]

Needs@"Combinatorica`"

Multiple one-argument function composition:

f@g@h@i@j@k

Sin[g[h[i[j[k]]]]]

First@Rest@Most@Range@10

Function definitions with lists as argument:

f@{a_, b_, c_}:= n@{a,b,c}

Precedence in Mathematica

The main objection to Prefix is that you have to know operator precedence

However this objection applies to all abbreviated operators (+, *, ^, [[ ]], { }, /@, etc.)

Mathematica is endowed with "a variety of special characters that greatly increase readability and elegance."

FORTRAN (FORmula TRANslation; early and primitive, but elegant), Mathematica (an advanced synthesis):

A conscious effort was made to provide a path of least action or smooth transduction from mathematical notation to code

Further, a significant feature of V6 is the addition of 100 undefined operators to facilitate creating user-defined notations

I submit that if you use Prefix, you will use it more often than the most common abbreviated operators

Precedence directs the order of abbreviated operators' operation

Precedence can be symbolized by parenthetical grouping, such as: a + (b ^ c) versus (a + b) ^ c

The Mathematica reference on precedence in 5.2 was Table A.2.7, now is in tutorial / InputSyntax: Operator Input Forms

It lists all abbreviated operators in tables of decreasing precedence

However, a superior reference can be generated from a little code

There exists an undocumented function, Precedence

Voila:

Precedence@Prefix

640.

It is not Listable, but it should be! Either reset Attributes to Listable or just Map it:

Precedence /@ {Prefix, Factorial}

{640., 610.}

What happened in the previous slide?

Prefix is a little "stickier" than Factorial==@ sticks to n more than ! does--and so we got (IntegerDigits@n)! instead of IntegerDigits[ n! ]

When faced with a few abbreviated operators, map Precedence onto them in the order they present in your expression

a + b * c ^ d - e

Precedence /@ {Plus, Times, Minus, Power}

{310., 400., 480., 590.}

Precedence mnemonics: Think of operator "stickiness" or "binding strength"

Mathematica's 1000 - Level Precedence Table

Abbreviated Operators

This list includes all nondefined operators as of v8.0, about an increase of 60 more over v6.0. I include a few of a group of syntax operators that have Precedence = 670, such as Parentheses, Comma, and Subscript. These are which are referred to in the documentation as "structural operators."

abbreviatedOperators = {Operate, Through, Pi, I, Unset, Plus, N, Infinity, Tilde, Backtick, Level, Position, Alternatives, Repeated, RepeatedNull, Condition, Except, AddTo, PreIncrement, Increment, Decrement, PreDecrement, Map, MapAll, MapAt, MapThread, Apply, Factorial, Factorial2, Prefix, Postfix, Infix, MatchFix, Comma, Head, Part, PatternTest, Power, Function, Set, SetDelayed, Rule, RuleDelayed, TagSet, UpSet, Unset, Put, PutAppend, Append, PrependTo, AppendTo, Get, Overscript, Underscript, Subscript, Sum, Product, Coproduct, PartialD, DifferentialD, Integral, Cap, Cup, TimesBy, Replace, ReplaceAll, Colon, SemiColon, CompoundExpression, Therefore, Because, And, Or, Not, Element, ForAll, Exists, NotExists, Xor, Nand, Nor, SuchThat, Implies, RoundImplies, RightTee, LeftTee, DoubleRightTee, DoubleLeftTee, VerticalSeparator, Union, Intersection, Vee, Wedge, Backslash, Divide, PlusMinus, MinusPlus, CirclePlus, CircleMinus, Times, CircleTimes, CenterDot, Diamond, Star, NonCommutativeMultiply, Cross, Dot, D, Del, Square, SmallCircle, Integrate, Sqrt, Conjugate, Transpose, ConjugateTranspose, Derivative, StringJoin, Slot, SlotSequence, Out, In, Blank, BlankSequence, BlankNullSequence, Optional, Pattern, Default, MessageName, Piecewise, Symbol, String, Integer, Real, Complex, FullForm, Null, List, AngleBracket, Floor, Ceiling, BracketingBar, DoubleBracketingBar, Parentheses, Quote, DoubleQuote, Percent, SubtractFrom, DivideBy, Equal, Greater, Unequal, Less, LessEqual, SameQ, UnsameQ, Question, Underscore, Slash, FormBox, Hold, HoldPattern, "=*=", Conditioned, Distributed};

Length@abbreviatedOperators

165

After defining the table of Abbreviated Operators, this code generates the first formatted table that you see at the top of this post, listing them in descending order of Precedence.

$PrecedenceTable = {#, Precedence@#} & /@abbreviatedOperators // #[[Ordering@#[[All, 2]] ] ] & //Reverse // Partition[#, Length@#/4 // Floor] & //TableForm[#, TableDirections -> Row, TableSpacing -> {3, 1}] & //Style[#, Magnification -> 1] &

And this code generates the second formatted table that you see at the top of the next post, listing Abbreviated Operators alphabetically.

$PrecedenceTable = {#, Precedence@#} &/@ abbreviatedOperators // #[[Ordering@#[[All, 1]] ] ] & //Partition[#, Length@#/4 // Floor] & //TableForm[#, TableDirections -> Row, TableSpacing -> {3, 1}] & //Style[#, Magnification -> 1] &

Introduction to my Mathematica guide: The Way of Mathematica

Greetings! Several years ago I began creating a guide to Mathematica for my own use--as a reference to what I wanted to learn and remember, especially about Mathematica programming. I also wanted to capture a philosophy about Mathematica, like the Tao--as in the Tao Teh Ching--or Way of Mathematica. How does one 'go with the flow' when programming in Mathematica? It evolved into a book and here I'm posting drafts from the book. Please keep in mind these are drafts and may contain errors or omissions. Of course I'm very interested in your comments and corrections.

One device I use that you may not like is capitalizing Mathematica functions, such as Map or Import, as proper nouns. The idea is to highlight them and impress them on our minds. However I can also see that this usage can be irritating--if so let me know.

More significantly, I use a new programming dialect that I first presented at the Wolfram Technology Conference in 2007--you can download the presentation here:

http://library.wolfram.com/infocenter/Conferences/7002/

This dialect, which features heavy usage of Prefix (f@x) and Postfix (x//f) syntax with pure Function (x//f [#, {parameters}]&, offers a number of significant advantages over the traditional Matchfix style. Specifically, these benefits include:

1. Code is more readable
2. We have less typing because we finally depart from the confusing matching brackets f[[[parameter1, g[parameter2], h[parameter3]]]] syntax that goes at least as far back as Lisp
3. Functions are listed in the order in which they are applied as in procedural programming
4. We have more options to organize our code so as to highlight what's important and bury what is not.

We can think of this dialect as a "functional-procedural fusion" and I haven't come up with a better name for it than that. Accordingly another benefit is that the syntax renders Mathematica easier to learn for procedural programmers. Schematically it looks like this:

Traditional Matchfix	h [ g [ f [ x, y ], z ], j ]
Postfix-Pure Function	f [ x, y ] // g [ #, z ]& // h [#, j ]&
Prefix	f @ g @ h @ i

Using Prefix and Postfix with abbreviated operators (such as +, -, x, /, ^, as in f@x+5) necessitates knowing Mathematica's Precedence table, included in the 2007 presentation and I will post the code and table for Mathematica 8 here. You can always determine the Precedence of any operators using that undocumented function:

In[68]:= Precedence /@ {Plus, Subtract, Times, Divide, Power}

Out[68]= {310., 310., 400., 470., 590.}

And you can always just use Matchfix, or group with parentheses, if you don't want to deal with Precedence. Of course we all deal with Precedence, and few would advise abolishing all abbreviated operator usage, in mathematics and Mathematica. So think of Prefix in Mathematica as a greatly extended usage of the power of abbreviated operators that harks to the origins of math.

http://reference.wolfram.com/mathematica/ref/Prefix.html

http://reference.wolfram.com/mathematica/ref/Postfix.html